I can't get to solve this, could someone help me?
Let $(X_i)$ be such as $P(X_i=1)=P(X_i=-1)= 0.5$ for all $i$ integer such as $1\le i\le n$.
Let $S_n=X_1+...+X_n$.
Let's now consider $2^n$ independant $S_n$ and $Z_n$ be there max.
I would like to: determine then $\lim_{n \to \infty} \frac{Z_n}{n}$.
I was suggested to look at P($S_n$ > $nx$). To do so I tried to calculate the numbers of paths joining $(0,0)$ and the points between $(n,nx)$ and $(n,n)$. The sum is pretty horrible with the factorials...
Any suggestion? Thanks!
Note that $[S_n\geqslant n-2]=[X_i=-1\ \text{for at most one}\ i]$ hence, adding the assumption that the random variables $(X_i)$ used to build $S_n$ are independent, one gets $$P(S_n\geqslant n-2)=(n+1)/2^n.$$ By independence of the $2^n$ copies of $S_n$ used to build $Z_n$, one gets $$ P(Z_n\leqslant n-3)=(1-(n+1)/2^n)^{2^n}\leqslant\mathrm e^{-n-1}. $$ The RHS is summable hence, by Borel-Cantelli lemma, $Z_n\geqslant n-2$ almost surely, for every $n$ large enough, for every dependence structure of the sequence $(Z_n)$ itself. The result follows.