¿Hay alguna razón fundamental para esperar $e$ que aparezca en esta pregunta de probabilidad?

Question

Me encontré con la siguiente pregunta, cuya respuesta es $e$ . Yo estaba un poco sorprendido, ya que no vi una razón por qué $e$ debería hacer acto de presencia. Así que, formulando la pregunta principal del título de otra manera: ¿debería haber sido posible predecir que al menos mi respuesta debería implicar $e$ de alguna manera no trivial?

Pregunta: Supongamos que se extraen variables aleatorias $x_i \in [0,1]$ donde el $x_i$ se distribuyen uniformemente. Si $x_i > x_{i-1}$ volvemos a desenfundar y, si no, nos detenemos. ¿Cuál es el número esperado de extracciones antes de parar?

Solución: La probabilidad de que tomemos $n$ viene dado por $\frac{n-1}{n!}$ ya que hay $n!$ formas de pedir $x_1,\ldots, x_n$ y exactamente $n-1$ opciones para la colocación de $x_{n-1}$ en el pedido $x_1 < x_1 < \cdots < x_{\widehat{n-1}} < x_n$ . Es decir, para que tome precisamente $n$ sorteos, necesitamos $x_1 < x_2, x_2 < x_3, \ldots, x_{n-2} < x_{n-1}$ pero entonces $x_n < x_{n-1}$ . Así, el valor esperado viene dado por $$ E(\text{number of draws}) = \sum_{n = 2}^\infty \frac{1}{(n-2)!} = \fbox{e} $$

P.D. También es posible que simplemente haya cometido un error, y si es así, por favor indíquelo y podré editar o borrar la pregunta en consecuencia.

Answer 1

Primero: yo tomaría un camino ligeramente distinto, pero eso es cuestión de gustos: Utilice ese $$ E[X]=\sum_{n=0}^\infty nP(X=n)=\sum_{n=0}^\infty P(X> n).$$ Similar a tu razonamiento, $X> n$ ocurre si (hasta igualdades casi imposibles) $x_1<x_2<\ldots <x_n$ que ocurre con probabilidad $\frac 1{n!}$ . Por lo tanto, (de nuevo) $$\tag1 E[X]=\sum_{n=0}^\infty\frac1{n!}=e.$$

Pero respecto a su pregunta principal: ¿Podríamos esperar $e$ a levantar la cabeza? Bueno, tal vez. El problema es sobre el orden aleatorio, por lo tanto sobre las permutaciones, y (con la mano) $e$ aparece muy a menudo en el contexto de las permutaciones, lo que se debe, por supuesto, a que es la suma de los recíprocos de los factoriales. Por otra parte, antes de seguir este pensamiento, ya se ha escrito $(1)$ ...

Answer 2

Voy a dar una forma diferente de enfocar el problema que muestra otra manera de que $e$ pueden surgir.

Como con la respuesta de Hagen von Eitzen, dejemos que $X$ sea la variable aleatoria que representa el número de extracciones.

Consideremos el problema estrechamente relacionado en el que $x_i \in \{1, 2, \ldots, N\}$ en su lugar. Como máximo $N + 1$ en este caso pueden producirse empates. Podemos calcular la expectativa utilizando el teorema binomial.

$$E[X] = \sum_{k=0}^N{P(X > k)} =\sum_{k=0}^{N}\frac{N\choose k}{N^k} = \left(1 + \frac1{N}\right)^N$$

Toma, $N \choose k$ es el número de formas estrictamente crecientes de elegir $x_1, \ldots, x_k$ que luego se divide por el número total de formas de elegirlos para obtener la probabilidad.

Por supuesto entonces, la expectativa se acerca $e$ en el límite como $N \to \infty$ . (No creo que esta sea una forma especialmente buena de resolver el problema, ya que todavía hay que justificar cómo se aplica este límite, pero espero que proporcione alguna idea sobre la aparición de $e$ independientemente).

En cuanto a la pregunta fundamental, realmente no veo una manera de saber que $e$ hasta que haya aparecido más o menos, pero $e$ parece surgir aquí de forma bastante natural, por lo que quizá no debería sorprender tanto en general cuando $e$ surge en un contexto combinatorio.