8
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ "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? $\endgroup$
    – leonbloy
    May 5, 2019 at 18:46
  • $\begingroup$ @leonbloy You mark each place you visit. $\endgroup$
    – BoltKey
    May 5, 2019 at 19:09

1 Answer 1

3
$\begingroup$

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.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .