Pregunta difícil en procesos estocásticos - varianza Martingales

Question

Tengo algún reto difícil de resolver y estoy buscando una pequeña pista/ayuda.

Mi pregunta es la siguiente:

10 ingleses intentan salir de un pub en un clima lluvioso. Ellos lo hacen de la siguiente manera. Inicialmente guardan los 10 paraguas en una cesta junto a la salida del pub. Entran y se beben una pinta cada uno. Luego vuelven a la cesta y cada uno coge un paraguas al azar (permutación aleatoria). Los que han escogido su propio paraguas se marchan disgustados, mientras que los que se han equivocado de paraguas, lo vuelven a colocar en su sitio y regresan al pub para tomar otra pinta de cerveza. Después, vuelven a la cesta y lo intentan una vez más. Y así sucesivamente.

Dejemos que $T$ sea el número de rondas necesarias para que todos los ingleses salgan, y que $N$ sea el número total de ales consumidas durante el procedimiento.
(a) Calcule $E(T)$ .
(b) Calcule $E(N)$ .

Una pista: Para $n = 0, 1, 2, \dots$ , set $X_n$ para ser el número de ingleses en el pub después de $n$ -en la ronda, y considerar $M_n = (X_n + n) 1_{\{n<T\}}.$ Para resolver (b) piensa en las martingalas de varianza.

¿Alguna pista? Además, ¿qué son las martingalas de varianza y cómo ayudan aquí?

Muchas gracias.

Answer 1

Además de las pistas, necesitamos las siguientes identidades relacionadas con derangos :

(1) $\displaystyle\sum_{i=0}^{n}\frac{!i}{i!~(n-i)!}=1,~(n\ge0),$

(2) $\displaystyle\sum_{i=0}^{n}\frac{!i~(n-i)}{i!~(n-i)!}=1,~(n\ge1),$

(3) $\displaystyle\sum_{i=0}^{n}\frac{!i~(n-i)~(n-i-1)}{i!~(n-i)!}=1,~(n\ge2),$

donde he adoptado la notación subfactorial. La prueba de (1) consiste en considerar entre todas las permutaciones posibles de $n$ distintos, cuál es la probabilidad $p^{(n)}_{i}$ es de una permutación aleatoria en la que exactamente $n-i$ los elementos están en sus posiciones originales ordenadas. Es fácil ver $p^{(n)}_{i}$ es exactamente el término dentro de la suma. Para (2), obsérvese que podemos cambiar el límite superior del sumatorio por $n-1$ , anular el $n-i$ término en el numerador con el factorial en el denominador y luego aplicar (1) sustituyendo $n$ con $n-1$ . Prueba similar para (3). Ahora podemos reescribir estas identidades como

(1') $\sum_{i=0}^{n}p^{(n)}_{i}=1,~(n\ge0),$

(2') $\sum_{i=0}^{n}p^{(n)}_{i}i=n-1,~(n\ge1),$

(3') $\sum_{i=0}^{n}p^{(n)}_{i}i^2=(n-1)^2+1,~(n\ge2),$

donde hemos utilizado (1) y (2) para obtener (2') y (1), (2) y (3) para obtener (3').

(a) Siguiendo sus indicaciones, utilizamos el análisis de primer paso en $X_n$ :

$\mathbb{E}\left[X_{n+1}\mid X_n\right]=\sum_{i=0}^{X_n}p^{(X_n)}_{i}i=X_n-1,$

donde $n<T$ es decir, $X_n>=2$ . Por lo tanto, $(X_n+n)1_{n<T}$ es una martingala y aplicando la teorema de parada opcional obtenemos $\mathbb{E}[T]=X_0=10$ , como $X_T=0$ es la condición de parada.

(b) Creo que la pista es considerar la varianza de $X_n$ . Aplicamos el análisis de primer paso en $X^2_n$ :

$\mathbb{E}\left[X^2_{n+1}\mid X_n\right]=\sum_{i=0}^{X_n}p^{(X_n)}_{i}i^2=(X_n-1)^2+1.$

También tenemos

$\mathbb{E}\left[Y_{n+1}\mid Y_n,X_n\right]=Y_n+X_n,$

donde $Y_n$ es el número total de cervezas consumidas después de $n$ La tercera ronda. Por lo tanto, $(Y_n+X^2_n/2+X_n)1_{n<T}$ es una martingala y $\mathbb{E}[N]=\mathbb{E}[Y_T]=X^2_0/2+X_0=60$ .