1. ## Tossing game

A man tossing a coin wins one point for heads and five points for tails. The game stops when the man accumulates at least 1000 points.
How do you estimate with accuracy $\pm 2$ the expectation of the length of the game?

A first observation is that the game necessarily stops between 200 and 1000 tosses. Those numbers being "large" enough, the expectation being 3 and the variance 4, e.g. finite, the Law of large Numbers tells us that a first estimate of the average length is 334.
But obviously it is possible to do better than that. (sub)Martingale theory?

2. Originally Posted by akbar
A man tossing a coin wins one point for heads and five points for tails. The game stops when the man accumulates at least 1000 points.
How do you estimate with accuracy $\pm 2$ the expectation of the length of the game?
This is a typical application of Wald's identity: if $X_1,X_2,\ldots$ are i.i.d. integrable random variables and $T$ is an integrable stopping time, then letting $S_n=X_1+\cdots+X_n$, we have:

$E[S_T]=E[X_1]E[T]$.
(This generalizes to martingales; in fact, either you prove it directly in this case or you use a general martingale theorem for the (bounded) martingale $M_n=S_{n\wedge T}-(n\wedge T)E[X_1]$)

In your case, you don't know $E[S_T]$ where $T=\inf\{i|S_i\geq 1000\}$, but you know it is between 1000 and 1004.

3. Wald's identity being based on the Optional Sampling Theorem, on can prove the result directly from it using the fact $Y_n=\sum_1^n X_k-3n$ is a martingale ( $X_n$ being the random variable describing each toss).

4. I have one last question about this problem though: how do you prove that $T$ and the $X_i$ are independent?
This is needed to use Wald's equation, and although it might seem obvious to some, I was wondering if you had some fully convincing arguments.

Devil is always in details.

5. Originally Posted by akbar
I have one last question about this problem though: how do you prove that $T$ and the $X_i$ are independent?
This is needed to use Wald's equation, and although it might seem obvious to some, I was wondering if you had some fully convincing arguments.
I don't know how it could be even remotely obvious... They're obviously not independent on the contrary, and don't need to be; $T$ only needs to be a stopping time relative to the usual filtration relative to $X_1,X_2,\ldots$

6. Agree. I am asking this as it is "obviously" a requirement for the proof of Wald's equation, as it is shown on wikipedia:

Wald's equation - Wikipedia, the free encyclopedia

On the second proof, there is the requirement of $\mathbb{E}(X_i|T=t)=E(X_i)$ for $i\leq t$. So it makes sense in that case.

Note this condition of independence is not mentioned in the PlanetMath version of the result where the wiki article is taken from.
So I hope you understand my need of an expert's view on the matter.
Cordialement.

7. Originally Posted by akbar
Agree. I am asking this as it is "obviously" a requirement for the proof of Wald's equation, as it is shown on wikipedia:

Wald's equation - Wikipedia, the free encyclopedia

On the second proof, there is the requirement of $\mathbb{E}(X_i|T=t)=E(X_i)$ for $i\leq t$. So it makes sense in that case.

Note this condition of independence is not mentioned in the PlanetMath version of the result where the wiki article is taken from.
So I hope you understand my need of an expert's view on the matter.
Cordialement.
1. The wikipedia page states a very simple result (proof: $E[X_1+\cdots+X_T]=E[E[X_1+\cdots+X_T|T]]=E[T E[X_1]]=E[T]E[X_1]$), this is not the "full" Wald's equation; the version you need here is when $T$ is a stopping time, that's the one I quoted.

2. Of course the PlanetMath page is wrong, and doesn't even make sense: what does it mean that $X_1,\ldots,X_N$ are i.i.d. when $N$ is a random variable itself?

3. Your first answer suggested you knew the optional stopping theorem: then you have one proof with no independence needed between $T$ and the $X_i$'s. This proof works in your case since $T$ is bounded, and the steps $X_i$ as well.

4. In order to get the general result I mentioned in my first post, you would need to avoid the optional stopping theorem (which requires for instance a uniform integrability of $(S_{n\wedge T})_{n\geq 0}$) and write a direct (very short) proof:

$E[X_1+\cdots+X_T]=\sum_{n=1}^\infty E[X_n {\bf 1}_{\{T\geq n\}}]$
and, since T is a stopping time, $\{T\geq n\}(=\{T\leq n-1\}^c)$ depends on $X_1,\ldots,X_{n-1}$ and is independent of $X_n$, hence:

$E[X_1+\cdots+X_T]=\sum_{n=1}^\infty E[X_n]P(T\geq n)=E[X_1]\sum_{n=1}^\infty P(T\geq n)$ $=E[X_1]E[T]$.
...as simple as that. (For full rigour, I should first prove that $E[|X_1+\cdots+X_T|]<\infty$, which is obtained via the exact same lines plus the triangular inequality)