Probability DP: add disjoint outcomes
Picture
A fair coin moves heads or tails with probability one half. Two flips create four equally likely paths.
Predict
When two disjoint paths reach one state, how do probabilities combine?
Walk through the small example
Add them. Disjoint transition outcomes add, while state equivalence allows histories to merge.
Mental model and complete Python solution
Ordinary counting sends one unit down each branch. Probability DP sends a weighted fraction. When branches meet, their mutually exclusive mass adds.
What the function promises: Return probabilities of exactly 0..flips heads for independent fair coin flips.
def head_distribution(flips):
if flips < 0: raise ValueError("Negative flips")
probability = [1.0]
for _ in range(flips):
next_probability = [0.0] * (len(probability)+1)
for heads, mass in enumerate(probability):
next_probability[heads] += mass/2
next_probability[heads+1] += mass/2
probability = next_probability
return probability
dist = head_distribution(2)
assert dist == [0.25,0.5,0.25]
assert abs(sum(head_distribution(20))-1.0) < 1e-12Work and storage: O(flips²) time and O(flips) space for the full final distribution.
When to recognize it: Disjoint transition outcomes add, while state equivalence allows histories to merge.
Check before applying it: Maximizing probability uses different algebra, and dependent events need correct conditional transitions.
Change one rule
Coin bias depends on the previous outcome.
See what changes
Add the previous outcome to the state because it changes the next transition probabilities.
Connect
dp state: Merge histories only when future distributions are identical.
invariants: Total probability mass provides a useful check.