Question
Implement a small numerical toolkit for reasoning about randomized algorithms with non-negative completion times. ```python def markov_tail(mean: float, a: float) -> float: ... def success_equal_restarts(budget: float, mean: float, attempts: int) -> float | None: ... def best_equal_attempt_count(budget: float, mean: float) -> int: ... def exponential_success(budget: float, rate: float = 1.0) -> float: ... ``` ## Requirements - `markov_tail` returns the Markov upper bound on `P(T >= a)`. - For equal restarts, split the budget evenly and derive a distribution-free lower bound using the tail bound; return `None` when it is non-informative under the stated assumptions. - Choose the positive integer attempt count maximizing that bound, with deterministic tie-breaking. - For an exponential clock, return exact success probability within the total budget and explain memorylessness. - Validate positive means, thresholds, budgets, rates, and attempt counts; clamp floating-point probabilities to `[0,1]`. ## Follow-ups 1. Express results using hazard rates. 2. Compare equal splits with a doubling schedule. 3. Optimize restarts when a completion-time distribution is known.