Flipping an unfair coin

Question

An coin has probability $p<0.5$ of landing heads up. We flip it infinitely many times, after $n$ tosses, let $S_n$ be the number of heads minus the number of tails. What is the expected value of $max\{S_0,S_1,S_2,S_3,...\}$?

Answer 1

Let $M=\max\{S_k;k\geqslant0\}$ and, for every $n\geqslant0$, $T_n=\inf\{k\geqslant0\mid S_k=n\}$. Thus $T_0=0$, if $n\geqslant1$ then $T_n$ may be infinite with positive probability, and $[M\geqslant n]=[T_n\lt\infty]$ for every $n\geqslant0$. Furthermore, conditionally on $[T_n\lt\infty]$, $T_{n+1}\lt\infty$ means that the path after time $T_n$ reached level $+1$ above level $n$. By Markov strong property, this implies that $P[T_{n+1}\lt\infty\mid T_n\lt\infty]=u$ with $u=P[T_{1}\lt\infty]$. Thus, $P[T_n\lt\infty]=u^n$ for every $n\geqslant0$ and $$ E[M]=\sum_{n\geqslant1}P[M\geqslant n]=\sum_{n\geqslant1}P[T_n\lt\infty]=\sum_{n\geqslant1}u^n=\frac{u}{1-u}. $$ To compute $u$, let us condition on $X_1$. If $X_1=1$, $T_1\lt\infty$. If $X_1=-1$, to hit $1$ starting from $-1$ one must climb two stairs. Hence, $u=p\cdot1+(1-p)\cdot u^2$. Since $p\lt\frac12$, $u\lt1$ hence $u=p/(1-p)$. Finally, $$ E[M]=\frac{p}{1-2p}. $$