El juego es la siguiente: comenzar con 1. Si estás en $n$, agregar uno con un % de probabilidad $\frac{1}{n+1}$, de lo contrario reste uno. Terminar el juego si llegar a 0.
¿Cuál es el número esperado de rondas que dura este juego? A través de datos empíricos, han calculado este valor para ser aproximadamente $2e-1$, pero estoy seguro de cómo probar este resultado.
He aquí una solución que utiliza básica de la cadena de Markov de la teoría.
Vamos a hacer que el estado cero, reflejando límite del yo.e, a partir de cero salta a uno con probabilidad uno. Este es ahora un irreductible de la cadena de Markov.
El cálculo directo muestra que $\pi_n={n+1\over 2 e\, n!}$ $n\geq 0$ define el único invariante probabilidad de medida para la cadena. Por lo tanto, por el general de la cadena de Markov la teoría, el número esperado de pasos para volver a cero a partir de cero es $$\mathbb{E}_0(T_0)={1\over \pi_0}= 2e.$$
Por otro lado, el primer paso de análisis de da $$\mathbb{E}_0(T_0)=1+\mathbb{E}_1(T_0),$ $ , de modo que $$\mathbb{E}_1(T_0)=2e-1.$$
(no es una solución aún)
Deje $[n]$ denotar el número esperado de rondas que se requiere para terminar el juego cuando tenemos un valor de $n$.
Por la linealidad de la expectativa, tenemos
$[0] = 0$
$[1] = 1 + \frac{1}{2} [2] + \frac{1}{2} [ 0] $
$[2] = 1 + \frac{1}{3} [ 3] + \frac{2}{3} [ 1]$
$\vdots $
$[n] = 1 + \frac{1}{n+1} [n+1] + \frac{n}{n+1} [n-1]$
Dejando $[1] = \alpha$, podemos calcular que
$\begin{array} {l|l} [1] & \alpha\\ [2] & 2 \alpha - 2 \\ [3] & 4 \alpha - 9 \\ [4] & 10 \alpha - 34 \\ [5] & 34 \alpha - 139 \\ \vdots & \vdots \end{array}$
Deje $[n] = f_n \alpha - g_n $. Entonces, desde el $[n] \geq 0$, esto nos indica que el $\alpha \geq \frac{g_n}{f_n}$.
Reclamo: $f_n, g_n$ crecen muy rápido (para ser cuantificados).
(Creo que tendríamos que averiguar las secuencias.)
Tenemos $f_{n+1} = (n+1) f_n - n f_{n-1}$$g_{n+1} = (n+1) g_n - n g_{n-1}+ (n+1)$.
$f_n$ es A003422, conocida como la izquierda factoriales, y dado por $f_n = \sum_{i=1}^n i!$.
Reclamo: $\frac{g_n}{f_n}$ es un aumento de la secuencia, que está delimitada por encima.
(Ni idea de por qué, pero si podemos resolver la recurrencia, que podría seguir.)
Reclamo: $\alpha = \lim_{n\rightarrow \infty} \frac{g_n}{f_n}$.
Ya tenemos $ \alpha \geq \lim_{n\rightarrow \infty} \frac{g_n}{f_n}$. Si $\alpha > \lim_{n\rightarrow \infty} \frac{g_n}{f_n}$, entonces habremos $[n+1] - [n] > 2 $ grandes $n$, lo que no hace sentido.
Configurar una hoja de Excel para relajarse una distribución asumida. Si $f(n)$ es el tiempo esperado a partir de $n$, la repetición es $f(n)=1+\frac 1{n+1}(nf(n-1)+f(n+1))$. Parece que convergen a $f(1)=2e-1$. Si lo aceptamos, podemos calcular los mayores, que $$\begin {array}{r|l}\\ n&f(n)\\ \hline 0&0\\1&2e-1\\2&4e-4\\3&8e-13\\4&20e-44\\5&68e-173\\6&308e-824\\7&1748e-4737\\8&11828e-32136 \end{array}$$ These fit well with the relaxation. $f 8 $ is within $ 10 ^ {-6} $. Neither $ 2,4,8,20,68 $ nor $1,4,13,44,173 $ is in OEIS. But I don't know how to justify $f 1 $ either. As $n $ gets large, I would expect the value to increase by $1 $ for each step in $n $, as you step downward almost surely. If one solved the recurrence and showed that it converges to $1$ que podría llegar allí.
Esto está lejos de una solución completa - sólo algunos ejemplos numéricos para valores pequeños aquí.
Deje $k$ el número de rondas en las que el juego dura, y deje $P(k = m)$ la probabilidad de que el juego dura $m$ rondas. El valor esperado $E(k)$ del tiempo que el juego dura es
$$E(k) = \displaystyle\sum\limits_{m=1}^{\infty} \left(m \cdot P(k=m)\right) = P(k=1) + 2 \cdot P(k=2) + 3 \cdot P(k=3) + \cdots$$
La probabilidad de que $k$ es cualquier número es $0$, debido a la paridad de $n$ cambios con cada giro.
La probabilidad de que el juego termina en la primera ronda es $$P(k=1) = 1-\frac{1}{2}=\frac{1}{2}$$
Para que el juego final en la tercera ronda, necesitamos un "triunfo" (un paso adelante), seguido por dos de las "pérdidas" (pasos): $$P(k=3) = \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{1}{2}$$
Para que el juego final en la quinta ronda, necesitamos WLWLL o WWLLL (donde W denota un aumento por uno y L denota una disminución por uno): $$P(k=5) = \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{3} \cdot \frac{3}{4} \cdot \frac{2}{3} \cdot \frac{1}{2}$$
En la séptima ronda, tendríamos WWWLLLL, WWLWLLL, WWLLWLL, WLWWLLL, o WLWLWLL. Dada la monotonía de este cálculo, voy a dejar aquí.
No estoy seguro de cómo encontrar una fórmula general para $P(k=m)$ $m$ extraño, y mucho menos encontrar $E(k)$.
Esto está relacionado con el Jugador de la ruina problema y el paseo aleatorio.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
