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}$$


\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,


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}$$


\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}


\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.

  • $\begingroup$ Have you explored whether a Chernoff bound on $P\{Y_n/n - p^2 > \varepsilon\}$ will work? $\endgroup$ – Dilip Sarwate Jul 22 '18 at 15:11
  • $\begingroup$ @DilipSarwate I am not familiar with Chernoff bounds, so no. $\endgroup$ – StubbornAtom Jul 22 '18 at 16:07

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.