First, and foremost,
much respect to you for digging deeper to figure out where AI went wrong.
I
think you're describing the
negative binomial distribution, which "models the number of failures in a sequence of independent and identically distributed
Bernoulli trials before a specified/constant/fixed number of successes
r occur." It fails on this problem for the same reason the
binomial distribution fails as an approach.
When I first encountered this problem independent of classes, while I was an undergrad enrolled in Statistical Theory 1 or 2. It was about making (basketball) five consecutive free throw shots in no more than 100 attempted free throws, given a probability of 30% to make any particular free throw shot. I'm going to revert back to free throws for my explanation here, in the interest of using slightly simpler terminology.
My first inclination was to divide 100 shots into 96 5-shot groups, and treat those 5-shot groups as Bernoulli trials. "[T]he
binomial distribution with parameters
n and
p is the discrete probability distribution of the number of successes in a sequence of n independent experiments, each asking a yes–no question, and each with its own Boolean-valued outcome:
success (with probability
p) or
failure (with probability
q = 1 −
p)."
The probability of making five shots out of five attempts is
p^5 = 0.3^5 = 0.00243. I wanted to subtract the probability that 0 of 96 5-shot groups was successful, which is the complement of at least one 5-shot group being successful, from 1. I applied the binomial distribution's probability mass function:
nCr *
p^
r *
q^(
n-
r), where "
nC
r" is "
n choose
r", the number of ways in which
r items can be selected from
n items, order not important. So, I had:
1 -
nC
r *
p^
r *
q^(
n-
r)
= 1 - (96 choose 0) * 0.00243^0 * (1 - 0.00243)^96
= 1 - 1 * 1 * 0.99757^96
= 1 - 0.99757^96
= 1 - 0.79170701
=
0.20829299, an incorrect result.
The reason it doesn't work is the 96 Bernoulli trials are not independent identically distributed (
i.i.d.) experiments, violating an assumption of the binomial distribution. Each 5-shot group shares four shots with each adjacent 5-shot group. Failure of one group makes a failure of an adjacent 5-shot group more likely. Suppose your first five shots are
success,
failure,
failure,
failure,
success. It's impossible for the second 5-shot group to include no failures.
The trials are not independent. The negative binomial distribution
also requires the Bernoulli trials be independent and identical distributed (
i.i.d.).
I asked my Stat Theory professor about the problem, and he confirmed my approach was wrong and that there
was a way to calculate the result directly, without a
Monte Carlo simulation, but he wouldn't tell me what it was. A couple years later, I learned about
Markov chains, and immediately recognized that they could be used to solve the problem. There were six possible states. There was the case in which five consecutive shots had not yet been made and the case where five in a row had been made. The case in which five shots hadn't yet been made could itself be partitioned into five states: the current streak could be exactly 0, 1, 2, 3, xor 4 shots long. I had my six states, and I knew
p and
q, which was all I needed to model the Markov process.
Besides using Markov chains and Monte Carlo simulations, I'm not aware of any other methods to solve the problem. That doesn't mean there isn't another way, only that I don't know what it is. Every other method
I've tried runs up against the
i.i.d. assumption.