Probability involving coin flips

1. Sep 21, 2009

1. The problem statement, all variables and given/known data
We are flipping a coin with probability p of getting heads n times.
A "change" occurs when an outcome is different than the one before it. For example, the sequence HTHH has 2 changes.
If p=1/2 what is the probability that there are k changes?

2. Relevant equations
I've been working with the probability mass function of a binomial random variable:
(n C k) pk(1-p)n-k

3. The attempt at a solution
For the n flips there are n-1 possible "gaps" between flips when change could occur.
I then reasoned that at the end of every flip since you a flipping a fair coin, there is a 1/2 chance of getting a change and a 1/2 chance of not getting a change. My resulting formulation for probability of k changes in n flips was:
(n-1 C k)((1/2)k)((1/2)n-k)
but I worked out explicitly the probabilities of k changes for n=2, 3, and 4 and this function did not give me at all correct answers. I'm not sure how I should approach it differently.

2. Sep 21, 2009

Dick

You've the right idea with (n-1 C k) counting the numbers of ways to get k flips in n throws in terms of where it flips. So how many total ways are there of throwing the coin n times and getting k flips? Now how many ways of throwing the coin n times without that restriction? Isn't the ratio going to be the probability?

3. Sep 21, 2009

"So how many total ways are there of throwing the coin n times and getting k flips? "
I say it's (n-1 C k) again.

"Now how many ways of throwing the coin n times without that restriction?"
2n

So this would give (n-1 C k)/2n, but when I run it against my calculated probabilities this gives half the value of the original answer. So it seems I should multiply by 2 in the formula. Not sure how to justify that though. Is it because you can have changes from H to T and T to H?

4. Sep 21, 2009

Dick

Yes, if you have k flips, you can either start with H or T. 2*(n-1 C k) total ways, right?

5. Sep 21, 2009