Acotación aleatoria de 3 valores.

Question

Tengo una matriz de tamaño M, para cada cambio de una variable aleatoria $X_i$ entrar y uno de salida. El $X_i$ r.v. son iid y $X_i = \pm1$ con $p=\frac{1}{2}$. Suponiendo que la suma de los $M$ $X_i$ variables aleatorias se inicia a partir de $0$, ¿cuál es la probabilidad de que después de $n$ cambios ha "redescubierto" $0$?

He tratado de resolver esta considerando la caminata aleatoria $\sum_{i}\varepsilon_i$ donde $\varepsilon_i=\pm2$ con $p=\frac{1}{4}$ e $\varepsilon_i=0$ con $p=\frac{1}{2}$, podría por favor ayudarme? Como un inicio que puedo ignorar que el conjunto es acotado.

Cualquier sugerencia es bien aceptada (si hay una solución que utiliza las funciones de generación es aún mejor, ya que estos son más familiar para mí), gracias a todos.

Answer 1

Primer vistazo a algunos de patrón:

$1$ paso: $1\over 2$

$2$ pasos: $1\over 2$ + $2$(${1\over 4}\times {1\over 4}$)

$3$ pasos: $1\over 2$ + 2(${1\over 4}\times {1\over 4}$) + 2$({1\over 4}\times{1\over 2}\times {1\over 4})$

$4$ pasos: $1\over 2$ + 2(${1\over 4}\times {1\over 4}$) + 2(${1\over 4}\times{1\over 2}\times {1\over 4}) + 2({1\over 4}\times{1\over 2}\times{1\over 2}\times {1\over 4} + {1\over 4}\times{1\over 4}\times{1\over 4}\times {1\over 4})$

Nos damos cuenta de que cada uno de los valores adicionales para $n\geq 2$ pasos consta de $2\times$ (${1\over 4}\times...\times{1\over 4}$) donde $...$ consiste de un número de ${1\over 4}$ y cualquier número de $1\over 2$ multiplicando juntos. Esto es claramente cierto porque una vez que subimos un número con una probabilidad de ${1\over 4}$ tenemos que volver primero antes de llegar a cero. Y el lado negativo es completamente simétrica en el lado positivo, de ahí que los $2\times$. Sin embargo, tenemos que tener en cuenta que el orden de las apariciones de $1\over 2$s y $1\over4$s que realmente le importa lo que el problema se vuelve difícil de usar funciones de generación para resolver que he intentado y no lo ha logrado.

Después de $n$th paso el valor adicional es

$$2({1\over4}\cdot{1\over 4})(\sum_{0\leq 2i \leq n-2}{n-2\choose 2i}({1\over 2})^{n-2i-2}({1\over 4})^{2i})$$

$$={1\over8}(\sum_{0\leq 2i \leq n-2}{n-2\choose 2i}({1\over 2})^{n+2i-2})$$

$$=({1\over2})^{n+1}(\sum_{0\leq 2i \leq n-2}{n-2\choose 2i}({1\over 2})^{2i})$$

En realidad, según Wolfram-Alpha, la suma tiene una forma cerrada de la solución (la cual yo no figura inicialmente)

$$=({1\over2})^{n+1}(({1\over2})^{n-1}(3^{n-2} +1)) =({1\over2})^{2n}(3^{n-2} +1) $$

Para encontrar el total probabilidad después de la $n$ pasos que uno necesita para resumir todos los pasos adicionales de $2$ a $n$ a final y el inicial de la $1\over 2$ con

$${1\over 2}+\sum_{j=2...n}({1\over2})^{2j}(3^{j-2} +1)$$

$$={1\over 2}+\sum_{j=0...n-2}({1\over2})^{2j+4}(3^{j} +1)$$

$$={1\over 2}+\sum_{j=0...n-2}({1\over16}({3\over4})^{j} +{1\over16}({1\over4})^{j})$$

$$={1\over 2}+{1\over16}({1-({3\over4})^{n-1}\over1-{3\over4}}) +{1\over16}({1-({1\over4})^{n-1}\over1-{1\over4}})$$

$$={1\over 2}+{1\over4}(1-({3\over4})^{n-1}) +{1\over12}(1-({1\over4})^{n-1})$$

Answer 2

La solución para el gran $M$ caso único.

El OP modelos de las grandes del $M$ caso con un paseo aleatorio con pasos $\{-2, 0, +2\}$ con probabilidades $\{{1\over 4}, {1\over 2}, {1\over 4}\}$. Este es innecesariamente complicado.

En su lugar, imagina cada turno dividido en 2 timesteps: en Primer lugar un valor es desplazado FUERA de la matriz, entonces el valor se desplaza EN la matriz. Por lo tanto 2 timesteps = 1 turno. Esto puede ser modelado como el (más) básica de paseo aleatorio con pasos $\{-1, +1\}$ con probabilidades $\{{1\over 2}, {1\over 2}\}$, considerando la suma dentro de la matriz. I. e., cambio de un $\pm 1$ es equivalente a mover $\mp 1$, y el cambio EN un $\pm 1$ es equivalente a mover $\pm 1$.

Claramente, con toda la simetría, el OP pregunta se convierte en la primera-volver-a-$0$ en el básico de paseo aleatorio. Volver-a-$0$ sólo puede ocurrir incluso a veces $2k$, que es el mismo que $k$ turnos. Este problema tiene muchas referencias disponibles. Yo no soy un experto, pero una referencia que he encontrado es: https://www.stat.berkeley.edu/~arturof/Docencia/STAT150/Notas/I_First_Return_Probabilities.pdf

Citando desde arriba, prob de la primera vuelta en el tiempo $2m$ (es decir, después de $m$ turnos) es $f_{2m} = {1\over 2m-1} {2m \choose m} 2^{-2m}$. Esto le da el PDF de la primera hora de regreso, y sumando dará la CDF de la primera vuelta el tiempo que el OP quiere. Otras referencias podría tener una fórmula explícita para el CDF. (Como he dicho, no soy un experto).

Por desgracia, esto sólo funciona para las grandes $M$. Para las pequeñas $M$, una vez que cambiar todo el contenido original de la matriz, su cambio futuro-outs son exactamente iguales a su turno-ins $M$ cambios de atrás, y se pierde la independencia de la propiedad. Sin embargo, este método funcionará hasta el momento de cambiar todo el contenido antiguo.