Gambler's ruin, the Lundberg bound and drawdowns

"""Exercise: gambler's ruin, the Lundberg bound and drawdowns (notes §3.6-3.8).

Implement every function, then run from the repo root:

    cd exercises && .venv/bin/python -m pytest modules/M03-betting-kelly-ruin/tests/test_m03_ruin.py

numpy only. Provided: toolkit.stats.max_drawdown_depth(path), the largest fall from a
running maximum in the path's own units (>= 0); for a Brownian path that is the MDD of
Magdon-Ismail et al. (2004). Fractional drawdowns of wealth use toolkit.stats.max_drawdown.
"""

from __future__ import annotations

import numpy as np

from toolkit.stats import max_drawdown_depth  # noqa: F401  (provided)


def ruin_prob(a: int, N: float, p: float) -> float:
    """Gambler's ruin (Prop. 3.11). A +-1 random walk starts at a (0 <= a <= N),
    steps up with probability p and down with q = 1 - p. Return P(hit 0 before N):
        p != q:  (rho^a - rho^N) / (1 - rho^N),  rho = q / p
        p == q:  1 - a / N
    If N is np.inf: (q/p)^a when p > q, else 1.0.
    """
    raise NotImplementedError


def simulate_ruin(a: int, N: int, p: float, n_paths: int, seed: int, max_steps: int = 1_000_000) -> float:
    """Monte Carlo of ruin_prob: run n_paths walks in parallel (vectorise over
    paths; loop over steps) until each hits 0 or N. Return the fraction hitting 0.
    rng = np.random.default_rng(seed); an up-step occurs when rng.random() < p.
    """
    raise NotImplementedError


def expected_duration(a: int, N: int, p: float) -> float:
    """Expected number of steps until the walk hits 0 or N (Prop. 3.12):
        p == q:  a (N - a)
        p != q:  a / (q - p) - (N / (q - p)) (1 - rho^a) / (1 - rho^N).
    """
    raise NotImplementedError


def lundberg_exponent(p: float, b: float, f: float, tol: float = 1e-13) -> float:
    """For fixed-fraction betting (stake f of wealth on a b:1 bet), log wealth is a
    random walk with steps ln(1 + b f) w.p. p and ln(1 - f) w.p. q. Return the
    theta > 0 solving  p (1 + b f)^(-theta) + q (1 - f)^(-theta) = 1  (Prop. 3.13),
    found by bracketing and bisection. Return 0.0 if the expected log step is <= 0
    (then no positive root exists and hitting any lower level is certain).
    """
    raise NotImplementedError


def ruin_bound_fixed_fraction(p: float, b: float, f: float, x: float) -> float:
    """Upper bound x^theta on P(wealth ever falls to x W0). Return 1.0 if theta == 0."""
    raise NotImplementedError


def simulate_fixed_fraction_hit(p: float, b: float, f: float, x: float, n_bets: int, n_paths: int, seed: int) -> float:
    """Fraction of n_paths fixed-fraction betting paths whose wealth falls to
    <= x W0 at some point within n_bets bets. Win when rng.random(n_paths) < p.
    """
    raise NotImplementedError


def prob_ever_down(m: float, s: float, d: float) -> float:
    """For X_t = m t + s W_t with m > 0, P(X ever reaches -d) = exp(-2 m d / s^2)
    (Prop. 3.7). Return 1.0 if m <= 0.
    """
    raise NotImplementedError


def stationary_drawdown_tail(m: float, s: float, d: float) -> float:
    """Long-run P(drawdown from running max > d) for the same process:
    exp(-2 m d / s^2) (Prop. 3.15)."""
    raise NotImplementedError


def expected_mdd_asymptotic(m: float, s: float, T: float) -> float:
    """Large-T approximation of E[max drawdown] over [0, T] for X = m t + s W
    (Magdon-Ismail, Atiya, Pratap & Abu-Mostafa 2004):
        (2 s^2 / m) * (0.25 ln(m^2 T / (2 s^2)) + 0.49088).
    """
    raise NotImplementedError


def simulate_mdd(m: float, s: float, T: float, n_steps: int, n_paths: int, seed: int) -> np.ndarray:
    """Max drawdown of n_paths discretised paths of X (X_0 = 0, dt = T/n_steps,
    increments m dt + s sqrt(dt) Z). Track running peak and running max drawdown
    rather than storing whole paths. Return the length-n_paths array.
    """
    raise NotImplementedError


def rw_excursion_depth_prob(p: float, k: int) -> float:
    """For a +-1 walk with p > 1/2 standing at its running maximum, the probability
    that it falls k below that maximum before making a new maximum. This is
    gambler's ruin from a = k with N = k + 1 (Prop. 3.16)."""
    raise NotImplementedError