Probabilidad de una caminata aleatoria cruzando una línea recta

Question

Deje $(S_n)_{n=1}^{\infty}$ ser un estándar de paseo aleatorio con $S_n = \sum_{i=1}^n X_i$ e $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Deje $\alpha \in \mathbb{R}$ ser una constante. Me gustaría saber el valor de

$$\mathcal{P}(\alpha) := \mathbb{P}\left(\exists \ n \in \mathbb{N}: S_n > \alpha n\right)$$

En otras palabras, estoy interesado en la probabilidad de que una caminata aleatoria $(S_n)_{n=1}^{\infty}$ cruza la línea recta que pasa por el origen con pendiente $\alpha$.

Dado que la norma de paseo aleatorio es recurrente, se desprende que el $\mathcal{P}(\alpha) = 1$ para $\alpha \leq 0$, mientras que, obviamente, $\mathcal{P}(\alpha) = 0$ para $\alpha \geq 1$. Por lo tanto el no trivial de la parte y la parte que más me interesa es la región de $\alpha \in (0,1)$. En esta región, sabemos que $\mathbb{P}(S_1 > \alpha) = \frac{1}{2}$, por lo tanto $\mathcal{P}(\alpha) \geq \frac{1}{2}$, pero encontrar un valor exacto parece difícil.

Nota: Una forma explícita de calcular el $\mathcal{P}(0)$ es por

$$\mathcal{P}(0) = \sum_{n=1}^{\infty} \frac{C_n}{2^{2n-1}} = 1$$

donde $C_n$ es el $n$-th catalán número, como se señaló, por ejemplo, en http://oeis.org/A000108 por Geoffrey Critzer. Para general $\alpha$ sin embargo, una suma no parecen dar una bonita expresión, ya que los coeficientes son más feos y los exponentes de la $2$ dependen de la $\alpha$ (para $\alpha = 0$ uno se exponentes $2n - 1$, pero para irracional $\alpha$ este exponente se convierte en algo feo). Pero encontrar una forma cerrada para estos coeficientes para general $\alpha$ también podría ayudar a resolver este problema.

Edit: Como puede ser demasiado pedir para una buena fórmula para $\mathcal{P}(\alpha)$, yo también estaría muy feliz si alguien podría proporcionar la (buena) límites o aproximaciones del valor de $\mathcal{P}(\alpha)$. Por ejemplo: Qué $\mathcal{P}(\alpha)$ disminuir linealmente en $\alpha$? Cualquier idea es muy apreciada!

Answer 1

Creo que leonbloy comentario/sugerencia es relevante, y siempre que $\alpha$ es racional, $P(\alpha)$ es algebraico. Por ejemplo, $P(1/3)$ es simplemente la probabilidad de que una caminata aleatoria en $\mathbb{Z}$, empezando en el origen y la adopción de medidas de $+2$ o $-1$, con igual probabilidad, nunca llegará $-1$. Si $f(n)$ es la probabilidad de llegar a un punto negativo dado que el pie se encuentra actualmente en $n$,, a continuación, $f(n)$ satisface $$f(n) = \frac{f(n+2)+f(n-1)}2.$$ El estándar ansatz $f(n) = x^n$ da tres soluciones para $x$: $x=1$ o $x=(-1\pm \sqrt{5})/2$. Es fácil ver que la única solución de la forma $f(n) = Ax_1^n + Bx_2^n + Cx_3^n$ que satisface las condiciones de frontera (en $-1$ y el infinito) es $f(n) = (-1/2+\sqrt{5}/2)^{n+1}$, del que se desprende que $$P(1/3) = \frac{\sqrt{5}-1}2.$$ Del mismo modo, $P(1/2)$ es igual a la única raíz de $x = (x^4+1)/2$ en $(0,1)$, y, en general, $P(k/(k+2))$ es el único relevante de raíz de $x = (x^{k+2}+1)/2$.

Si $\alpha$ es racional, pero no de esta forma, las condiciones de frontera se convierten en un poco más complicado. Por ejemplo, considere el $\alpha=1/5$. Esto puede ser modelado por una caminata aleatoria en $\mathbb{Z}$ cuando una partícula se lleva a pasos de $+3$ o $-2$. La correspondiente ansatz da $x^2 = (x^5+1)/2$, que tiene dos raíces de valor absoluto menor que 1, uno positivo y uno negativo. Desde el paseo se puede ahora salta a la izquierda, se puede llegar a un primer valor negativo tanto en la $-1$ y a las $-2$. Aparte de $f(n)\to 0$ en el infinito, obtenemos las dos condiciones de contorno $f(-1)=1$ e $f(-2)=1$. Ahora podemos encontrar $f$ explícitamente (al menos numéricamente) como $f(n) = Ax_1^n+Bx_2^n$ donde $x_1$ e $x_2$ son las raíces en $(-1,1)$ e $A$ e $B$ están determinados por las condiciones de frontera.

