A group of $n \geq 10$ people sits at a round table. Each person tosses a fair coin. Let $X$ be the number of people whose coin and the coins of both neighbors land heads.
a) Compute $\mathbf{var}(X).$
b) Using the Chebyshev inequality, bound $$ \mathbf{P}(|X-\mathbf{E}(X)| \geq c \sqrt{n}), $$ where $c > 0$ is a constant.
Attempt at a)
Let $X$ be the number of people whose coin and the coins of both neighbors land heads.
Let $X_k = \begin{cases}1 \quad \text{ if the $k^{th}$ toss starts a run of $3$ heads } \\ 0 \quad \text{ otherwise. } \end{cases}$
Then $X=X_1+X_2+…+X_n$.
$\mathbf{P}(X_k=1)=\frac{1}{8} \quad \mathbf{E}(X_k)=1\cdot\frac{1}{8}+0\cdot\frac{7}{8}=\frac{1}{8} \quad \mathbf{E}(X_k^2)=1^2\cdot\frac{1}{8}+0^2\cdot\frac{7}{8}=\frac{1}{8}$
$$\begin{align} \mathbf{var}(X)=&\mathbf{E}(X^2)-\mathbf{E}(X)^2 \\
=&\mathbf{E}(\Sigma_1^n X_i^2)-\mathbf{E}(\Sigma_1^n X_i)^2 \\ =&\Sigma_i^n\mathbf{E}(X_i^2)+2\Sigma_{1\leq i \leq j}^n\mathbf{E}(X_iX_j)-(\Sigma_i^n\mathbf{E}(X_i))^2 \\ =& \frac{n}{8} +2\Sigma_{1\leq i \leq j}^n\mathbf{E}(X_iX_j)-(\frac{n}{8})^2 \end{align} $$
Now $X_iX_j= \begin{cases} 1 \quad \text{ if both the $i^{th}$ and $j^{th}$ toss both start runs of $3$ heads}\\ 0 \quad \text{ otherwise. } \end{cases}$
The $\mathbf{P}(X_iX_j=1)=\frac{1}{16}$???
Thus we have that $$\mathbf{var}(X)=\frac{n}{8}+2\frac{n}{16} -(\frac{n}{8})^2 =\frac{16n-n^2}{64}$$
But this seems wrong as it seems to be negative for higher values of $n$. Which we cannot have negative variance.
thank you for your help.
attempt at b) $$ \begin{align} & \mathbf{P}\left(|X-\mathbf{E}(X)| \geq c \sqrt{n}\right) \\ =& \mathbf{P}\left((X-\mathbf{E}(X))^2 \geq c^2n \right) \end{align}$$
Define $Y=\left(X-\mathbf{E}(X)\right)^2 $ then
$$\begin{align} \mathbf{E}(|Y|)=\mathbf{E}(Y)=\mathbf{E}\left(X-\mathbf{E}(X)\right)^2 = n \end{align} $$
Hency by Chebyshev's Inequality, $$\mathbf{P}(|Y| \geq c^2n) \leq \frac{\mathbf{E}(|Y|)}{c^2n}=\frac{1}{c^2}. $$
Best Answer
In the following we use $n$ instead of the longer string $10$. (Number of people.) The indices $j,k$ will be considered modulo $n$. (So $j\pm1$ is also considered after applying $\pm1$ modulo $n$.) The following works for any $n\ge 6$.
Let $X_k$ be the random variable on $\{0,1\}^n$ which is $1$ if the components $k-1,k,k+1$ are all heads, else $0$.
The computation of $\Bbb E X_k = \frac 1{2^3}= \frac 18$ is ok, so $$\Bbb E X =\Bbb E\sum_k X_k =\sum_k \Bbb E X_k = \sum_k \frac 18 = \frac n8\ .$$
Now we compute explicitly for some fixed $k$: $$ \begin{aligned} \Bbb E X_k^2 &=\frac 1{2^3}\ ,\text{ positions $k-1,k,k+1$ are head,}\\ \Bbb E X_kX_{k\pm 1} &=\frac 1{2^4}\ ,\text{ positions $k-1,k,k+1$ and also $k\pm2$ are head,}\\ \Bbb E X_kX_{k\pm 2} &=\frac 1{2^5}\ ,\text{ positions $k-1,k,k+1$ and also $k\pm2,k\pm 3$ are head,}\\ \Bbb E X_kX_j &=\frac 1{2^6}\ ,\text{ positions $k-1,k,k+1$ and also $j-1,j,j+1$ are head,} \end{aligned} $$ the index $j$ being not among the neighbors of distance $\le 2$ to $k$. So $$ \begin{aligned} \Bbb EX^2 &= \Bbb E \sum_{k,j}X_kX_j\\ &= \sum_k\sum_j\Bbb E X_kX_j\\ &=\sum_k\left( \frac 1{2^3} +\frac 1{2^4}+\frac 1{2^4} +\frac 1{2^5}+\frac 1{2^5} +(n-5)\frac 1{2^6} \right) \\ &= \sum_k\frac 1{2^6}(8+4+4+2+2+(n-5)) = \frac {n(n+15)}{64}\ . \end{aligned} $$ So the variation of $X$ is $$ \sigma^2:= \operatorname{Var}[X] = E[X^2]-E[X]^2 = \frac {n(n+15)}{64} - \left(\frac n8\right)^2 = \frac {15n}{64} \ . $$ So the standard deviation $\sigma$ is the square root of this number, a specific constant times $\sqrt n$.
So we apply the inequality of Cebîshev: $$ \Bbb{P}(\ |X-\Bbb{E}(X)| \geq c \sqrt{n}\ ) = \Bbb{P}\left(\ |X-\Bbb{E}(X)| \geq c \cdot\frac 8{\sqrt {15}}\sigma\ \right) \le \left(\frac {\sqrt{15}}{8c}\right)^2 =\frac {15}{64c} \ . $$
For my safe i wanted to verify the above, the following rather simple sage code confirms the results:
Results: