Expected number of tosses

[tuanl]

Given \(0< a<1\) and a is irrational. Let \(d_n=0\) or \(1\), depending on the nth toss is head or tail. Let \(X=\sigma_{n=1}^{\infty}\frac{d_n}{2^n}\). Two players play a game of tossing a fair coin. Player 1 wins the game after N tosses if it is guaranteed at that time that the eventual value of \(X < a\) (i.e, \(\sigma_{n=1}^{N}\frac{d_n}{2^n} +\sigma_{n=N+1}^{\infty} \frac{1}{2^n} < a\)). Similarly, player 2 wins after N tosses if it's guaranteed then that \(X>a\). Given that the probability of player 1 wins is also a. Prove that the expected number of tosses in this game is \(2\).

This is a related question derived from Problem A4 on the Putnam 1989. It's quite beautiful but also tough

 

[pruse]

For each \(n\geq 1\), let \(X_n=1\) if there is no winner on the \(n\)-th toss. Then the expected number of tosses is \(1+\sum_{n=1}^\infty E(X_n)=1+\sum_{n=1}^\infty P(X_n=1)\). We'll show that \(P(X_n=1)=\frac{1}{2^n}\), so that the expectation evaluates to \(1+\frac{1}{2}+\frac{1}{2^2}+\cdots = 2\), as claimed.

For no one to win on the \(n\)-th toss, note that the requisite condition is \(a-\frac{1}{2^n}<0.d_1d_2\cdots d_n < a\), where the "decimal" is in base 2. Also note that the number \(0.d_1\cdots d_n\) is a dyadic number with denominator \(2^n\). Dividing the unit interval into \(2^n\) equal sub-intervals, we see that \(a\) must be located between some two consecutive dyadics \(\frac{k}{2^n}, \frac{k+1}{2^n}\). (Since \a\) is irrational it must fall strictly between them.) Then \(\frac{k}{2^n}\) is the unique dyadic of denominator \(2^n\) between \(a-\frac{1}{2^n}\) and \(a\). This means that, for no winner to emerge on the \(n\)-th toss, the sequence of tosses up to and including the \(n\)-th toss must be given by exactly the binary digits of this dyadic number. The probability of this happening is of course \(\frac{1}{2^n}\).