12.1: Paseos Aleatorios en Espacio Euclide**

Última actualización
Guardar como PDF

Page ID: 150196

Charles M. Grinstead & J. Laurie Snell
Swarthmore College and Dartmouth College via American Mathematical Society

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

En los últimos capítulos, hemos estudiado sumas de variables aleatorias con el objetivo de describir las funciones de distribución y densidad de la suma. En este capítulo, veremos las sumas de variables aleatorias discretas desde una perspectiva diferente. Nos ocuparemos de las propiedades que pueden asociarse con la secuencia de sumas parciales, como el número de cambios de signo de esta secuencia, el número de términos en la secuencia que equivalen a 0, y el tamaño esperado del término máximo en la secuencia.

Comenzamos con la siguiente definición.

Let$\{X_k\}_{k = 1}^\infty$ Ser una secuencia de variables aleatorias discretas independientes, distribuidas idénticamente. Para cada entero positivo$n$, dejamos$S_n$ denotar la suma$X_1 + X_2 + \cdots + X_n$. La secuencia$\{S_n\}_{n = 1}^\infty$ se llama un Si el rango común de los$X_k$'s es${\mathbf R}^m$, entonces decimos que$\{S_n\}$ es un paseo al azar en${\mathbf R}^m$.

Consideramos que la secuencia de$X_k$'s es el resultado de experimentos independientes. Dado que los$X_k$'s son independientes, la probabilidad de cualquier secuencia particular (finita) de resultados se puede obtener multiplicando las probabilidades que cada uno$X_k$ toma en el valor especificado en la secuencia. Por supuesto, estas probabilidades individuales vienen dadas por la distribución común de los$X_k$'s. Normalmente estaremos interesados en encontrar probabilidades de eventos que involucren la secuencia relacionada de$S_n$'s. Tales eventos pueden describirse en términos de los$X_k$'s, por lo que sus probabilidades pueden ser calculado utilizando la idea anterior.

Hay varias formas de visualizar una caminata aleatoria. Uno puede imaginar que una partícula se coloca en el origen en${\mathbf R}^m$ en el tiempo$n = 0$. La suma$S_n$ representa la posición de la partícula al final de los$n$ segundos. Así, en el intervalo de tiempo$[n-1, n]$, la partícula se mueve (o salta) de la posición$S_{n-1}$ a$S_{n}$. El vector que representa este movimiento es justo$S_n - S_{n-1}$, que es igual$X_n$. Esto quiere decir que en una caminata aleatoria, los saltos son independientes e idénticos distribuidos. Si$m = 1$, por ejemplo, entonces uno puede imaginar una partícula en la línea real que comienza en el origen, y al final de cada segundo, salta una unidad a la derecha o a la izquierda, con probabilidades dadas por la distribución$X_k$ de los s. si$m = 2$, uno puede visualizar el proceso como teniendo lugar en una ciudad en la que las calles forman cuadras cuadradas de la ciudad. Una persona comienza en una esquina (es decir, en una intersección de dos calles) y va en una de las cuatro direcciones posibles según la distribución de los$X_k$ s. si$m = 3$, uno podría imaginar estar en un gimnasio de la jungla, donde uno es libre de moverse en cualquiera de las seis direcciones (izquierda, derecha, adelante, hacia atrás, arriba y abajo). Una vez más, las probabilidades de estos movimientos vienen dadas por la distribución de los$X_k$'s.

Otro modelo de una caminata aleatoria (utilizada principalmente en el caso donde se encuentra el rango${\mathbf R}^1$) es un juego, que involucra a dos personas, que consiste en una secuencia de movimientos independientes, distribuidos idénticamente. La suma$S_n$ representa la puntuación de la primera persona, digamos, después de$n$ movimientos, con el supuesto de que la puntuación de la segunda persona es$-S_n$. Por ejemplo, dos personas podrían estar volteando monedas, con un partido o no partido representando$+1$ o$-1$, respectivamente, para el primer jugador. O, tal vez se está volteando una moneda, con una cabeza o cola representando$+1$ o$-1$, respectivamente, para el primer jugador.

Caminatas aleatorias en la línea real

Primero consideraremos el caso no trivial más simple de una caminata aleatoria${\mathbf R}^1$, es decir, el caso en el que la función de distribución común de las variables aleatorias$X_n$ viene dada por\[f_X(x) = \left \{ \begin{array}{ll} 1/2, & \mbox{if $x = \pm 1,$} \\ 0, & \mbox{otherwise.} \end{array} \right.\] Esta situación corresponde a que una moneda justa sea volteada, con$S_n$ representar el número de cabezas menos el número de colas que se producen en los primeros$n$ volteos. Observamos que en esta situación, todos los caminos de longitud$n$ tienen la misma probabilidad, es decir$2^{-n}$.

A veces es instructivo representar una caminata aleatoria como una línea poligonal, o camino, en el plano, donde el eje horizontal representa el tiempo y el eje vertical representa el valor de$S_n$. Dada una secuencia$\{S_n\}$ de sumas parciales, primero trazamos los puntos$(n, S_n)$, y luego para cada uno$k < n$, conectamos$(k, S_k)$ y$(k+1, S_{k+1})$ con un segmento de línea recta. El de un camino es solo la diferencia en los valores de tiempo de los puntos inicial y final en el camino. Se hace referencia al lector a la Figura [fig 12.1]. Esta figura, y el proceso que ilustra, son idénticos al ejemplo, dado en el Capítulo 1, de dos personas jugando cabeza o cola.

Devoluciones y primeras devoluciones

Decimos que ha ocurrido una, o hay una a la vez$n$, si$S_n = 0$. Observamos que esto solo puede ocurrir si$n$ es un entero par. Para calcular la probabilidad de una ecualización en el momento$2m$, solo necesitamos contar el número de caminos de longitud$2m$ que comienzan y terminan en el origen. El número de tales caminos es claramente\[{2m \choose m}\ .\] Dado que cada camino tiene probabilidad$2^{-2m}$, tenemos el siguiente teorema.

[thm 12.1.1] La probabilidad de un retorno al origen en el tiempo$2m$ viene dada por\[u_{2m} = {2m \choose m}2^{-2m}\ .\] La probabilidad de un retorno al origen en un momento impar es 0.

Se dice que una caminata aleatoria tiene una al origen en el momento$2m$ si$m > 0$, y$S_{2k} \ne 0$ para todos$k < m$. En la Figura [fig 12.1], el primer retorno ocurre en el tiempo 2. $f_{2m}$Definimos como la probabilidad de este evento. (También definimos$f_0 = 0$.) Se puede pensar en la expresión$f_{2m}2^{2m}$ como el número de caminos de longitud$2m$ entre los puntos$(0, 0)$ y$(2m, 0)$ que no tocan el eje horizontal excepto en los puntos finales. Usando esta idea, es fácil probar el siguiente teorema.

[thm 12.1.2] Para$n \ge 1$, las probabilidades$\{u_{2k}\}$ y$\{f_{2k}\}$ están relacionadas por la ecuación\[u_{2n} = f_0 u_{2n} + f_2 u_{2n-2} + \cdots + f_{2n}u_0\ .\] Hay$u_{2n}2^{2n}$ caminos de longitud$2n$ que tienen puntos finales$(0, 0)$ y$(2n, 0)$. La colección de tales rutas se puede dividir en$n$ conjuntos, dependiendo del momento del primer retorno al origen. Una trayectoria en esta colección que tiene un primer retorno al origen en el momento$2k$ consiste en un segmento inicial de$(0, 0)$ a$(2k, 0)$, en el que no hay puntos interiores en el eje horizontal, y un segmento terminal de$(2k, 0)$ a$(2n, 0)$, sin más restricciones sobre este segmento. Así, el número de caminos en la colección que tienen un primer retorno al origen en el momento$2k$ viene dado por\[f_{2k}2^{2k}u_{2n-2k}2^{2n-2k} = f_{2k}u_{2n-2k}2^{2n}\ .\] Si sumamos más$k$, obtenemos la ecuación\[u_{2n}2^{2n} = f_0u_{2n} 2^{2n} + f_2u_{2n-2}2^{2n} + \cdots + f_{2n}u_0 2^{2n}\ .\] Dividiendo ambos lados de esta ecuación por$2^{2n}$ completa la prueba.

La expresión en el lado derecho del teorema anterior debería recordar al lector una suma que apareció en Definición [defn 7.1] de la convolución de dos distribuciones. La convolución de dos secuencias se define de manera similar. El teorema anterior dice que la secuencia$\{u_{2n}\}$ es la convolución de sí misma y de la secuencia$\{f_{2n}\}$. Así, si representamos cada una de estas secuencias mediante una función generadora ordinaria, entonces podemos usar la relación anterior para determinar el valor$f_{2n}$.

[thm 12.1.3] Para$m \ge 1$, la probabilidad de un primer retorno al origen en el momento$2m$ viene dada por\[f_{2m} =

ParseError: colon expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[2]/p[6]/span[4]/span[1], line 1, column 5

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[2]/p[6]/span[4]/span[2], line 1, column 2

\ .\] Comenzamos definiendo las funciones generadoras\[U(x) = \sum_{m = 0}^\infty u_{2m}x^m\] y el\[F(x) = \sum_{m = 0}^\infty f_{2m}x^m\ .\] Teorema [thm 12.1.2] dice que\[U(x) = 1 + U(x)F(x)\ . \label{eq 12.1.1}\] (La presencia del 1 en el lado derecho se debe a la hecho que$u_0$ se define como 1, pero el Teorema [thm 12.1.2] sólo se mantiene para$m \ge 1$.) Observamos que ambas funciones generadoras ciertamente convergen en el intervalo$(-1, 1)$, ya que todos los coeficientes son como máximo 1 en valor absoluto. Así, podemos resolver la ecuación anterior para$F(x)$, obteniendo\[F(x) =

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[2]/p[6]/span[12]/span, line 1, column 9

\ .\] Ahora, si podemos encontrar una expresión de forma cerrada para la función$U(x)$, también tendremos una expresión de forma cerrada para$F(x)$. Del Teorema [thm 12.1.1], tenemos\[U(x) = \sum_{m = 0}^\infty {2m \choose m}2^{-2m}x^m\ .\] En Wilf, ¹ encontramos que\[{1\over{\sqrt {1 - 4x}}} = \sum_{m = 0}^\infty {2m \choose m} x^m\ .\] Al lector se le pide probar esta afirmación en Ejercicio [exer 12.1.1]. Si reemplazamos$x$ por$x/4$ en la última ecuación, vemos que\[U(x) = {1\over{\sqrt {1-x}}}\ .\] Por lo tanto, tenemos\[\begin{aligned} F(x) &=&

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[2]/p[6]/span[20]/span[1], line 1, column 9

\\ &=&

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[2]/p[6]/span[20]/span[2], line 1, column 6

\\ &=& 1 - (1-x)^{1/2}\ . \end{aligned}\]

Si bien es posible calcular el valor de$f_{2m}$ usar el Teorema Binomial, es más fácil anotarlo$F'(x) = U(x)/2$, de manera que los coeficientes se$f_{2m}$ pueden encontrar integrando la serie para$U(x)$. Obtenemos, para$m \ge 1$,

\[\begin{aligned} f_{2m} &=& {u_{2m-2}\over{2m}}\\ &=& {2m-2 \choose m-1}\over{m2^{2m-1}}\\ &=& {2m \choose m}\over{(2m-1)2^{2m}}\\ &=& {u_{2m}\over{2m-1}}\ ,\end{aligned}\]

ya que\[{2m-2 \choose m-1} = {m\over{2(2m-1)}}{2m\choose m}\ .\] Esto completa la prueba del teorema.

Probabilidad de retorno eventual

En el proceso de caminata aleatoria simétrica en${\mathbf R}^m$, ¿cuál es la probabilidad de que la partícula finalmente regrese al origen? Primero examinamos esta cuestión en el caso que$m = 1$, y luego consideramos el caso general. Los resultados en los siguientes dos ejemplos se deben a Pólya. ²

[examen 12.1.0.5] (Eventual Return in${\mathbf R}^1$) Uno tiene que abordar la idea de retorno eventual con cierto cuidado, ya que el espacio muestral parece ser el conjunto de todos los paseos de longitud infinita, y este conjunto no es denumerable. Para evitar dificultades,$w_n$ definiremos como la probabilidad de que se haya producido un primer retorno a más tardar en el tiempo$n$. Así,$w_n$ se refiere al espacio muestral de todos los recorridos de longitud$n$, que es un conjunto finito. En términos de los$w_n$'s, es razonable definir la probabilidad de que la partícula finalmente regrese al origen para ser\[w_* = \lim_{n \rightarrow \infty} w_n\ .\] Este límite claramente existe y es como mucho uno, ya que la secuencia$\{w_n\}_{n = 1}^\infty$ es una secuencia creciente, y todos sus términos son a lo sumo uno.

En cuanto a$f_n$ las probabilidades, vemos que\[w_{2n} = \sum_{i = 1}^n f_{2i}\ .\] Así,\[w_* = \sum_{i = 1}^\infty f_{2i}\ .\] en la prueba del Teorema [thm 12.1.3],\[F(x) = \sum_{m = 0}^\infty f_{2m}x^m\] se introdujo la función generadora. Ahí se señaló que esta serie converge para$x \in (-1, 1)$. De hecho, es posible demostrar que esta serie también converge para$x = \pm 1$ mediante el uso de Ejercicio [exer 12.1.4], junto con el hecho de que\[f_{2m} =

ParseError: colon expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[3]/p[3]/span[7]/span, line 1, column 5

\ .\] (Este hecho fue probado en la prueba del Teorema [thm 12.1.3].) Ya que también sabemos que\[F(x) = 1 - (1-x)^{1/2}\ ,\] vemos que\[w_* = F(1) = 1\ .\] Así, con probabilidad uno, la partícula vuelve al origen.

Una prueba alternativa del hecho que se$w_* = 1$ puede obtener utilizando los resultados del Ejercicio [exer 12.1.2].

[examen 12.1.0.6] (Eventual Retorno en${\mathbf R}^m$) Ahora volvemos nuestra atención al caso de que la caminata aleatoria se lleva a cabo en más de una dimensión. Definimos$f^{(m)}_{2n}$ que es la probabilidad de que el primer retorno al origen en${\mathbf R}^m$ ocurra en el momento$2n$. La cantidad$u^{(m)}_{2n}$ se define de manera similar. Así,$f^{(1)}_{2n}$ e$u^{(1)}_{2n}$ igual$f_{2n}$ y$u_{2n}$, que se definieron anteriormente. Si, además, definimos$u^{(m)}_0 = 1$ y$f^{(m)}_0 = 0$, entonces uno puede imitar la prueba del Teorema [thm 12.1.2], y mostrar que para todos$m \ge 1$,\[u^{(m)}_{2n} = f^{(m)}_0 u^{(m)}_{2n} + f^{(m)}_2 u^{(m)}_{2n-2} + \cdots + f^{(m)}_{2n}u^{(m)}_0\ . \label{eq 12.1.1.5}\]

Seguimos generalizando trabajos previos definiendo\[U^{(m)}(x) = \sum_{n = 0}^\infty u^{(m)}_{2n} x^n\] y\[F^{(m)}(x) = \sum_{n = 0}^\infty f^{(m)}_{2n} x^n\ .\] Entonces, mediante el uso de la Ecuación [eq 12.1.1.5], vemos que\[U^{(m)}(x) = 1 + U^{(m)}(x) F^{(m)}(x)\ ,\] como antes. Estas funciones siempre convergerán en el intervalo$(-1, 1)$, ya que todos sus coeficientes son como mucho uno en magnitud. De hecho, ya que\[w^{(m)}_* = \sum_{n = 0}^\infty f^{(m)}_{2n} \le 1\] para todos$m$, la serie para$F^{(m)}(x)$ converge en$x = 1$ también, y$F^{(m)}(x)$ es izquierda-continua en$x = 1$, es decir,\[\lim_{x \uparrow 1} F^{(m)}(x) = F^{(m)}(1)\ .\] Así, tenemos\[w^{(m)}_* = \lim_{x \uparrow 1} F^{(m)}(x) = \lim_{x \uparrow 1} \frac{U^{(m)}(x) - 1}{U^{(m)}(x)}\ , \label{eq 12.1.1.6}\] así que determinar$w^{(m)}_*$, basta con determinar\[\lim_{x \uparrow 1} U^{(m)}(x)\ .\] Dejamos$u^{(m)}$ denotar este límite.

Afirmamos que\[u^{(m)} = \sum_{n = 0}^\infty u^{(m)}_{2n}\ .\] (Esta afirmación es razonable; dice que para averiguar qué pasa con la función$U^{(m)}(x)$ en$x = 1$, solo deja entrar$x = 1$ la serie power para$U^{(m)}(x)$.) Para probar la afirmación, observamos que los coeficientes$u^{(m)}_{2n}$ son no negativos, por lo que$U^{(m)}(x)$ aumenta monótonamente en el intervalo$[0, 1)$. Así, para cada uno$K$, tenemos\[\sum_{n = 0}^K u^{(m)}_{2n} \le \lim_{x \uparrow 1} U^{(m)}(x) = u^{(m)} \le \sum_{n = 0}^\infty u^{(m)}_{2n}\ .\] Al dejar$K \rightarrow \infty$, vemos que\[u^{(m)} = \sum_{2n}^\infty u^{(m)}_{2n}\ .\] Esto establece el reclamo.

De la Ecuación [eq 12.1.1.6], vemos que si$u^{(m)} < \infty$, entonces la probabilidad de un retorno eventual es\[\frac {u^{(m)} - 1}{u^{(m)}}\ ,\] while if$u^{(m)} = \infty$, entonces la probabilidad de retorno eventual es 1.

Para completar el ejemplo, debemos estimar la suma\[\sum_{n = 0}^\infty u^{(m)}_{2n}\ .\] En Ejercicio [exer 12.1.12], se pide al lector que demuestre que\[u^{(2)}_{2n} = \frac 1 {4^{2n}} {{2n}\choose n}^2\ .\] Usando la Fórmula de Stirling, es fácil demostrar que (ver Ejercicio [exer 12.1.13])\[

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[3]/p[9]/span[3]/span, line 1, column 2

{\sqrt {\pi n}}\ ,\] así\[u^{(2)}_{2n} \sim \frac 1{\pi n}\ .\] De esto se deduce fácilmente que\[\sum_{n = 0}^\infty u^{(2)}_{2n}\] diverge, entonces$w^{(2)}_* = 1$, es decir, en${\mathbf R}^2$, la probabilidad de un eventual retorno es 1.

Cuando$m = 3$, Ejercicio [exer 12.1.12] muestra que\[u^{(3)}_{2n} = \frac 1{2^{2n}}{{2n}\choose n} \sum_{j,k} \biggl(\frac 1{3^n}\frac{n!}{j!k!(n-j-k)!}\biggr)^2\ .\] Let$M$ denota el mayor valor de\[\frac 1{3^n}\frac {n!}{j!k!(n - j - k)!}\ ,\] sobre todos los valores no negativos de$j$ y$k$ con$j + k \le n$. Es fácil, usando la Fórmula de Stirling, demostrar eso\[M \sim \frac cn\ ,\] por alguna constante$c$. Así, tenemos\[u^{(3)}_{2n} \le \frac 1{2^{2n}}{{2n}\choose n} \sum_{j,k} \biggl(\frac M{3^n}\frac{n!}{j!k!(n-j-k)!}\biggr)\ .\] Usando Ejercicio [exer 12.1.14], se puede demostrar que la expresión de la derecha es como mucho\[\frac {c'}{n^{3/2}}\ ,\] donde$c'$ está una constante. Así,\[\sum_{n = 0}^\infty u^{(3)}_{2n}\] converge, así$w^{(3)}_*$ es estrictamente menos de uno. Esto quiere decir que en${\mathbf R}^3$, la probabilidad de un eventual retorno al origen es estrictamente menor a uno (de hecho, es aproximadamente .34).

Se pueden resumir estos resultados afirmando que no se debe emborrachar en más de dos dimensiones.

Número esperado de ecualizaciones

Damos ahora otro ejemplo del uso de funciones generadoras para encontrar una fórmula general para términos en una secuencia, donde la secuencia se relaciona por relaciones de recursión con otras secuencias. Ejercicio [exer 12.1.9] da otro ejemplo más.

(Número esperado de ecualizaciones) [examen 12.1.1] En este ejemplo, derivaremos una fórmula para el número esperado de ecualizaciones en una caminata aleatoria de longitud$2m$. Al igual que en la prueba del Teorema [thm 12.1.3], el método tiene cuatro partes principales. Primero, se encuentra una recursión que relaciona el término$m$ th en la secuencia desconocida con términos anteriores en la misma secuencia y con términos en otras secuencias (conocidas). Un ejemplo de tal recursión se da en Teorema [thm 12.1.2]. Segundo, la recursión se utiliza para derivar una ecuación funcional que involucra las funciones generadoras de la secuencia desconocida y una o más secuencias conocidas. La ecuación [eq 12.1.1] es un ejemplo de tal ecuación funcional. En tercer lugar, se resuelve la ecuación funcional para la función generadora desconocida. Por último, usando un dispositivo como el Teorema Binomial, integración o diferenciación, se encuentra una fórmula para el coeficiente$m$ th de la función generadora desconocida.

Comenzamos$g_{2m}$ definiendo como el número de ecualizaciones entre todas las caminatas aleatorias de longitud$2m$. (Por cada caminata aleatoria, ignoramos la ecualización en el tiempo 0.) Nosotros definimos$g_0 = 0$. Dado que el número de caminatas de longitud$2m$ es igual$2^{2m}$, el número esperado de ecualizaciones entre todas esas caminatas aleatorias es$g_{2m}/2^{2m}$. A continuación, definimos la función generadora$G(x)$:\[G(x) = \sum_{k = 0}^\infty g_{2k}x^k\ .\] Ahora necesitamos encontrar una recursión que$\{g_{2k}\}$ relacione la secuencia con una o ambas secuencias conocidas$\{f_{2k}\}$ y$\{u_{2k}\}$. $m$Consideramos que es un entero positivo fijo, y consideramos el conjunto de todos los caminos de longitud$2m$ como la unión disjunta\[E_2 \cup E_4 \cup \cdots \cup E_{2m} \cup H\ ,\] donde$E_{2k}$ está el conjunto de todos los caminos de longitud$2m$ con la primera ecualización en el momento$2k$, y$H$ es el conjunto de todos los caminos de longitud $2m$sin igualación. Es fácil mostrar (ver Ejercicio [exer 12.1.3]) que\[|E_{2k}| = f_{2k} 2^{2m}\ .\] Afirmamos que el número de ecualizaciones entre todos los caminos que pertenecen al conjunto$E_{2k}$ es igual a\[|E_{2k}| + 2^{2k} f_{2k} g_{2m - 2k}\ . \label{eq 12.1.2}\] Cada camino en$E_{2k}$ tiene una ecualización a la vez$2k$, por lo que el número total de tales ecualizaciones es justo$|E_{2k}|$ . Esta es la primera suma en la ecuación de expresión [eq 12.1.2]. Hay$2^{2k} f_{2k}$ diferentes segmentos iniciales de longitud$2k$ entre los caminos en$E_{2k}$. Cada uno de estos segmentos iniciales se puede aumentar a una trayectoria de longitud de$2m$$2^{2m-2k}$ maneras, al colindar todas las trayectorias posibles de longitud$2m - 2k$. El número de ecualizaciones obtenidas al unir todas estas trayectorias a cualquier segmento inicial es$g_{2m - 2k}$, por definición. Esto da la segunda suma en la Ecuación [eq 12.1.2]. Dado que$k$ puede variar de 1 a$m$, obtenemos la recursión\[g_{2m} = \sum_{k = 1}^m \Bigl(|E_{2k}| + 2^{2k}f_{2k}g_{2m - 2k}\Bigr)\ . \label{eq 12.1.3}\]

El segundo summand en el término típico anterior debería recordar al lector una convolución. De hecho, si multiplicamos la función generadora$G(x)$ por la función generadora\[F(4x) = \sum_{k = 0}^\infty 2^{2k}f_{2k} x^k\ ,\] el coeficiente de$x^m$ iguales\[\sum_{k = 0}^m 2^{2k}f_{2k}g_{2m-2k}\ .\] Así, el producto$G(x)F(4x)$ es parte de la ecuación funcional que estamos buscando. El primer summand en el término típico en la Ecuación [eq 12.1.3] da lugar a la suma\[2^{2m}\sum_{k = 1}^m f_{2k}\ .\] De Ejercicio [exer 12.1.2], vemos que esta suma es justa$(1 - u_{2m})2^{2m}$. Así, necesitamos crear una función generadora cuyo coeficiente$m$ th sea este término; esta función generadora es\[\sum_{m = 0}^\infty (1- u_{2m})2^{2m} x^m\ ,\] o\[\sum_{m = 0}^\infty 2^{2m} x^m - \sum_{m = 0}^\infty u_{2m}2^{2m} x^m\ .\] La primera suma es justa$(1-4x)^{-1}$, y la segunda suma es$U(4x)$. Entonces, la ecuación funcional que hemos estado buscando es\[G(x) = F(4x)G(x) + {1\over{1-4x}} - U(4x)\ .\] Si resolvemos esta recursión para$G(x)$, y simplificamos, obtenemos\[G(x) = {1\over{(1-4x)^{3/2}}} - {1\over{(1-4x)}}\ . \label{eq 12.1.4}\]

Ahora necesitamos encontrar una fórmula para el coeficiente de$x^m$. La primera suma en la Ecuación [eq 12.1.4] es$(1/2)U'(4x)$, por lo que el coeficiente de$x^m$ en esta función es\[u_{2m+2} 2^{2m+1}(m+1)\ .\] La segunda suma en la Ecuación [eq 12.1.4] es la suma de una serie geométrica con relación común$4x$, por lo que el coeficiente de$x^m$ es$2^{2m}$. Por lo tanto, obtenemos

\[\begin{aligned} g_{2m} &=& u_{2m+2}2^{2m+1}(m+1) - 2^{2m}\\ &=& {1\over 2}

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[4]/p[6]/span/span, line 1, column 2

(m+1) - 2^{2m}\ .\end{aligned}\]

Recordamos que el cociente$g_{2m}/2^{2m}$ es el número esperado de igualaciones entre todas las trayectorias de longitud$2m$. Usando Ejercicio [exer 12.1.4], es fácil demostrar que\[

ParseError: colon expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[4]/p[7]/span[3]/span, line 1, column 5

\sim \sqrt{2\over \pi}\sqrt {2m}\ .\] En particular, esto significa que el número promedio de ecualizaciones entre todas las trayectorias de longitud no$4m$ es el doble del número promedio de ecualizaciones entre todas las trayectorias de longitud$2m$. Para que el número promedio de ecualizaciones se duplique, se deben cuadruplicar las longitudes de las caminatas aleatorias.

Es interesante señalar que si definimos\[M_n = \max_{0 \le k \le n} S_k\ ,\] entonces tenemos\[E(M_n) \sim \sqrt{2\over \pi}\sqrt n\ .\] Esto significa que el número esperado de ecualizaciones y el valor máximo esperado para caminatas aleatorias de longitud$n$ son asintóticamente iguales como$n \rightarrow \infty$. (De hecho, se puede demostrar que los dos valores esperados difieren como mucho$1/2$ para todos los enteros positivos$n$. Ver Ejercicio [exer 12.1.9].)

i [exer 12.1.1] Utilizando el Teorema Binomial, mostrar que\[{1\over{\sqrt {1 - 4x}}} = \sum_{m = 0}^\infty {2m \choose m} x^m\ .\] ¿Cuál es el intervalo de convergencia de esta serie de potencias?

i [exer 12.1.2]

Demostrar que para$m \ge 1$,\[f_{2m} = u_{2m-2} - u_{2m}\ .\]
Usando la parte (a), busca una expresión de forma cerrada para la suma\[f_2 + f_4 + \cdots + f_{2m}\ .\]
Utilizando la parte (b), demostrar que\[\sum_{m = 1}^\infty f_{2m} = 1\ .\] (También se puede obtener esta afirmación del hecho de que\[F(x) = 1 - (1-x)^{1/2}\ .)\]
Usando las partes (a) y (b), muestran que la probabilidad de no igualación en los primeros$2m$ resultados es igual a la probabilidad de una ecualización en el momento$2m$.

i [exer 12.1.3] Usando la notación de Ejemplo [examen 12.1.1], mostrar que\[|E_{2k}| = f_{2k} 2^{2m}\ .\]

i [exer 12.1.4] Usando la Fórmula de Stirling, demostrar que\[u_{2m} \sim {1\over{\sqrt {\pi m}}}\ .\]

i [exer 12.1.5] A en una caminata aleatoria ocurre en el momento$2k$ si$S_{2k-1}$ y$S_{2k+1}$ son de signo opuesto.

Dar un argumento riguroso que demuestre que entre todos los ámbitos de longitud$2m$ que tienen una ecualización en el momento$2k$, exactamente la mitad tienen un cambio de plomo a la vez$2k$.
Deducir que el número total de cambios de plomo entre todos los pasos de longitud$2m$ es igual\[{1\over 2}(g_{2m} - u_{2m})\ .\]
Encontrar una expresión asintótica para el número promedio de cambios de plomo en una caminata aleatoria de longitud$2m$.

i [exer 12.1.6]

Mostrar que la probabilidad de que una caminata aleatoria de longitud$2m$ tenga un último retorno al origen en el tiempo$2k$, donde$0 \le k \le m$, es igual
\[
ParseError: colon expected (click for details)
```
Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[4]/ol[3]/li[1]/span[4]/span, line 1, column 3
```
= u_{2k}u_{2m - 2k}\ .\]
(El caso$k = 0$ consiste en todos los caminos que no regresan al origen en ningún momento positivo.): Un camino cuyo último retorno al origen ocurre en el momento $2k$consta de dos caminos pegados entre sí, uno de los cuales es de longitud$2k$ y que comienza y termina en el origen, y el otro camino del cual es de longitud$2m - 2k$ y que comienza en el origen pero nunca regresa al origen. Ambos tipos de rutas se pueden contar utilizando las cantidades que aparecen en esta sección.
Usando la parte (a), mostrar que si$m$ es impar, la probabilidad de que un paseo de longitud no$2m$ tenga ecualización en los últimos$m$ resultados es igual a$1/2$, independientemente del valor de$m$.: La respuesta a la parte a) es simétrica en$k$ y$m-k$.

i [exer 12.1.7] Mostrar que la probabilidad de no igualación en una caminata de longitud$2m$ es igual$u_{2m}$.

[exer 12.1.8] Mostrar que\[P(S_1 \ge 0,\ S_2 \ge 0,\ \ldots,\ S_{2m} \ge 0) = u_{2m}\ .\]: Primero explica por qué\[\begin{aligned} &&P(S_1 > 0,\ S_2 > 0,\ \ldots,\ S_{2m} > 0) \\ && \;\;\;\;\;\;\;\;\;\;\;\;\; = {1\over 2}P(S_1 \ne 0,\ S_2 \ne 0,\ \ldots,\ S_{2m} \ne 0) \ .\end{aligned}\] Luego usa Ejercicio [exer 12.1.7], junto con la observación de que si no se produce ecualización en los primeros$2m$ resultados, entonces el camino pasa por el punto$(1,1)$ y permanece sobre o por encima de la línea horizontal $x = 1$.

[exer 12.1.9] En Feller, ³ uno encuentra el siguiente teorema: Let$M_n$ be the random variable que da el valor máximo de$S_k$, for$1 \le k \le n$. Definir\[p_{n, r} = {n\choose

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[4]/p[17]/span[5]/span, line 1, column 4

}2^{-n}\ .\] Si$r \ge 0$, entonces\[P(M_n = r) = \left \{ \begin{array}{ll} p_{n, r}\,,&\mbox{if $r \equiv n\, (\mbox{mod}\ 2)$}, \\ p_{n, r+1}\,,&\mbox{if $r \not\equiv n\,(\mbox{mod}\ 2)$}. \end{array} \right.\]

Usando este teorema, muestra eso\[E(M_{2m}) = {1\over{2^{2m}}}\sum_{k = 1}^m (4k-1){2m \choose m+k}\ ,\] y si$n = 2m+1$, entonces\[E(M_{2m+1}) = {1\over {2^{2m+1}}} \sum_{k = 0}^m (4k+1){2m+1\choose m+k+1}\ .\]
Para$m \ge 1$, definir\[r_m = \sum_{k = 1}^m k {2m\choose m+k}\] y\[s_m = \sum_{k = 1}^m k {2m+1\choose m+k+1}\ .\] Mediante el uso de la identidad\[{n\choose k} = {n-1\choose k-1} + {n-1\choose k}\ ,\] mostrar eso\[s_m = 2r_m - {1\over 2}\biggl(2^{2m} - {2m \choose m}\biggr)\] y\[r_m = 2s_{m-1} + {1\over 2}2^{2m-1}\ ,\] si$m \ge 2$.
Definir las funciones generadoras\[R(x) = \sum_{k = 1}^\infty r_k x^k\] y\[S(x) = \sum_{k = 1}^\infty s_k x^k\ .\] Mostrar eso\[S(x) = 2 R(x) - {1\over 2}\biggl({1\over{1- 4x}}\biggr) + {1\over 2}\biggl(\sqrt{1-4x}\biggr)\] y\[R(x) = 2xS(x) + x\biggl({1\over{1-4x}}\biggr)\ .\]
Demuestre eso\[R(x) = {x\over{(1-4x)^{3/2}}}\ ,\] y\[S(x) = {1\over 2}\biggl({1\over{(1- 4x)^{3/2}}}\biggr) - {1\over 2}\biggl({1\over{1- 4x}}\biggr)\ .\]
Demuestre eso\[r_m = m{2m-1\choose m-1}\ ,\] y\[s_m = {1\over 2}(m+1){2m+1\choose m} - {1\over 2}(2^{2m})\ .\]
Demostrar eso\[E(M_{2m}) = {m\over{2^{2m-1}}}{2m\choose m} + {1\over{2^{2m+1}}}{2m\choose m} - {1\over 2}\ ,\] y
\[E(M_{2m+1}) =
ParseError: EOF expected (click for details)
```
Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[4]/ol[4]/li[6]/span[2]/span, line 1, column 4
```
{2m+2\choose m+1} - {1\over 2}\ .\]
El lector deberá comparar estas fórmulas con la expresión para$g_{2m}/2^{(2m)}$ en Ejemplo [examen 12.1.1].

[exer 12.1.10] (de K. Levasseur ⁴) Un padre y su hijo juegan el siguiente juego. Se baraja una baraja de$2n$ cartas,$n$ roja y$n$ negra. Las tarjetas se entregan una a la vez. Antes de que se entregue cada tarjeta, el padre y el niño adivinan si será roja o negra. Quien haga conjeturas más correctas gana el juego. Se supone que el niño adivine cada color con la misma probabilidad, por lo que tendrá una puntuación de$n$, en promedio. El padre realiza un seguimiento de cuántas tarjetas de cada color ya se han presentado. Si quedan más cartas negras, digamos, que cartas rojas en el mazo, entonces el padre adivinará el negro, mientras que si queda un número igual de cada color, entonces el padre adivina cada color con probabilidad 1/2. ¿Cuál es el número esperado de conjeturas correctas que hará el padre? : Cada uno de los${{2n}\choose n}$ posibles ordenamientos de tarjetas rojas y negras corresponde a una caminata aleatoria de longitud$2n$ que regresa al origen en el momento$2n$. Demostrar que entre cada par de ecualizaciones sucesivas, el padre tendrá razón exactamente una vez más de lo que estará equivocado. Explique por qué esto significa que el número promedio de conjeturas correctas por parte del padre es mayor que$n$ exactamente la mitad del número promedio de ecualizaciones. Ahora defina la variable aleatoria$X_i$ para que sea 1 si hay una ecualización en el momento$2i$, y 0 de lo contrario. Entonces, entre todos los caminos relevantes, tenemos\[E(X_i) = P(X_i = 1) = \frac

ParseError: colon expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[4]/p[18]/span[12]/span[1], line 1, column 3

ParseError: colon expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[4]/p[18]/span[12]/span[2], line 1, column 3

\ .\] Así, el número esperado de ecualizaciones es igual a\[E\biggl(\sum_{i = 1}^n X_i\biggr) = \frac 1

ParseError: colon expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[4]/p[18]/span[13]/span[1], line 1, column 3

\sum_{i = 1}^n

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[4]/p[18]/span[13]/span[2], line 1, column 2

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[4]/p[18]/span[13]/span[3], line 1, column 2

\ .\] Uno ahora puede usar funciones generadoras para encontrar el valor de la suma.

Cabe señalar que en un juego como este, una pregunta más interesante que la que se hizo anteriormente es ¿cuál es la probabilidad de que el padre gane el juego? Para este juego, esta pregunta fue respondida por D. Zagier. ⁵ Demostró que la probabilidad de ganar es asintótica (para grandes$n$) a la cantidad\[\frac 12 + \frac 1{2\sqrt 2}\ .\]

[exer 12.1.11] Demostrar que\[u^{(2)}_{2n} = \frac 1{4^{2n}} \sum_{k = 0}^n \frac {(2n)!}{k!k!(n-k)!(n-k)!}\ ,\] y\[u^{(3)}_{2n} = \frac 1{6^{2n}} \sum_{j,k} \frac {(2n)!}{j!j!k!k!(n-j-k)!(n-j-k)!}\ ,\] donde la última suma se extiende sobre todos los no negativos$j$ y$k$ con$j+k \le n$. También muestran que esta última expresión puede ser reescrita como\[\frac 1{2^{2n}}{{2n}\choose n} \sum_{j,k} \biggl(\frac 1{3^n}\frac{n!}{j!k!(n-j-k)!}\biggr)^2\ .\]

[exer 12.1.12] Demostrar que si$n \ge 0$, entonces\[\sum_{k = 0}^n {n \choose k}^2 = {{2n} \choose n}\ .\]: Escribe la suma como\[\sum_{k = 0}^n {n \choose k}{n \choose {n-k}}\] y explica por qué este es un coeficiente en el producto\[(1 + x)^n (1 + x)^n\ .\] Usa esto, junto con Ejercicio [exer 12.1.11], para demostrar que\[u^{(2)}_{2n} = \frac 1{4^{2n}}

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[4]/p[21]/span[6]/span, line 1, column 2

{{2n}\choose n}^2\ .\]

[exer 12.1.13] Usando la Fórmula de Stirling, demostrar que\[

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/12:_Caminatas_Aleatorias/12.01:_Paseos_Aleatorios_en_Espacio_Euclide**), /content/body/div[4]/p[22]/span[2]/span, line 1, column 2

{\sqrt {\pi n}}\ .\]

[exer 12.1.14] Demostrar que\[\sum_{j,k} \biggl(\frac 1{3^n}\frac{n!}{j!k!(n-j-k)!}\biggr) = 1\ ,\] donde la suma se extiende sobre todos los no negativos$j$ y$k$ tales que$j + k \le n$.: Contar cuántas formas se pueden colocar bolas$n$ etiquetadas en 3 urnas etiquetadas.

[exer 12.1.15] Usando el resultado probado para la caminata aleatoria${\mathbf R}^3$ en Ejemplo [examen 12.1.0.6], explique por qué la probabilidad de un eventual retorno en${\mathbf R}^n$ es estrictamente menor que uno, para todos$n \ge 3$.: Considera una caminata aleatoria${\mathbf R}^n$ e ignora todos menos los tres primeros coordenadas de la posición de la partícula.