# Prove that every position is equally as likely in this random walk scenario

There are two points $$A$$ and $$B$$. You are standing in the middle between them.

In each step, go half the way to the point $$A$$, or half the way to the point $$B$$, each with probability of $$0.5$$. Mark the point where you stop.

Prove that the ratio of amount of marks on each pair of subintervals of interval $$[A, B]$$ of the same length converges to $$1$$.

• "Mark the point where you stop." You mean you place a mark in each place you visit ? Or rather you have a fixed number of iterations $n$ and you mark the final point only? May 5, 2019 at 18:46
• @leonbloy You mark each place you visit. May 5, 2019 at 19:09

Assume WLOG $$A=0$$, $$B=1$$, so that we are inside the interval $$[0,1]$$, then

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

with $$x_0=1/2$$. Consider the fractional part of the binary representation of $$x_n$$. The above transition rule corresponds to shifting the fractional part one place to the right and adding a $$0$$ or a $$1$$ with equal probability to the first bit on the left.

Now, for some fixed $$m \in \mathbb N$$ consider the $$[0,1]$$ interval divided into $$2^m$$ diadic intervals of equal lengths: $$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 of their fractional parts.

Then, regarding as a "state" the interval to which each $$x_n$$ belongs to, we have a Markov chain. It's irreducible, aperiodic, ergodic, with doubly stochastic transition matrix: hence the stationary distribution is uniform over the $$2^m$$ states, the mean recurrence time is $$2^m$$, and for large $$m$$ the number of visits to each state (interval) tends to $$n/2^m$$. More precisely: if we denote by $$V_n(k)$$ the number of visits to interval $$k$$ up to time $$n$$, and by $$\ell$$ the interval length, then $$\lim_{n\to \infty} V_n(k)/n = 2^{-m}=\ell$$ almost surely; see eg here.

In that sense, then, the average number of visits to any diadic interval is (asymptotically) equal to its length. Because any interval can be expressed as a (countably infinite) sum of such intervals (with different $$m$$), then the property also holds for any interval.

Finally , if $$A_n$$ and $$B_n$$ represent the number of visits to two different intervals of same length $$\ell>0$$ up to time $$n$$, we have

$$\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.$$ which implies

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