# asymptotic distribution of the maximum of partial sums of iid binary random variables (Bernoulli)

I've encountered a problem when using the random walk to approximate a Brownian motion:

Consider a sequence of iid random variable ${X_{i}}\$ where $i=1,2,...\$ with binary outcomes such that: $X_{i}=1$ with probability $p$, and $X_{i}=-1$ with $1-p$.

Define the partial sums as $Y_{n}=X_{1}+X_{2}+...+X_{n}$.

And the maximum as $Z_{n}=\max_{1\leq i \leq n} {Y_{i}}$

Let $a\$ be a positive number. The problem is to find the value of

$$\lim_{n\rightarrow\infty}\Pr\lbrace Z_{n}\geq a\rbrace$$

I tried to consider an example where $a=0.5$, then $$\Pr\{Z_{1}\geq0.5\}=p$$ $$\Pr\{Z_{2}\geq0.5\}=\Pr\{\max_{i=1,2}Y_{i}\geq0.5\}=\Pr\{\max\{X_{1},X_{1}+X_2\}\geq0.5\}$$ $$=1-\Pr\{X_1<0.5, X_1+X_2<0.5\}=1-\Pr\{X_1+X_2<0.5\mid X_1<0.5\}\Pr\{X_1<0.5\}$$ $$=1-1*(1-p)=p$$ and $$\Pr\{Z_3\geq0.5\}=1-\Pr\{X_1<0.5, X_1+X_2<0.5, X_1+X_2+X_3<0.5\}$$ but it seems complicated, according to the answer for a similar question: Distribution of maximum of partial sums of independent random variables, Markov property doesn't hold here. And the result is: $$\Pr\{Z_3\geq0.5\}=p^2+p-p^3$$

So is there a closed-form expression for this binary case? Many thanks!

• For the closed-form, I don't know but I'd doubt. In any case, you don't need it to solve your problem. – user52227 Oct 3 '17 at 8:32