Quebra-cabeças: Qual é o comprimento esperado de uma sequência iid que aumenta monotonicamente quando extraída de uma distribuição uniforme [0,1]?

Esta é uma pergunta de entrevista para uma posição quantitativa de analista, relatada aqui . Suponhamos que estamos desenhando a partir de uma distribuição uniforme $[0,1]$ e os empates são iid, qual é o comprimento esperado de uma distribuição que aumenta monotonicamente? Ou seja, paramos de desenhar se o desenho atual for menor ou igual ao desenho anterior.

mas acho que calcular essas integrais aninhadas é cada vez mais difícil e não estou conseguindo o "truque" para generalizar para . Eu sei que a resposta final está estruturada $\Pr(\text{length} = n)$

Alguma idéia de como responder a essa pergunta?

Aqui estão algumas dicas gerais para resolver esta questão:

Você tem uma sequência de variáveis ​​aleatórias contínuas de IID, o que significa que elas podem ser trocadas . O que isso implica sobre a probabilidade de obter uma ordem específica para os primeiros valores? Com base nisso, qual é a probabilidade de obter uma ordem crescente para os primeiros valores? É possível descobrir isso sem integrar a distribuição das variáveis ​​aleatórias subjacentes. Se você fizer isso bem, poderá obter uma resposta sem nenhuma suposição de uma distribuição uniforme - ou seja, obtém uma resposta que se aplica a qualquer sequência intercambiável de variáveis ​​aleatórias contínuas.$n$$n$

Aqui está a solução completa ( não olhe se você deve descobrir isso sozinho ):

Seja sua sequência de variáveis ​​aleatórias contínuas independentes e deixe é o número de elementos crescentes no início da sequência. Como essas são variáveis ​​aleatórias permutáveis ​​contínuas, elas são quase certamente desiguais entre si e qualquer ordem é igualmente provável; portanto, temos: (Observe que esse resultado é válido para qualquer sequência IID de variáveis ​​aleatórias contínuas; elas não precisam ter uma distribuição uniforme.) Portanto, a variável aleatória tem função de massa de probabilidade$U_1, U_2, U_3, \cdots \sim \text{IID Continuous Dist}$$N \equiv \max \{ n \in \mathbb{N} | U_1 < U_2 < \cdots < U_n \}$

$$\mathbb{P}(N \geqslant n) = \mathbb{P}(U_1 < U_2 < \cdots < U_n) = \frac{1}{n!}.$$ $N$ $$p_N(n) = \mathbb{P}(N=n) = \frac{1}{n!} - \frac{1}{(n+1)!} = \frac{n}{(n+1)!}.$$ Você notará que este resultado está de acordo com os valores que você calculou usando a integração sobre os valores subjacentes. (Esta parte não é necessária para a solução; é incluída para fins de completude.) Usando uma regra conhecida para o valor esperado de uma variável aleatória não negativa , temos: Observe novamente que não há nada em nosso trabalho que use a distribuição uniforme subjacente. Portanto, este é um resultado geral que se aplica a qualquer sequência intercambiável de variáveis ​​aleatórias contínuas. $$\mathbb{E}(N) = \sum_{n=1}^\infty \mathbb{P}(N \geqslant n) = \sum_{n=1}^\infty \frac{1}{n!} = e - 1 = 1.718282.$$

Algumas idéias adicionais:

Pelo trabalho acima, vemos que esse resultado distributivo e o valor esperado resultante não dependem da distribuição subjacente, desde que seja uma distribuição contínua. Isso realmente não é surpreendente, uma vez que consideramos o fato de que toda variável aleatória escalar contínua pode ser obtida por meio de uma transformação monotônica de uma variável aleatória uniforme (com a transformação sendo sua função quantil). Como as transformações monotônicas preservam a ordem de classificação, examinar as probabilidades de ordenar variáveis ​​aleatórias contínuas arbitrárias da IID é o mesmo que analisar as probabilidades de ordenar variáveis ​​aleatórias uniformes da IDI .

Outro método de solução que fornece a solução para um caso mais geral.

Suponha que seja o comprimento esperado de uma sequência monotônica , de modo que . O valor que queremos calcular é . E sabemos que . Condicionamento no próximo valor,$F(x)$$\{x_1, x_2, ...\}$$x\leq x_1\leq x_2\leq\cdots$$F(0)$$F(1)=0$

onde é a densidade U [0,1]. tão$\pi(y)=1$

Resolvendo com a condição de contorno , obtemos . Portanto, .$F(1)=0$$F(x) = e^{(1-x)}-1$$F(0)=e-1$

Outro método de solução é calcular a integral diretamente.

A probabilidade de gerar uma sequência cuja parte crescente tem comprimento de é , onde .$\geq n$$f^n(0)$$f^n(x) = \int_{x}^{1}\int_{x_1}^{1}\int_{x_2}^{1}...\int_{x_{n-2}}^{1}\int_{x_{n-1}}^{1}dx_ndx_{n-1}...dx_2dx_1$

O que precisamos fazer é calcular .$f^n(0)$

Se você tentar calcular os primeiros , talvez descubra que$f^n(x)$$f^n(x) = \sum_{t=0}^n \dfrac{(-x)^t}{t!(n-t)!}$

Caso base: quando ,$n=1$$f^1(x) = \sum_{t=0}^1 \dfrac{(-x)^t}{t!(n-t)!}=1-x=\int_{x}^{1}dx_1$

Hipótese indutiva: quando ,$n=k$$f^n(x) = \sum_{t=0}^k \dfrac{(-x)^t}{t!(k-t)!}\text{ , for }k \geq 1$

Etapa indutiva: quando ,$n = k+1$

$\ \ \ \ \ f^{n}(x) = f^{k+1}(x) = \int_{x}^{1}f^{k}(x^*)dx^*$

$=\int_{x}^{1}\sum_{t=0}^{k} \dfrac{(-x^*)^t}{t!(k-t)!}dx^*$

$=\sum_{t=0}^{k} \dfrac{-(-x^*)^{t+1}}{t!(k-t)!\times(t+1)}\Biggr|_{x}^{1}\\=\sum_{t=0}^{k} \dfrac{-(-x^*)^{t+1}}{(t+1)!(k-t)!}\Biggr|_{x}^{1}$

$=\sum_{t=1}^{k+1} \dfrac{-(-x^*)^{t}}{t!(k-t+1)!}\Biggr|_{x}^{1}$

$=\sum_{t=1}^{k+1} \dfrac{(-1)^{t+1}}{t!(k-t+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\sum_{t=1}^{k+1} \dfrac{(-1)^{t+1}C_t^{k+1}}{(k+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\dfrac{1}{(k+1)!}+\sum_{t=0}^{k+1} \dfrac{(-1)^{t+1}C_t^{k+1}}{(k+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\dfrac{1}{(k+1)!}-\dfrac{(1-1)^{k+1}}{(k+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\sum_{t=0}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

Por indução matemática, a suposição é válida.

Assim, obtemos que$f^n(0)=\dfrac{1}{n!}$

Então,$E(length)=\sum_{n=1}^{\infty} Pr(length\geq n)=\sum_{n=1}^{\infty} \dfrac{1}{n!}=e-1$