Upper bound for the probability $P\left[\left|\frac{Y_n}{n}-p^2\right|>\varepsilon\right]$

Question

Let $X_1,X_2,\cdots,X_{n+1}$ be independent random variables with $$P(X_i=1)=p=1-P(X_i=0)\quad\text{ for all }i$$

Define $Y_i$ to be the number of $i$'s such that $X_i=X_{i+1}=1\,,\quad i=1,2,\cdots,n$.

For some $\varepsilon>0$, I am trying to find an upper bound of the probability$$T_n=P\left[\left|\frac{Y_n}{n}-p^2\right|>\varepsilon\right]$$

We can write $$Y_n=Z_1+Z_2+\cdots+Z_n$$

where $$Z_K=\begin{cases}1&,\text{ if }X_k=X_{k+1}=1\\0&,\text{ otherwise}\end{cases}$$

So,

\begin{align}E(Y_n)&=\sum_{k=1}^n E(Z_k) \\&=\sum_{k=1}^nP(X_k=1,X_{k+1}=1) \\&=\sum_{k=1}^nP(X_k=1)P(X_{k+1}=1)=np^2 \end{align}

That is, $$E\left(\frac{Y_n}{n}\right)=p^2$$

Using Markov's inequality,

$$P\left[\left|\frac{Y_n}{n}-E\left(\frac{Y_n}{n}\right)\right|>\varepsilon\right]<\frac{\operatorname{Var}\left(\frac{Y_n}{n}\right)}{\varepsilon^2}\quad,\,\varepsilon>0$$

So one upper bound of the desired probability $T_n$ is $$\frac{\operatorname{Var}(Y_n)}{n^2\varepsilon^2}=g(n)\quad,\text{say}$$

We have $$\operatorname{Var}(Y_n)=\sum_{k=1}^n \operatorname{Var}(Z_k)+2\sum_{k>k'}\operatorname{Cov}(Z_k,Z_{k'})\tag{1}$$

Now,

\begin{align} \operatorname{Var}(Z_k)&=E(Z_k^2)-(E(Z_k))^2 \\&=P(Z_k=1)-\left(P(Z_k=1)\right)^2 \\&=p^2-p^4 \end{align}

And

\begin{align} \operatorname{Cov}(Z_k,Z_{k+1})&=E(Z_kZ_{k+1})-E(Z_k)E(Z_{k+1}) \\&=P(Z_k=1,Z_{k+1}=1)-P(Z_k=1)P(Z_{k+1}=1) \\&=p^3-p^4 \end{align}

We also note that $$\operatorname{Cov}(Z_k,Z_{k'})=0\qquad,\text{ if }|k-k'|>1$$

Hence from $(1)$ we arrive at

\begin{align} g(n)&=\frac{np^2(1-p)(1+p)+2(n-1)p^3(1-p)}{n^2\varepsilon^2} \\&=\frac{p^2(1-p)}{n\varepsilon^2}\left[1+p+2\left(1-\frac{1}{n}\right)p\right] \\&<\frac{p^2(1-p)(1+3p)}{n\varepsilon^2} \end{align}

While I reached this answer as a simple application of a probability inequality, my question is what other approach could I take to find an upper bound of the probability? Surely, this upper bound is not unique, so what other answers could I arrive at using a different approach, maybe by using some limit theorem? After upper bounds, is it a valid question to ask for the supremum of $T_n$?

The source of the problem is basically some old exam papers. If what I seek is some sort of a classic result or inequality, then I would like to know about the theory behind that as well.

Answer 1

Let $\mathcal F_k$ be the $\sigma$-algebra generated by $X_1,\dots,X_k$. Let $D_k:=Y_k-\mathbb E\left[Y_k\mid\mathcal F_k\right]$. Then $\left(D_k\right)_{k\geqslant 1}$ is a martingale differences sequence for the filtration $\left(\mathcal F_{k+1}\right)_{k\geqslant 1}$. Since $\left\lvert D_k\right\rvert\leqslant 1$, Hoeffding's inequality entails that $$T'_n:=\Pr\left(\left\lvert \sum_{k=1}^nD_k\right\rvert\gt n\varepsilon/2\right)\leqslant 2\exp\left(-n\varepsilon^2/4\right).$$ Since $\mathbb E\left[Y_k\mid\mathcal F_k\right]=p\mathbf 1\left\{X_k=1\right\}$, we can treat $$ T''_n:=\Pr\left(\left\lvert \sum_{k=1}^n\mathbb E\left[Y_k\mid\mathcal F_k\right]-p^2\right\rvert\gt n\varepsilon/2\right) $$ using Hoeffding's inequality forsum of independent random variables.