Demuestre que cada posición es igual de probable en este escenario de caminata aleatoria

Question

Hay dos puntos de $A$ e $B$. Usted está de pie en el medio entre ellos.

En cada paso, ir a la mitad del camino hasta el punto de $A$o a la mitad del camino hacia el punto de $B$, cada una con probabilidad de $0.5$. Marca el punto donde se detiene.

Demostrar que la relación de la cantidad de marcas en cada par de subintervalos de intervalo de $[A, B]$ de la misma longitud converge a $1$.

Answer 1

Asumir WLOG $A=0$, $B=1$, por lo que estamos dentro del intervalo de $[0,1]$, luego

$$x_{n+1}=\begin{cases} \frac{x_{n}}{2} & p=\frac12\\ \frac12 +\frac{x_{n}}{2} & p=\frac12\\ \end{casos}$$

con $x_0=1/2$. Considerar la parte fraccionaria de la representación binaria de $x_n$. La anterior regla de transición corresponde al desplazamiento de la parte fraccionaria de un lugar a la derecha y la adición de un $0$ o $1$ , con igual probabilidad para el primer bit de la izquierda.

Ahora, para algunos fijos $m \in \mathbb N$ considerar la $[0,1]$ intervalo dividido en $2^m$ diadic intervalos de longitudes iguales: $I_{m,k}=[ k/2^m,k/2^m+1/2^m)$. Note that the numbers included in each interval share the first $m$ bits de sus partes fraccionarias.

Entonces, si consideramos el intervalo para el cual cada una de las $x_n$ pertenece como un "estado", esto forma una cadena de Markov. Es irreductible, aperiódicos, ergodic, con doblemente estocástica de la matriz de transición: de ahí la distribución estacionaria es uniforme a lo largo de la $2^m$ estados, la media de tiempo de recurrencia es $2^m$, y para las grandes $m$ el número de visitas a cada estado (intervalo) tiende $n/2^m$. Más precisamente: si denotamos por a$V_n(k)$ el número de visitas a intervalo de $k$ a $n$, y por $\ell$ longitud del intervalo, entonces $\lim_{n\to \infty} V_n(k)/n = 2^{-m}=\ell$ casi seguramente; véase, por ejemplo aquí.

En ese sentido, entonces, el número promedio de visitas a cualquier diadic intervalo es (asintóticamente) igual a su longitud. Porque cualquier intervalo se puede expresar como un (countably infinito) suma de los intervalos (con diferentes $m$), entonces la propiedad también se cumple para cualquier intervalo.

Por último , si $A_n$ e $B_n$ representan el número de visitas a dos diferentes intervalos de la misma longitud, $\ell>0$ a $n$, tenemos

$$\lim_{n\to \infty} \frac{A_n}{n} = \ell \hskip{1cm} a.s.$$ $$\lim_{n\to \infty} \frac{B_n}{n} = \ell \hskip{1cm} a.s.$$ lo que implica

$$\lim_{n\to \infty} \frac{A_n}{B_n} = 1 \hskip{1cm} a.s.$$