Como ya se ha señalado, $P(\alpha)$ hace un salto en cada número racional. Con el enfoque descrito anteriormente, uno de los, en principio, puede calcular tanto el "inferior" y "superior" valores de $P(\alpha)$ (la parte superior del valor es la probabilidad de que $S_n$ alcanza, pero no de la cruz, la línea de pendiente $\alpha$) siempre que $\alpha$ es racional. Esto es posible sólo cuando se $\alpha$ es relativamente simple fracción, pero todavía debe ser posible obtener una buena parcela de $P(\alpha)$ como una función de la $\alpha$.

Recuerdo que después de este problema fue discutido en el problema abierto de la sesión de FPSAC 2003, el Ponto von Brömssen hecho algunas de esas parcelas. Yo no he estado en contacto con él en los últimos años, pero al parecer tiene un (inactivo) MO-cuenta. Yo se lo notifiquen de esta pregunta.

AGREGÓ: Uno podría preocuparse acerca de si, en general, una solución obtenida como se indica arriba es la correcta. Por ejemplo, en el ejemplo con $\alpha = 1/5$, la ecuación de $x^2 = (x^5+1)/2$ tiene, aparte de las tres raíces reales, también con dos raíces reales, e incluso después de encontrar una solución $f$ que implica que sólo los dos raíces reales distinto de 1, puede no ser totalmente evidente que no hay ninguna otra función real de la forma $g(n) = A_1x_1^n+\cdots+A_5x_5^n$ que satisface las condiciones de frontera (esto sería posible si los dos no-real de las raíces tuvo valor absoluto menor que 1).

No es una aplicación simple de movimiento Browniano que muestra que cualquier cosa que satisfaga la recursividad $g(n+2) = (g(n) + g(n+5))/2$ así como las condiciones de frontera, debe ser la solución correcta. Escogí este, recientemente, de Jeff Steif (en un contexto ligeramente distinto), y me dijo que escuché desde Yuval Peres de hace veinte años. Aquí es cómo va:

Supongamos que alguien nos da una función de $g$ que satisface $g(-1) = g(-2) = 1$, $g(n+2) = (g(n) + g(n+5))/2$ para $n\geq 0$, e $g(n)\to 0$ as $n\to\infty$. Ya que tal función debe tener la forma $A_1x_1^n+\cdots+A_5x_5^n$, es fácil ver que todos los valores tienen que estar en el intervalo de $[0,1]$ (no podría haber un menor valor de $g$).

