I have a series of N events, each with its own probability of occurring. How would I calculate the probability that at least M of the N events actually do occur?
I think this is conditional, in that getting at least M occurrences depends on getting at least M-1 occurrences. Past that I'm getting stuck.
For any future visitors, the expression given for the probability of at least $m$ out of $n$ events $(A_1, \ldots ,A_n)$ in An Introduction to Probability by William Feller is this:
$$P_m = S_m - \binom{m}{1}S_{m+1}+\binom{m+1}{2}S_{m+2}-\ldots\pm\binom{n-1}{m-1}S_n$$
where $$\displaystyle S_k = \sum_{1\leq i_1< i_2\ldots< i_k\leq n}P(A_{i_1}\cap A_{i_2}\cap\ldots \cap A_{i_k})$$
It's certainly not pretty, but it is general.
It is proved by finding the expression for exactly $m$ events and then adding the expressions from $m$ to all $n$ using induction.
Let us consider that we have four independent events A,B,C,D each with probability Pa,Pb,Pc,Pd associated with it. Now we have to find the probability of at least two events occurring.
First we find the probability of exactly two events occurring.
These two events can be AB, AC, AD, BC, BD, CD.
event space = {AB, AC, AD, BC, BD, CD, }
Since all these events are mutually exclusive.
Probability of any one them occurring is Sum of all probabilities in the events space.
P(AB) = Pa * Pb * (1-Pc) * (1-Pd)
P(AC) = Pa * (1-Pb) * Pc * (1-Pd)
P(AD) = Pa * (1-Pb) * (1-Pc) * Pd
P(BC) = (1-Pa) * Pb * Pc * (1-Pd)
P(BD) = (1-Pa) * Pb * (1-Pc) * Pd
P(CD) = (1-Pa) * (1-Pb) * Pc * Pd
After that we can sum all these to get the probability of Two events occurring. In a similar way we can calculate probability of Three and Four events occurring.
Final probability = Prob(Two_events) + Prob(Three_events) + Prob(Four_events)
However I am unable to generalize for at least M events out of N.
I hope it will shed more light on your problem.
Per Alex's suggestion, here's the Lua script I used to solve my problem. It does take a long while, and don't ignore the optimization suggestion if it's relevant!
--[[
Lua script to calculate the odds that N of M events, each with its own probability of occuring, actually occur.
numEvents: M, the total number of events in the chain
sucessChances: the probabilities of each event, in order
targetNumSuccesses: N, the minimum number of successes we'd like to see
If targetNumSuccesses is less than half of numEvents, this could be optimized by finding event chains with exactly numEvent successes, rather than failures.
The optimization would probably save you several lengthy iterations, especially if targetNumSuccesses is very small.
This is left as an exercise for the reader.
--]]
local numEvents = 30
local targetNumSuccesses = 16
local successChances = {}
for i=1, numEvents do
-- Insert code to calculate your event probabilities here!
local someValue
successChances[i] = someValue
end
-- Establish a failure table of all events failing to occur
local failureTable = {}
local function resetFailureTable()
for i=1, numEvents do
failureTable[i] = false
end
end
-- This is a helper function to work through the possibile permutations of events.
local function reverseSubList(list, front, back)
if front > back then
front, back = back, front
end
local swaps = (back - front)/2
for i = 0, swaps do
list[front+i], list[back-i] = list[back-i], list[front+i]
end
end
local numEventProbability = 0
local totalProbability = 0
local exhausted = false
--[[
Start iterating through the possible series of events.
The outer loop creates an event chain with exactly numEvent *failures*.
The inner loop:
calculates the probability of that event chain
adds it to a running total
finds the next event chain with the same number of failures
Once all chains with exactly numEvent failures have been calculated:
numEvent is "exhausted"
the total probability of all chains with exactly numEvent failures is printed
that value is added to the running total probability
--]]
for numEvents = 1,(numEvents - targetNumSuccesses) do
-- Fill the failureTable with an appropriate number of hits.
resetFailureTable()
for i = 1, numEvents do
failureTable[i] = true
end
-- This is already the base permutation of the failureTable, so:
while not exhausted do
local eventChainProbability = 1
for subEvent = 1, numEvents do
if failureTable[subEvent] then
eventChainProbability = eventChainProbability*(1-successChances[subEvent])
else
eventChainProbability = eventChainProbability*(successChances[subEvent])
end
end
numEventProbability = numEventProbability + eventChainProbability
-- Get the next permutation of the failureTable
for i = 30,1,-1 do
if failureTable[i] == true and failureTable[i+1] == false then
local rightmost
for j=30,1,-1 do if failureTable[j] == false then rightmost = j break end end
failureTable[i] = false
failureTable[rightmost] = true
reverseSubList(failureTable, i+1, 30)
break
elseif i == 1 then
exhausted = true
end
end
end
exhausted = false
print(string.format("Odds of being exactly %d failures: %.2f", numEvents, numEventProbability))
totalProbability = totalProbability + numEventProbability
numEventProbability = 0
end
print("Odds of at least %d successes: %f", targetNumSuccesses, 1-totalProbability)
local a = io.read()
For anyone who finds this question - like I did - and wants to learn more about the problem:
If the $N$ events are independent and non-identical (as suggested by "each with its own probability of occurring" from the question), then the probability of getting $M$ or more successes follows a Poisson-binomial distribution. The answer given by zer0cube is correct and Milind Hegde posted the general case. A closed-form variation of the Probability Mass Function (PMF) - the probability that exactly $M$ trials occur - was found by Fernandez & Williams (2010) (and can be found on the linked wiki page). To find the probability that $M$ or more events occur, then you would sum the PMF for $k$ successes from $k = M, M+1, \dots N$.
