Bounding profits of gambler by Azuma Inequality

Question

A gambler plays the following game: In each round, he can pay any $0 < p < 1$ dollars, and win 1 dollar with probability p (independently). Show that the probability that the gambler's net gain exceeds h at any of the first n rounds is at most $\exp(\frac {-h^2}{2n})$ (means $P(\max S_n >h)\le\exp(-\frac{h^2}{2n})$).

I thought using Azuma–Hoeffding inequality by defining $X_k=$ the profit per round and $S_k=\sum X_i$ the balance after k rounds. I think that $X_k$ can be viewed as a random walk on $[0,1]$ where in each step the walk goes to a random point on $[0,1]$ uniformly so $X_k,S_k$ fit to this inequality but the lecturer said I need to look instead at $Y_n=\max X_k$.

Suppose I know that $X_k$ is martingale, so is $Y_n$ but how do I prove $X_i=\cases{-p_i\quad p_i\\1-p_i\quad 1-p_i}$ is a martingale?

EDIT: The lecturer said that I need to look at a variable which is similar to $S_k$ (not $\max S_k$ which is not a martingale at all) but I can't find any variable on which I can apply the Azuma Inequality.

Answer 1

Given the history before $i$, you have $X_i = \left\{ \begin{array}{ll} -p_i &\mbox{ with prob $1-p_i$} \\ 1-p_i & \mbox{ with prob $p_i$} \end{array} \right.$

So then $E[X_i]=0$ for all $i$, and $S_k = \sum_{i=1}^k X_i$ is indeed a martingale with bounded changes (why?).

Also, you can consider a "stopped" process $\tilde{S}_k$ that is also a martingale, defined as $S_k$ whenever we have not yet crossed the $h$ threshold, and stopped at the crossing value thereafter.

Answer 2

You've not got your concepts quite right. $X_i$ is a martingale, but $X_i$ actually stores the current value of the game, so your definition of $S_n$ is redundant, and can be replaced by simply $Y_n = \max X_k$. The most amount that can be won in a game is (almost surely) \$1, and the most amount than can be lost is (almost surely) \$1. This allows the definition of $c_k \eq 1$ in the Azuma-Hoeffding inequality that $|X_n - X_{n-1}| \le c_k ( \eq 1)$.

Azuma Inequality

We can apply Azuma's inequality, remembering that $\sum_{i=1}^n 1^2 \eq n$, which gives the probability that $|X_n - X_0| \ge h$, i.e. the probability that $X_n$ (the current value of the martingale) is bigger than $X_0$ (the initial starting value of the martingale, i.e. \$0) by the desired value $h$. This gives the result.

Also $X_k$ is a walk on $(-k,k)$, with each individual game being a walk on $(-1,1)$.