4
$\begingroup$

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?

$\endgroup$
1
  • 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, 2015 at 16:37

1 Answer 1

0
$\begingroup$

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

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

You must log in to answer this question.

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