Gambler's ruin — the canonical random walk, exact¶
What this teaches: the textbook absorbing random walk gives three classical closed forms, and
musil.probabilistic returns each one exactly as a fractions.Fraction. A gambler starts with i chips,
bets one at a time on a coin, and stops at ruin (0 chips) or at the goal N.
The model¶
A 1-D walk between two absorbing barriers — up and down are enabled only strictly between them:
Model(
init=Walk(start),
actions=[
Action("up", enabled=lambda s: 0 < s.pos < n, apply=lambda s: Walk(s.pos + 1)),
Action("down", enabled=lambda s: 0 < s.pos < n, apply=lambda s: Walk(s.pos - 1)),
],
terminal=lambda s: s.pos in (0, n), # 0 = ruin, n = goal, both absorbing
)
Reaching the goal — reach_probability¶
With a fair coin the position is a martingale (a fair game), so the probability of reaching N before
0 is linear in the stake: exactly i / N. For N = 5 the starts 0..5 give 0, 1/5, 2/5, 3/5,
4/5, 1.
reach_probability(walk_model(2, 5, up=2, down=1), goal,
weight=lambda name, s: 2 if name == "up" else 1) # Fraction(24, 31)
Weighting the up-step 2 : 1 makes p = 2/3, so q/p = 1/2. The goal probability from i = 2 of
N = 5 is (1 - (1/2)²) / (1 - (1/2)⁵) = (3/4)/(31/32) = 24/31. Weights are integer ratios; the layer
normalises them into the exact distribution.
Expected duration — expected_reward¶
Charge 1 per bet and the expected reward is the expected number of bets until the game ends. For the fair
walk it is exactly i * (N - i):
For N = 5 the starts 0..5 give 0, 4, 6, 6, 4, 0 — longest from the middle, as intuition expects. The
walk is absorbed almost surely, so the expectation is finite (a stochastic-shortest-path answer).
Why i / N (the martingale argument)
Let h(i) be the probability of reaching N before 0 from i. For the fair walk each step goes up or
down with probability 1/2, so h(i) = ½ h(i+1) + ½ h(i-1), with h(0) = 0 and h(N) = 1. That
recurrence forces h to be linear, and the only line through (0, 0) and (N, 1) is h(i) = i / N.
musil does not use this formula — it solves the DTMC's linear system over Fraction — so the test that
reach_probability equals i / N is an independent check of the exact solver.
Source¶
"""Gambler's ruin — the canonical absorbing random walk, three exact closed forms.
A gambler starts with `i` chips and bets one chip at a time on a coin, stopping at ruin (0 chips) or at the
goal `N`. This is the textbook DTMC: a 1-D random walk between two absorbing barriers. `musil.probabilistic`
returns each classical answer exactly, as `fractions.Fraction`:
- `reach_probability` on the FAIR walk — the probability of reaching `N` before `0` from start `i` is exactly
`i / N`. (A martingale result: position is a fair game, so the win probability is linear in the stake.)
- `expected_reward` with a cost of 1 per step — the expected NUMBER OF BETS until the game ends (ruin or goal)
is exactly `i * (N - i)`. A stochastic-shortest-path answer: every strategyless step costs 1, and the walk
is absorbed almost surely, so the expectation is finite.
- `reach_probability(..., weight=...)` on a BIASED walk — when the up-step has probability `p` and the down
`q = 1 - p`, the goal probability is `(1 - (q/p)^i) / (1 - (q/p)^N)`. Weights encode `p : q` as integers.
Everything is exact rational arithmetic: no sampling, no floating point, no dependency.
Run: python examples/gamblers_ruin.py
"""
from __future__ import annotations
from collections.abc import Callable
from dataclasses import dataclass
from fractions import Fraction
from musil import Action, Model
from musil.probabilistic import assert_probability, expected_reward, reach_probability
@dataclass(frozen=True)
class Walk:
pos: int # chips in hand; the walk is absorbed at 0 (ruin) and at N (goal)
def walk_model(start: int, n: int, *, up: int = 1, down: int = 1) -> Model[Walk]:
"""The walk from `start` chips toward goal `n`. `up : down` are the (integer) relative weights of a
winning vs losing bet; the default 1 : 1 is the fair coin. The two barriers (0 and n) are terminal."""
return Model(
init=Walk(start),
actions=[
Action("up", enabled=lambda s: 0 < s.pos < n, apply=lambda s: Walk(s.pos + 1)),
Action("down", enabled=lambda s: 0 < s.pos < n, apply=lambda s: Walk(s.pos - 1)),
],
terminal=lambda s: s.pos in (0, n),
)
def _goal(n: int) -> Callable[[Walk], bool]:
return lambda s: s.pos == n
def _absorbed(n: int) -> Callable[[Walk], bool]:
return lambda s: s.pos in (0, n)
def _one_per_step(_name: str, _s: Walk) -> int:
return 1 # every bet costs 1, so the expected reward is the expected number of bets
if __name__ == "__main__":
N = 5
print("Fair walk — P(reach N before 0) = i / N:")
for i in range(N + 1):
p = reach_probability(walk_model(i, N), _goal(N))
print(f" start {i}: {p}")
assert_probability(p, equals=Fraction(i, N), label=f"P(goal | start {i})")
print("\nFair walk — E[number of bets until absorbed] = i * (N - i):")
for i in range(N + 1):
dur = expected_reward(walk_model(i, N), _absorbed(N), cost=_one_per_step)
print(f" start {i}: {dur}")
assert dur == Fraction(i * (N - i))
print("\nBiased walk — up-step weighted 2 : 1 (p = 2/3), start 2 of 5:")
# Closed form (1 - (q/p)^i) / (1 - (q/p)^N) with q/p = 1/2, i = 2, N = 5:
# (1 - 1/4) / (1 - 1/32) = (3/4) / (31/32) = 24/31.
biased = reach_probability(walk_model(2, N, up=2, down=1), _goal(N), weight=lambda name, _s: 2 if name == "up" else 1)
print(f" P(reach goal) = {biased}")
assert_probability(biased, equals=Fraction(24, 31), label="P(goal | biased, start 2)")
print("\nAll three classical closed forms match exactly — no sampling, no floating point.")
Run it¶
See also¶
- Monty Hall — another exact-fraction DTMC, the famous 2/3 result.
- Availability — steady-state, until-probabilities, and MDP recovery cost.
- API reference —
reach_probability,expected_reward,assert_probability.