What is the expected number of flips you need to get k changeovers? Flip a fair coin several times. Say that a changeover occurs whenever an outcome differs from the one preceding it. For instance, if you flip the coin 5 times and the outcome is HHTHT, then there are 3 changeovers.

*

*Consider n independent flips of this coin, what is the expected number of changeovers?


*What is the expected number of flips you need to get k changeovers?
My Attempt

*

*This one isn't too hard. Let $I_j$ be an indicator random variable that equals $1$ if we have a changeover and $0$ otherwise. For $I_j=1$, we need to have a heads on the $j^{th}$ flip and tails on the $(j+1)^{th}$ flip or tails first then heads for $j\in[1,n-1]$. Thus,
$$\mathbb{P}(I_j=1)=2p(1-p)$$
Our coin is fair, so $p=\frac{1}{2}$. Thus, $\mathbb{P}(I_j=1)=\frac{1}{2}$
If X is a random variable representing the number of changeovers. Then by linearity of the expectation, we have that
$$\mathbb{E}(X)=\sum_j\mathbb{P}(I_j)=(n-1)\cdot\frac{1}{2}=\frac{n-1}{2}$$


*For this part, I am not so sure how to start. Would I use a binomial distribution? As in $X\sim\text{Bin}(n,\frac{1}{2})$ so that our probability is
$$\mathbb{P}(X=k)=\binom{n}{k}(\frac{1}{2})^k(1-\frac{1}{2})^{n-k}$$
I'm not too sure that this is the right approach or how to continue.
Edit
Second attempt for the second part: (I know this is wrong from the comments below, but can I get pointers on where I went wrong?)
Let X be the number of flips before k changeovers. Then $X\sim\text{Geom}(p)$. The probability is given by the formula
$$\mathbb{P}(X=k)=(1-p)^{k-1}p$$
We know that $p=\frac{1}{2}$ from the last part, so $\mathbb{P}(X=k)=\frac{1}{2^k}$ The expectation of a geometric distribution is $\mathbb{E}[X]=\frac{1}{p}$, so we have $E[X]=2^k$
 A: Your solution for the first part is correct.
For the second part, let the probability of heads be $p$ and the probability of tails be $q=1-p$.  If we've just thrown heads, then the number of tosses until the next tails is geometrically distributed with parameter $q$ and the expected number of tosses is $\frac1q$.  Similarly the expected number of tosses until the first heads after a tails is $\frac1p$.  If the first toss is heads then the expected number of tosses until the $k$th changeover is $$1+\left\lceil\frac k2\right\rceil\frac1q+\left\lfloor\frac k2\right\rfloor\frac1p,$$
since $\left\lceil\frac k2\right\rceil$ changeovers are from heads to tails, and $\left\lfloor\frac k2\right\rfloor$ changeovers are from tails to heads.  This is because the first changeover is from heads to tails, and the types of the changeovers alternate.
Similarly, if the first toss is tails then the expected number of tosses until the $k$th changeover is $$1+\left\lceil\frac k2\right\rceil\frac1p+\left\lfloor\frac k2\right\rfloor\frac1q.$$ Weighting these by the appropriate probabilities, we get that the expectation is $$1+2\left\lfloor\frac k2\right\rfloor+\left\lceil\frac k2\right\rceil\left(\frac pq+\frac qp\right).$$
With a fair coin $p=q$, and this simplifies to $2k+1$.
A: 1 More simply, we aren't concerned as to which face appeared on the first flip, or later on, on the $(i-1)^{th}$ flip.
With $X_i$ as the indicator variable indicating an $i_{th}$ flip changeover,
$\Bbb E[X_i] = \Bbb P[X_i] = \frac1 2$
and by linearity of expectation, summing from $i=2\,to\;  n, \,\Bbb E[X] = \frac{(n-1)}2$
2 From results of part $1, k = \frac{(n-1)}2$,
so $n = 2k+1$
