Problem source

A fair coin is thrown $n$ times. On each throw, 1 point is scored for a head and 1 point is lost for a tail. Let $S_{n}$ be the points total for the series of $n$ throws, i.e. $S_{n}=X_{1}+X_{2}+\cdots+X_{n},$
where 
\[
X_{j}=\begin{cases}
1 & \text{ if the }j \text{ th throw is a head}\\
-1 & \text{ if the }j\text{ th throw is a tail.}
\end{cases}
\]
\begin{questionparts}
\item  If $n=10\,000,$ find an approximate value for the probability that
$S_{n}>100.$
\item Find an approximate value for the least $n$ for which $\mathrm{P}(S_{n}>0.01n)<0,01.$ 
\end{questionparts}
Suppose that instead no points are scored for the first throw, but that on each successive throw, 2 points are scored if both it and the first throw are heads, two points are deducted if both are tails, and no points are scored or lost if the throws differ. Let $Y_{k}$ be the score on the $k$th throw, where $2\leqslant k\leqslant n.$
Show that $Y_{k}=X_{1}+X_{k}.$
Calculate the mean and variance of each $Y_{k}$ and determine whether it is true that 
\[
\mathrm{P}(Y_{2}+Y_{3}+\cdots+Y_{n}>0.01(n-1))\rightarrow0\quad\mbox{ as }n\rightarrow\infty.
\]

Solution source

Notice that $\mathbb{E}(X_i) = 0, \mathbb{E}(X_i^2) = 1$ and so $\mathbb{E}(S_n) =0, \textrm{Var}(S_n) = n$.

\begin{questionparts}
\item Then by the central limit theorem (or alternatively the normal approximation to the binomial), 

\begin{align*}
&& \mathbb{P}(S_n > 100) &\underbrace{\approx}_{\text{CLT}} \mathbb{P} \left (Z > \frac{100}{\sqrt{10\, 000}} \right) \\
&&&= \mathbb{P}(Z > 1) \\
&&&= 1-\Phi(1) \\
&&&\approx 15.9\%
\end{align*}

\item \begin{align*}
&&\mathbb{P}(S_n > 0.01n) &\approx \mathbb{P} \left (Z > \frac{0.01n}{\sqrt{n}} \right) \\
&&&= \mathbb{P}(Z > 0.01 \sqrt{n}) \\
&&&= 1-\Phi(0.01\sqrt{n}) \\
&&&< 0.01 \\ 
&& \Phi^{-1}(0.01) &= -2.3263\ldots \\
\Rightarrow && 0.01 \sqrt{n} &= 2.3263\ldots \\
\Rightarrow && n &\approx 233^2
\end{align*}
\end{questionparts}

\begin{array}{cc|cc}
1\text{st throw}& k\text{th throw} & X_1 + X_k & Y_k \\ \hline
\text{head} & \text{head} & 1 + 1 & 2 \\
\text{head} & \text{tail} & 1 - 1 & 0 \\
\text{tail} & \text{head} & -1 + 1 & 0 \\
\text{tail} & \text{tail} & -1- 1 & -2 \\
\end{array}

Across all possible cases $Y_k = X_1 + X_k$ so therefore these random variables are equal.

\begin{align*}
\mathbb{E}(Y_k) &= \mathbb{E}(X_1) + \mathbb{E}(Y_k) \\
&= 0 + 0 = 0 \\
\\
\textrm{Var}(Y_k) &= \textrm{Var}(X_1)+\textrm{Var}(X_k) \\
&= 2 \\
\\
\mathbb{E}\left (\sum_{k=2}^n Y_k \right) &= 0 \\
\textrm{Var}\left (\sum_{k=2}^n Y_k \right) &= 2(n-1)
\end{align*}

Therefore approximately $\displaystyle \sum_{k=2}^n Y_k \approx N(0, 2(n-1))$

\begin{align*}
\mathbb{P} \left (\sum_{k=2}^n Y_k  > 0.01(n-1) \right) &\approx \mathbb{P} \left (Z > \frac{0.01(n-1)}{\sqrt{2(n-1)}} \right)  \\
&=  \mathbb{P} \left (Z > c \sqrt{n-1} \right)  \\
&\to 0 \text{ as } n \to \infty
\end{align*}