You are playing a fair betting game. i.e. Every round you win 1 dollar with probability 0.5 or lose 1 dollar with probability 0.5. You play a total of $T$ rounds in a game. Suppose in hindsight, you always left the game when you had the best possible earnings for that game, then what are your expected earnings?

The answer to this is O($\sqrt{T}$). I still can't figure out why. Any suggestions?

  • 1
    $\begingroup$ By reflection principle for $t\ge 0$, $P(M_n>t)=P(S_n>t)+P(S_n>t+1)\le P(|S_n|>t)$, hence $E(M_n)\le E(|S_n|)<\sigma(S_n)=\sqrt n$. Intuitively, average distance from zero at time $n$ is $\sqrt n$, so the maximal possible deviation by time $T$ is also on the order of $\sqrt T$ since SRW is very regular. $\endgroup$ – A.S. Dec 12 '15 at 16:37

This is ultimately a question about random walks, and this problem is very closely related to Wald's Second Identity; Wald's identity states that if $\{X_i\}$ are iid with $\mathbb{E} X_i = 0$ and $\text{Var}(X_i) = 1$, then for any stopping time $T$, we have $$ \mathbb{E} (S_T^2) = \mathbb{E}(T),$$ where $S_k = \sum_{i = 1}^k X_i$. In your case, the $X_i$'s are Rademacher random variables, i.e. $\mathbb{P}(X_i = 1) = \mathbb{P}(X_i = -1) = \frac{1}{2},$ which indeed have mean $0$ and variance $1$.

  • $\begingroup$ I don't think stopping time fits "in hindsight" condition. $\endgroup$ – A.S. Dec 12 '15 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.