calculating the probability of k changeovers when flipping a coin Consider n independent flips of a coin having probability p of landing heads.
Say that a changeover occurs whenever an outcome differs from the one preceding it. For instance,if n = 5 and the outcome is HHTHT, then there are 3 changeovers. If $p=\frac{1}{2}$, what is the probability there are $k$ changeovers.
I'm pretty sure there is a fancy way but what I got is 
$$P(\text{k change overs}) =
\begin{cases}
2^{k+1}(\dfrac{1}{2^n}), & 0\leq k<n-1 \\
2^{n-k}(\dfrac{1}{2^n}), &  k=n-1 
\end{cases}$$ 
Would this be one correct way of writing the answer? I basically got this by trying a few sample trials.
 A: There are $n-1$ potential changeovers, each equally likely, so this is a binomial problem. Let $C_k$ be the event there are $k$ change-overs.
$$P(C_k) = {n-1\choose k}\dfrac{1}{2^{n-1}}$$ 
Think about the internal gaps between flips as being a success if a change occurs. The next flip will be the same, or not with equal probability. For example, if $n=4$,
$$P(C_0) = P(HHHH)+P(TTTT) = \dfrac{1}{8} ={4-1\choose 0}\dfrac{1}{2^{4-1}}$$
$$P(C_1) = P(THHH)+ P(HTTT)+P(HHTT)+P(HHHT)+ P(TTHH)+P(TTTH) = \dfrac{3}{8} ={4-1\choose 1}\dfrac{1}{2^{4-1}}$$
$$P(C_2) = P(THTT)+ P(HTHH)+P(TTHT)+P(HHTH)+ P(THHT)+P(HTTH) = \dfrac{3}{8} ={4-1\choose 2}\dfrac{1}{2^{4-1}}$$
$$P(C_3) = P(HTHT)+ P(THTH)= \dfrac{1}{8} ={4-1\choose 3}\dfrac{1}{2^{4-1}}$$
A: This problem can be thought of as an instance of the Stars and bars problem:
We place k changeovers (bars) in between the n-1 spaces between the n coin flips (stars). This can be done in $\binom{n-1}{k}$ ways.
The first throw is either a $\{H,T\}$ in 2 ways.
Once the first throw is decided, the full pattern is decided. The probability of a single pattern is $\frac{1}{2^n}$.
Therefore the total probability of k change-overs is $$\binom{n-1}{k}\times 2 \times \frac{1}{2^n}=\binom{n-1}{k}\times  \frac{1}{2^{n-1}}$$
