• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

Expected number of tosses

Joined
4/14/12
Messages
90
Points
18
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 :)
 
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}\).
 
Back
Top