Someone recently contacted me to ask the following question: What is the probability that two students, each taking the same multiple choice exam, with q possible answers per question, will get k or more identical answers in a row?
I initially imagined this to be straightforward. It’s just a sequence of n Bernoulli trials with p=1/q, with k successes, right? Probably just a few terms clumped with a binomial distribution? Oh, boy was I wrong. Go try it out.
MathWorld has an especially interesting solution: http://mathworld.wolfram.com/Run.html