Im having a problem I wanted to solve but Im having a hard time to do so. the following problem is: $$$$ "Consider tossing a coin n times. We define a run to be a sequence of tosses that result in the same outcome. Thus, for example, if n = 7, the sequence $HHTHTTH$ contains 5 runs, while if n = 12 the sequence $HHHHHTTTTHTT$ contains 4 runs. Fix n and let p be the probability of heads. Let R denote the number of runs. Calculate $ER$ and $Var(R)$, the expected value of the number of runs and it's variance." $$$$
$$$$ I've dealt with the ER quite ok,I did it with indiciator random variables.and ER turned out to be $2np(1-p)$ but I can't figure how to calculate the variance, any help would be appreciated , thanks. $$$$ edit: ok I think I'm on to something,any suggestion if this is correct or not would be appreciated,assuming I can think about every toss as a success if I break the run , which is in probabillity of 2p(1-p) and continuing the current run to be counted as "failure" in prob of 1-2p(1-p). I can say intuitively that all the tosses are independent of each other, because whether a toss "broke" the current run or not doesn't depend if I broke the run beforehand. and if I think about it this way, I can say that R distributes according to Bin(n,2p(1-p)), which solves my problem and VAR(R) turns to be 2np(1-p)(1-2p(1-p)).
We will assume that $n\ge1$.
The Odd Contributions
We start by using stars and bars to count the number of way to divide $h$ heads and $n-h$ tails into $2r+1$ (non-empty) runs. We have two cases, those starting with a run of heads, comprised of $r+1$ runs of heads and $r$ runs of tails: $$ \begin{align} &\overbrace{\binom{0}{r}\binom{0}{n-h}}^{\text{one run, all heads}}+\overbrace{\quad\binom{h-1}{r}\quad}^{\substack{\text{number of ways to}\\\text{arrange $h$ items in}\\\text{$r+1$ bins}}}\overbrace{\binom{n-h-1}{r-1}}^{\substack{\text{number of ways to}\\\text{arrange $n-h$ items}\\\text{in $r$ bins}}}\\[6pt] &=\binom{0}{r}\binom{0}{n-h}+\left[\binom{h}{r}-\binom{h-1}{r-1}\right]\binom{n-h-1}{r-1}\tag{1a} \end{align} $$ and those starting with a run of tails, comprised of $r$ runs of heads and $r+1$ runs of tails: $$ \begin{align} &\overbrace{\ \ \binom{0}{r}\binom{0}{h}\ \ }^{\text{one run, no heads}}+\overbrace{\quad\binom{h-1}{r-1}\quad}^{\substack{\text{number of ways to}\\\text{arrange $h$ items in}\\\text{$r$ bins}}}\overbrace{\binom{n-h-1}{r}}^{\substack{\text{number of ways to}\\\text{arrange $n-h$ items}\\\text{in $r+1$ bins}}}\\[6pt] &=\binom{0}{r}\binom{0}{h}+\left[\frac{n-h}h\binom{h}{r}-\binom{h-1}{r-1}\right]\binom{n-h-1}{r-1}\tag{1b} \end{align} $$ Thus, the probability of getting $2r+1$ runs is $$ \begin{align} P_n(p,2r+1) &=\binom{0}{r}\left(p^n+(1-p)^n\right)\\ &+\sum_{h=1}^{n-1}\left[\frac nh\binom{h}{r}-2\binom{h-1}{r-1}\right]\binom{n-h-1}{r-1}p^h(1-p)^{n-h}\tag{1c} \end{align} $$ Explanation:
$\text{(1c)}$: add $\text{(1a)}$ and $\text{(1b)}$ $$ \begin{align} \sum_{r=0}^\infty&(2r+1)P_n(p,2r+1)\\ &=p^n+(1-p)^n\\ &+\sum_{r=1}^\infty\sum_{h=1}^{n-1}(2r+1)\left[\color{#C00}{\frac nh\binom{h}{r}}-\color{#090}{2\binom{h-1}{r-1}}\right]\binom{n-h-1}{r-1}p^h(1-p)^{n-h}\tag{1e}\\ &=p^n+(1-p)^n\\ &+\sum_{r=1}^\infty\sum_{h=1}^{n-1}\left[\color{#C00}{2n\binom{h-1}{r-1}+\frac nh\binom{h}{r}}\right]\binom{n-h-1}{r-1}p^h(1-p)^{n-h}\\ &-\sum_{r=1}^\infty\sum_{h=1}^{n-1}\left[\color{#090}{4(h-1)\binom{h-2}{r-2}+6\binom{h-1}{r-1}}\right]\binom{n-h-1}{r-1}p^h(1-p)^{n-h}\tag{1f}\\ &=p^n+(1-p)^n+\sum_{h=1}^{n-1}\left[\color{#C00}{2n\binom{n-2}{h-1}+\frac nh\binom{n-1}{h-1}}\right]p^h(1-p)^{n-h}\\ &-\sum_{h=1}^{n-1}\left[\color{#090}{4(h-1)\binom{n-3}{h-1}+6\binom{n-2}{h-1}}\right]p^h(1-p)^{n-h}\tag{1g}\\ &=(\color{#C00}{2np(1-p)+1})-\left(\color{#090}{4(n-3)p^2(1-p)^2+6p(1-p)}\right)\tag{1h}\\[6pt] &=1+(n-3)2p(1-p)-4(n-3)p^2(1-p)^2\tag{1i} \end{align} $$ Explanation:
$\text{(1e)}$: apply $\text{(1c)}$
$\text{(1f)}$: $2r+1=\color{#C00}{2r+1}=\color{#090}{2(r-1)+3}$
$\text{(1g)}$: $\binom{h-k}{r-k}=\binom{h-k}{h-r}$ and sum in $r$ using Vandermonde's Identity
$\text{(1h)}$: $\color{#C00}{\frac nh\binom{n-1}{h-1}=\binom{n}{h}}$ and $\color{#090}{(h-1)\binom{n-3}{h-1}=(n-3)\binom{n-4}{h-2}}$
$\phantom{\text{(1h):}}$ sum in $h$ using the Binomial Theorem
$\text{(1i)}$: collect like terms $$ \begin{align} \sum_{r=0}^\infty&(4r^2+4r+1)P_n(p,2r+1)\\ &=p^n+(1-p)^n\\ &+\sum_{r=1}^\infty\sum_{h=1}^{n-1}(4r^2+4r+1)\left[\color{#C00}{\frac nh\binom{h}{r}}-\color{#090}{2\binom{h-1}{r-1}}\right]\binom{n-h-1}{r-1}p^h(1-p)^{n-h}\tag{1j}\\ &=p^n+(1-p)^n\\ &\textstyle{}+\sum\limits_{r=1}^\infty\sum\limits_{h=1}^{n-1}\left[\color{#C00}{4n(h{-}1)\binom{h-2}{r-2}{+}8n\binom{h-1}{r-1}{+}\frac nh\binom{h}{r}}\right]\binom{n-h-1}{r-1}p^h(1{-}p)^{n-h}\\ &\textstyle{}-\sum\limits_{r=1}^\infty\sum\limits_{h=1}^{n-1}\left[\color{#090}{8(h{-}1)(h{-}2)\binom{h-3}{r-3}{+}32(h{-}1)\binom{h-2}{r-2}{+}18\binom{h-1}{r-1}}\right]\binom{n-h-1}{r-1}p^h(1{-}p)^{n-h}\tag{1k}\\ &=p^n+(1-p)^n\\ &\textstyle{}+\sum\limits_{h=1}^{n-1}\left[\color{#C00}{4n(h{-}1)\binom{n-3}{h-1}{+}8n\binom{n-2}{h-1}{+}\frac nh\binom{n-1}{h-1}}\right]p^h(1{-}p)^{n-h}\\ &\textstyle{}-\sum\limits_{h=1}^{n-1}\left[\color{#090}{8(h{-}1)(h{-}2)\binom{n-4}{h-1}{+}32(h{-}1)\binom{n-3}{h-1}{+}18\binom{n-2}{h-1}}\right]p^h(1{-}p)^{n-h}\tag{1m}\\ &=\left(\color{#C00}{4n(n-3)p^2(1-p)^2+8np(1-p)+1}\right)\\[6pt] &-\left(\color{#090}{8(n-4)(n-5)p^3(1-p)^3+32(n-3)p^2(1-p)^2+18p(1-p)}\right)\tag{1n}\\[6pt] &=1{+}(8n{-}18)p(1{-}p){+}4(n{-}3)(n{-}8)p^2(1{-}p)^2{-}8(n{-}4)(n{-}5)p^3(1{-}p)^3\tag{1p} \end{align} $$ Explanation:
$\text{(1j)}$: apply $\text{(1c)}$
$\text{(1k)}$: $4r^2+4r+1=\color{#C00}{4r(r-1)+8r+1}=\color{#090}{4(r-1)(r-2)+16(r-1)+9}$
$\text{(1m)}$: $\binom{h-k}{r-k}=\binom{h-k}{h-r}$ and sum in $r$ using Vandermonde's Identity
$\text{(1n)}$: $\color{#C00}{(h-1)\binom{n-3}{h-1}=(n-3)\binom{n-4}{h-2}}$ and $\color{#C00}{\frac nh\binom{n-1}{h-1}=\binom{n}{h}}$
$\phantom{\text{(1n):}}$ $\color{#090}{(h-1)(h-2)\binom{n-4}{h-1}=(n-4)(n-5)\binom{n-6}{h-3}}$ and $\color{#090}{(h-1)\binom{n-3}{h-1}=(n-3)\binom{n-4}{h-2}}$
$\phantom{\text{(1n):}}$ sum in $h$ using the Binomial Theorem
$\text{(1p)}$: collect like terms
The Even Contributions
Next, we count the number of way to divide $h$ heads and $n-h$ tails into $2r$ (non-empty) runs. We have two cases, those starting with a run of heads, comprised of $r$ runs of heads and $r$ runs of tails: $$ \overbrace{\quad\binom{h-1}{r-1}\quad}^{\substack{\text{number of ways to}\\\text{arrange $h$ items in}\\\text{$r$ bins}}}\overbrace{\binom{n-h-1}{r-1}}^{\substack{\text{number of ways to}\\\text{arrange $n-h$ items}\\\text{in $r$ bins}}}\tag{2a} $$ and those starting with a run of tails, comprised of $r$ runs of heads and $r$ runs of tails: $$ \binom{h-1}{r-1}\binom{n-h-1}{r-1}\tag{2b} $$ Thus, the probability of getting $2r$ runs is $$ P_n(p,2r)=\sum_{h=1}^{n-1}2\binom{h-1}{r-1}\binom{n-h-1}{r-1}p^h(1-p)^{n-h}\tag{2c} $$ Explanation:
$\text{(2c)}$: add $\text{(2a)}$ and $\text{(2b)}$ $$ \begin{align} \sum_{r=1}^\infty&2rP_n(p,2r)\\ &=\sum_{r=1}^\infty\sum_{h=1}^{n-1}4r\binom{h-1}{r-1}\binom{n-h-1}{r-1}p^h(1-p)^{n-h}\tag{2d}\\ &=\sum_{r=1}^\infty\sum_{h=1}^{n-1}\left[4(h-1)\binom{h-2}{r-2}+4\binom{h-1}{r-1}\right]\binom{n-h-1}{r-1}p^h(1-p)^{n-h}\tag{2e}\\ &=\sum_{h=1}^{n-1}\left[4(h-1)\binom{n-3}{h-1}+4\binom{n-2}{h-1}\right]p^h(1-p)^{n-h}\tag{2f}\\[6pt] &=4p(1-p)+4(n-3)p^2(1-p)^2\tag{2g} \end{align} $$ Explanation:
$\text{(2d)}$: apply $\text{(2c)}$
$\text{(2e)}$: $4r=4(r-1)+4$
$\text{(2f)}$: $\binom{h-k}{r-k}=\binom{h-k}{h-r}$ and sum in $r$ using Vandermonde's Identity
$\text{(2g)}$: $(h-1)\binom{n-3}{h-1}=(n-3)\binom{n-4}{h-2}$
$\phantom{\text{(2g):}}$ sum in $h$ using the Binomial Theorem $$ \begin{align} \sum_{r=1}^\infty&4r^2P_n(p,2r)\\ &=\sum_{r=1}^\infty\sum_{h=1}^{n-1}8r^2\binom{h-1}{r-1}\binom{n-h-1}{r-1}p^h(1-p)^{n-h}\tag{2h}\\ &\textstyle{}=\sum\limits_{r=1}^\infty\sum\limits_{h=1}^{n-1}\left[8(h{-}1)(h{-}2)\binom{h-3}{r-3}{+}24(h{-}1)\binom{h-2}{r-2}{+}8\binom{h-1}{r-1}\right]\binom{n-h-1}{r-1}p^h(1{-}p)^{n-h}\tag{2i}\\ &\textstyle{}=\sum\limits_{h=1}^{n-1}\left[8(h{-}1)(h{-}2)\binom{n-4}{h-1}{+}24(h{-}1)\binom{n-3}{h-1}{+}8\binom{n-2}{h-1}\right]p^h(1{-}p)^{n-h}\tag{2j}\\ &=8(n-4)(n-5)p^3(1-p)^3+24(n-3)p^2(1-p)^2+8p(1-p)\tag{2k}\\[6pt] &=8p(1-p)+24(n-3)p^2(1-p)^2+8(n-4)(n-5)p^3(1-p)^3\tag{2m} \end{align} $$ Explanation:
$\text{(2h)}$: apply $\text{(2c)}$
$\text{(2i)}$: $4r^2=4(r-1)(r-2)+12(r-1)+4$
$\text{(2j)}$: $\binom{h-k}{r-k}=\binom{h-k}{h-r}$ and sum in $r$ using Vandermonde's Identity
$\text{(2k)}$: $(h-1)(h-2)\binom{n-4}{h-1}=(n-4)(n-5)\binom{n-6}{h-3}$ and $(h-1)\binom{n-3}{h-1}=(n-3)\binom{n-4}{h-2}$
$\phantom{\text{(2k):}}$ sum in $h$ using the Binomial Theorem
$\text{(2m)}$: collect like terms
The Expected Value
The sum of $\text{(1g)}$ and $\text{(2f)}$ is $$ \textstyle p^n{+}(1{-}p)^n{+}\sum\limits_{h=1}^{n-1}\left[2(n{-}1)\binom{n-2}{h-1}{+}\binom{n}{h}\right]p^h(1{-}p)^{n-h}\tag{3a} $$ For $n\ge2$, $$ \sum_{h=1}^{n-1}\binom{n-2}{h-1}p^h(1-p)^{n-h}=p(1-p)\tag{3b} $$ Multiplying both sides of $\text{(3b)}$ by $(n-1)$ extends it to $n\ge1$.
Adding the expected value contribution from the odd numbers of runs from $\text{(1h)}$ and the contribution from the even numbers of runs from $\text{(2g)}$, we get the expected value of the number of runs, for $n\ge1$, to be $$ \sum_{r=0}^\infty rP_n(p,r)=1+2(n-1)p(1-p)\tag{3c} $$
The Variance
The sum of $\text{(1m)}$ and $\text{(2j)}$ is $$ \textstyle p^n{+}(1-p)^n{+}\sum\limits_{h=1}^{n-1}\left[4(n{-}2)(n{-}3)\binom{n-4}{h-2}{+}(8n{-}10)\binom{n-2}{h-1}{+}\binom{n}{h}\right]p^h(1{-}p)^{n-h}\tag{4a} $$ For $n\ge4$, $$ \sum_{h=1}^{n-1}\binom{n-4}{h-2}p^h(1-p)^{n-h}=p^2(1-p)^2\tag{4b} $$ Multiplying both sides of $\text{(4b)}$ by $(n-2)(n-3)$ extends it to $n\ge2$. For $n=1$, $\text{(4a)}$ gives $1$.
Adding the expected value contribution from the odd numbers of runs from $\text{(1p)}$ and the contribution from the even numbers of runs from $\text{(2k)}$, we get the expected value of the square of the number of runs, for $n\ge2$, to be $$ \sum_{r=0}^\infty r^2P_n(p,r)=1+(8n-10)p(1-p)+4(n-3)(n-2)p^2(1-p)^2\tag{4c} $$ For $n=1$, the expected value of the square of the number of runs is $1$.
Subtracting the square of $\text{(3c)}$ from $\text{(4c)}$ gives the variance, for $n\ge2$, to be $$ (4n-6)p(1-p)-(12n-20)p^2(1-p)^2\tag5 $$ and for $n=1$, the variance is $0$.