Consider n independent flips of a coin having probability p of landing heads. Say a changeover occurs whenever an outcome differs from the one preceding it. If p = 1/2, what is the probability there are k changeovers?(n−1k)(12)n−1 Explanation:
Denote the occurence of a changeover by event - C (for change)
Denote the occurence of a non-changeover by event - S (for sameness)
With this mapping, the above example sequence H H T H T H H T can be rewritten as S C C C C S C, starting from position (2).
Hence, the probability of k changeovers in n trials, is just equal to the probability of occurence of k 'C's in an (n-1) length sequence in the {S,C} universe, as mapped above. But, this is really the same as the probability of occurence of k heads in n-1 trials (because P(S) = P(C) = 1/2, same as probability of occurence of head or a tail). This is nothing but, number of ways of choosing k positions out of n-1 slots for occurence of head (=(n-1)Ck), divided by the total number of combinations possible (=2^(n-1)).
Hence, this is equal to (n−1k)(12)n−1