Ahora comienza un movimiento Browniano en la línea real desde el punto de $g(0)$, y se ejecuta hasta que golpea $g(-2)$ o $g(3)$. Si llegara $g(3)$, continúe hasta que llegue a $g(1)$ o $g(6)$, etc. En tiempo finito, la partícula que va a llegar ya sea a $1=g(-1) = g(-2)$ o 0 (en caso de que se fue a través de $g(n)$ para algunos secuencia de $n$'s tiende a infinito).

Se sigue de las propiedades básicas del movimiento Browniano que la probabilidad de que llegue a 1 antes de llegar a cero es $g(0)$. Dado que el proceso correctamente emula el paseo aleatorio discreto de pasos $+3$ e $-2$, se deduce que la probabilidad de que la emulación de pie sobre los enteros llega a $-1$ o $-2$ antes de ir hasta el infinito también es $g(0)$.

Por lo tanto, las condiciones de contorno de forma exclusiva especificar la solución (y el argumento, obviamente, se generaliza para cualquier racional $\alpha$).

Answer 2

Escribí un Arce programa en 2003, que calcula el $P(\alpha)$ (tanto en el "superior" e "inferior" valores) para un determinado número racional $\alpha$, muy en línea con el método descrito por Johan. Creo que yo era capaz de calcular para todas las $\alpha=a/b$ para los números enteros $1\le a\lt b\le 300$ en un par de horas, por lo que el programa probablemente se podría calcular bastante buenas aproximaciones a $P(1-2/\log_2(p))$ al $p$ no es demasiado grande. (Edit: Al $p$ es grande, $1/2$ va a ser una muy buena aproximación. Por ejemplo, si $p\gt1000$ entonces $0.499\lt P(1-2/\log_2(p))\lt1/2$.)

Yo no publicar nada de esto, pero gran parte de ella está contenida en el artículo "El Promedio Máximo de Ganancia en una Secuencia de Bernoulli Juegos" de Wolfgang Stadje (American Mathematical Monthly, diciembre de 2008).

EDIT: Ya que no tengo acceso a Maple más, he traducido el programa Matlab:

function p=p(s,t);
d=gcd(s+t,2*t);
s=(s+t)/d;
t=2*t/d;
pol=zeros(1,t+1);
pol([1 s+1 t+1])=[1 -2 1];
r=roots(pol);
[rsort,i]=sort(abs(r));
p=1-prod(abs(1-r(i(1:t-s))));

El programa calcula $P(s/t)$ para los números enteros $0\lt s\lt t$, mediante el cálculo de $1$ menos que el producto de $1-r$ para los ceros $r$ de % de $z^{2t/d}-2z^{(t-s)/d}+1$ que tiene valor absoluto menos de $1$ (hay $(t-s)/d$ de ellos), donde $d=\gcd(s+t,2t)$.

Por cierto, en mis notas he encontrado el límite inferior $P(\alpha)\ge A$ donde $\alpha=1-\frac{2\log A}{\log(2A-1)}$, con igualdad de $\alpha=(k-2)/k$. Creo que Johan estaba involucrado en la obtención de esta obligado.

EDITAR (14 de Mayo): Así pues, aquí es una manera bastante detallada de la prueba de la fórmula utilizada en el programa anterior.

Lema 1. Para los números enteros $0\lt 2b\lt a$, el polinomio $g(z)=z^a-2z^b+1$ no tiene varios ceros y exactamente $b$ ceros en el interior del círculo unidad.

Prueba. Si $g(z)=g'(z)=0$ entonces $z\ne 0$ y $$0=g'(z)=az^{a-1}-2bz^{b-1}=z^{b-1}(az^{a-b}-2b),$$ por lo $az^{a-b}-2b=0$. Por lo tanto, $0=g(z)-g'(z)*z/a=1-2(1-b/a)z^b$, de modo que $|z|^b=\frac1{2(1-b/a)}=\frac a{2(a-b)}$. También, $az^{a-b}-2b=0$ lo $|z|^{a-b}=2b/a$. Esto implica que $$\left(\frac a{2(a-b)}\right)^{a-b}=\left(\frac{2b}a\right)^b.$$ Esto puede ser reescrita como $2(1-b/a)^{1-b/a}(b/a)^{b/a}=1$. Pero es fácil comprobar que $2(1-y)^{1-y}y^y\gt1$ para $0\lt y\lt1/2$, una contradicción.

La segunda parte puede ser demostrado por una recta de avance de la aplicación del teorema de Rouché.

Lema 2. Supongamos que $\sum_{i=1}^kA_ir_i^{-j}=1$ para $1\le j\le k$. A continuación,$\sum_{i=1}^kA_i=1-\prod_{i=1}^k(1-r_i)$.

Prueba. Las ecuaciones pueden ser vistos como un sistema de ecuaciones lineales en $A_1,\dots,A_k$, y el resultado puede ser obtenido mediante el uso de la regla de Cramer y Vandermonde determinantes. Me salto los detalles. (En realidad, creo que he tenido una sencilla prueba de este lema, pero yo no podía encontrar en mis notas, ni en la figura ahora.)

Ahora, vamos a $L=\max_{n\gt0}{S_n/n}$, por lo que el $P(\alpha)=P(L\gt\alpha)$. También, vamos a $Y_i=(X_i+1)/2$ e $T_n=\sum_{i=1}^nY_i$ (de modo que $T_n$ es un paseo aleatorio con pasos $0$ e $1$ en lugar de $\pm 1$). (La razón principal de esto es que mi resultado original fue para $T_n$, pero también creo que las fórmulas de obtener un poco más sencillo en este caso).

Permítanme subrayar el resultado voy a demostrar:

Teorema. Para los números enteros $0\lt s\lt t$, $P(s/t)=1-\prod_{i=1}^{t-s}(1-r_i)$, donde $r_1,\dots,r_{t-s}$ son los ceros de $z^{2t}-2z^{(t-s)}+1$ que tiene valor absoluto menos de $1$.

Prueba. Deje $M=\max_{n\gt0}{T_n/n}$ e $Q(\alpha)=P(M\gt\alpha)$. Voy a probar el resultado correspondiente para $Q(s/t)$, y luego traducirlo a $P$, utilizando el hecho de que $T_n=(S_n+n)/2$, lo que implica que $P(\alpha)=Q((\alpha+1)/2)$.

Supongamos entonces que $1/2\lt s/t\lt1$ y considerar la posibilidad de $Q(s/t)$. Como Johan hizo, definimos otro paseo aleatorio $U_n=\sum_{i=1}^nZ_i$ con pasos $Z_i=s$ o $Z_i=s-t$, de modo que $Q(s/t)$ es igual a la probabilidad de que $U_n$ nunca llegar a $-1$, definir $f(j)$ como la probabilidad de que $U_n$ llegará $-1$ cuando está actualmente en $j$, y encontrar que $f(j)=f(j+s)/2+f(j+s-t)/2$ para $j\ge0$. La ecuación característica de esta recursividad es $g(z)=z^t-2z^{t-s}+1=0$. Por el Lema 1 y desde $f(j)$ tiende a $0$ as $j$ tiende a infinito, debemos tener $f(j)=\sum_{i=1}^{t-s}A_ir_i^j$ donde $r_1,\dots,r_{t-s}$ son (necesariamente simple) ceros de $g(z)$ dentro del círculo unidad. Desde $f(j)=0$ para $s-t\le j\le -1$, Lema 2 implica que $Q(s/t)=f(0)=\sum_{i=1}^{t-s}A_i=1-\prod_{i=1}^{t-s}(1-r_i)$.

Ahora, si $0\lt s/t\lt1$ entonces $P(s/t)=Q((s+t)/(2t))$, lo que, por lo que demuestran, es igual a $1-\prod_{i=1}^{t-s}(1-r_i)$ donde $r_1,\dots,r_{t-s}$ son los ceros de $z^{2t}-2z^{t-s}+1$ dentro del círculo unidad. Esto concluye la prueba.

Answer 3

He aquí una joya que he oído de Olle Häggström en 2003. No completamente responder a la pregunta, pero es sorprendentemente simple (imo) de manera de obtener un límite superior en $P(\alpha)$.

Supongamos que el pie cruza una línea de pendiente $\alpha$. Luego, en algún punto se encuentra por encima de la línea por última vez. Acondicionado en el último tiempo, podemos permutar los pasos antes de que el punto de cualquier manera que nos gusta, de lo que se deduce que la probabilidad condicional de que el primer paso de la caminata era una $+1$ al menos $(1+\alpha)/2 $. Pero esa probabilidad es sólo $$\frac{1/2}{P(\alpha)},$$ and it follows that $$P(\alpha) \leq \frac{1/2}{(1+\alpha)/2} = \frac{1}{1+\alpha}.$$

AGREGADO: es posible obtener muy fuerte estimaciones de $P(\alpha)$ mediante la combinación de este tipo de argumento con algunos combinatoria de la primera $n$ pasos de la caminata. Por otro lado, la razón por la que la estimación no es fuerte es que el pie, a veces, el sobrepasamiento (en realidad siempre si $\alpha$ es irracional), de modo que el último punto sobre o encima de la línea de pendiente $\alpha$ es estrictamente arriba. Esto indica que el valor exacto de $P(\alpha)$ dependerá, en una forma complicada en la medida en que $\alpha$ puede ser aproximada por los números racionales, y una fórmula simple que puede ser mucho pedir. Estoy seguro de que las cosas interesantes que se puede decir acerca de la $P(\alpha)$, pero podría requerir la especificación de lo que queremos saber.

Answer 4

(Sólo un toque. Debe ser un comentario más de una respuesta, pero no tienen suficiente rep)

Me parece interesante el ligeramente problema más general en el que la inicial de la distancia a la línea es mayor que cero, o que la línea tiene la ecuación de $a n + b$ Considerando los $a$ fijo y $b$ variable, se puede conseguir (si no me equivoco) a la siguiente ecuación en $P(b)$ (probabilidad de que el proceso cruza la línea) como:

$P(b)= \begin{cases} \frac{1}{2}\left[ P(b+a-1)+P(b+a+1) \right], & \mbox{if } b \geq 0; \\ 1, & \mbox{if } b < 0. \end{casos} $

Queremos una solución (aparte de la trivial $P(b)=1$) que se va a cero, como se $b \to \infty$ , y estamos especialmente interesados en $P(0^+)$ No parece fácil, parece muy sensible para el parámetro de $a$. Yo creo que si $a$ es racional, $a=m/n$, la función tiene discontinuidades en los puntos de $k/n$.

Answer 5

Alon / Spencer da una estimación superior en el Apéndice A de "El método probabilístico". Esto proporciona$P(S_n > a) < e^{-a^2/2n}$ para$a > 0$ (Teorema A.1.1). Hay muchos límites como este, si está interesado en límites superiores simples.