Brain-teaser: ¿Cuál es la duración esperada de una secuencia iid que aumenta monótonamente cuando se extrae de una distribución uniforme [0,1]?

Question

Esta es una pregunta de la entrevista para el analista cuantitativo posición, informó aquí. Supongamos que tenemos el dibujo de un uniforme de $[0,1]$ distribución y los sorteos son iid, ¿cuál es la duración esperada de un monótonamente creciente de distribución? I. e., dejamos de dibujo si la corriente es menor que o igual que el sorteo anterior.

He llegado a los primeros: $$ \Pr(\text{longitud} = 1) = \int_0^1 \int_0^{x_1} \mathrm{d}x_2\, \mathrm{d}x_1 = 1/2 $$ $$ \Pr(\text{longitud} = 2) = \int_0^1 \int_{x_1}^1 \int_0^{x_2} \mathrm{d}x_3 \, \mathrm{d}x_2 \, \mathrm{d}x_1 = 1/3 $$ $$ \Pr(\text{longitud} = 3) = \int_0^1 \int_{x_1}^1 \int_{x_2}^1 \int_0^{x_3} \mathrm{d}x_4\, \mathrm{d}x_3\, \mathrm{d}x_2\, \mathrm{d}x_1 = 1/8 $$

pero me parece que el cálculo de estas anidada integrales cada vez más difícil y no estoy recibiendo el "truco" para generalizar a $$ \Pr(\text{longitud} = n) $$

Sé que la respuesta final está estructurado $$ \mathbb E(\text{longitud de una secuencia progresión}) = \sum_{n=1}^{\infty}n\Pr(\text{longitud} = n) $$

Alguna idea sobre cómo responder a esta pregunta?

Answer 1

Aquí hay algunos consejos generales en la solución de esta pregunta:

Dispone de una secuencia continua de variables aleatorias IID lo que significa que son intercambiables. ¿Qué implica esto acerca de la probabilidad de obtener un determinado orden para el primer $n$ valores? Basado en esto, ¿cuál es la probabilidad de obtener un orden creciente por primera $n$ valores? Es posible que esta cifra fuera sin integrar sobre la distribución de la base de variables aleatorias. Si haces esto bien, usted será capaz de obtener una respuesta sin ningún tipo de suposición de una distribución uniforme - es decir, de obtener una respuesta que se aplica para cualquier intercambiables secuencias de variables aleatorias continuas.

---

Aquí está la solución completa (no se ven si se supone que esta figura fuera de ti mismo):

Deje $U_1, U_2, U_3, \cdots \sim \text{IID Continuous Dist}$ ser su secuencia de variables aleatorias continuas independientes, y deje $N \equiv \max \{ n \in \mathbb{N} | U_1 < U_2 < \cdots < U_n \}$ el número de aumento de los elementos en el inicio de la secuencia. Debido a que estos son continuas intercambiables variables aleatorias, que son casi seguramente desigual para cada uno de los otros, y cualquier pedido es igual de probable, por lo que tenemos: $$\mathbb{P}(N \geqslant n) = \mathbb{P}(U_1 < U_2 < \cdots < U_n) = \frac{1}{n!}.$$ (Note that this result holds for any IID sequence of continuous random variables; they don't have to have a uniform distribution.) So the random variable $N$ has probability mass function $$p_N(n) = \mathbb{P}(N=n) = \frac{1}{n!} - \frac{1}{(n+1)!} = \frac{n}{(n+1)!}.$$ You will notice that this result accords with the values you have calculated using integration over the underlying values. (This part isn't needed for the solution; it is included for completeness.) Using a well-known rule for the expected value of a non-negative random variable, we have: $$\mathbb{E}(N) = \sum_{n=1}^\infty \mathbb{P}(N \geqslant n) = \sum_{n=1}^\infty \frac{1}{n!} = e - 1 = 1.718282.$$ Observe de nuevo que no hay nada en nuestro trabajo que utiliza el subyacente de la distribución uniforme. Por lo tanto, este es un resultado general que se aplica a cualquier intercambiables secuencia de variables aleatorias continuas.

---

Algunas ideas adicionales:

Desde el anterior trabajo podemos observar que la distribución de resultados y resultando el valor esperado no dependen de la distribución subyacente, por lo que es una distribución continua. Esto no es realmente sorprendente, una vez que tenemos en cuenta el hecho de que cada una continua escalar de variable aleatoria puede ser obtenida a través de una transformación monotónica de una variable aleatoria uniforme (con la transformación de su función cuantil). Desde monótona de las transformaciones preservar de rango-orden, mirando las probabilidades de órdenes arbitrarias IID continuo de variables aleatorias es lo mismo que mirar en las probabilidades de órdenes de IID uniforme de variables aleatorias.

Answer 2

Otro método de solución que le brinda la solución para un caso más general.

Supongamos que$F(x)$ es la longitud esperada de una secuencia monotónica$\{x_1, x_2, ...\}$, tal que$x\leq x_1\leq x_2\leq\cdots$. El valor que queremos calcular es$F(0)$. Y sabemos$F(1)=0$. Acondicionamiento en el siguiente valor,

ps

donde$$F(x) = \int_0^x \pi(y)\cdot 0 dy + \int_x^1\pi(y)(1+F(y))dy= \int_x^1 1+F(y) dy$ es la densidad U [0,1]. Asi que

ps

Al resolver con la condición de frontera$\pi(y)=1$, obtenemos$$F'(x)=-(1+F(x))$. Por lo tanto$F(1)=0$.