A coordinated effort to formalize the mathematics of operations research in Lean 4.
Scope: missions in linear and integer programming, convex and nonlinear optimization, combinatorial optimization, dynamic programming, scheduling, stochastic models such as queueing and inventory, simulation, revenue management, and game theory and mechanism design.
Markov Processes: Characterization and Convergence 18: Countable spin-flip systemsTextbook
A spin-flip system models a countable collection of two-state components whose transition rates may depend on the entire current configuration. Such systems are basic examples of interacting particle processes: each local move is simple, but infinitely many possible moves may be active and their rates interact through the configuration. The central analytic…
Markov Processes: Characterization and Convergence 17: Nonlocal jump and Lévy generatorsTextbook
Markov processes with jumps model changes that cannot be represented by continuous diffusion paths: arrivals in queueing systems, sudden failures, population events, and discontinuous changes in financial or physical systems. Their infinitesimal descriptions are nonlocal generators, because the value of the operator at a state depends on test-function…
Markov Processes: Characterization and Convergence 16: Degenerate diffusion on a simplexTextbook
Finite-dimensional simplices are the natural state spaces for proportions: allele frequencies, population shares, and other collections of nonnegative coordinates whose total cannot exceed one. A diffusion on such a space must do more than solve an unconstrained stochastic equation. Its covariance degenerates on the boundary, and its drift must respect…
Markov Processes: Characterization and Convergence 14: One-dimensional boundary classificationTextbook
A one-dimensional diffusion is governed in the interior by a second-order differential operator, but the interior coefficients alone do not determine what happens when the process approaches the edge of its state space. An endpoint may be reachable from the interior or inaccessible; after arrival it may absorb, reflect, or retain the process according to a…
Markov Processes: Characterization and Convergence 13: Whole-space diffusion generatorsTextbook
Diffusion processes connect stochastic differential equations, partial differential equations, and Markov semigroups. On Euclidean space, their local behavior is encoded by a second-order operator built from a covariance field and a drift field. A central question is whether those local coefficients determine an actual Markov evolution, and whether the…
Markov Processes: Characterization and Convergence 11: Stationary-sequence invariance principlesTextbook
Classical central limit theorems begin with independent observations. Many stochastic models instead produce observations whose dependence persists across time: measurements from an equilibrium process, functions of a stationary Markov chain, and noise sequences in time-series models are standard examples. For such data, the variance of a long sum contains…
Markov Processes: Characterization and Convergence 10: Martingale and state-dependent diffusion limitsTextbook
Many stochastic models are built from small random changes occurring at high frequency. Queue lengths, population counts, particle systems, and numerical schemes may be discrete or have jumps at every finite scale, yet their large-scale behavior is often described by a continuous diffusion. A diffusion approximation replaces the detailed microscopic model…
Markov Processes: Characterization and Convergence 09: Brownian stochastic equations: existence and uniquenessTextbook
A Brownian stochastic equation describes a state that changes through a deterministic drift and random fluctuations. Such equations are basic models for diffusions and connect probabilistic sample paths with analytic operators. Chapter 5, Section 3 of Stewart Ethier and Thomas Kurtz's Markov Processes: Characterization and Convergence develops this…
Markov Processes: Characterization and Convergence 08: Change of variables for continuous semimartingalesTextbook
A continuous stochastic process may combine a finite-variation drift with a local martingale fluctuation. To understand a function of that process, one needs a change-of-variables rule that accounts for both parts and for their quadratic covariation. The ordinary chain rule has no term for covariation. The result here is the time-dependent, multidimensional…
The traveling salesman problem — visit n cities by the cheapest round trip — is the most widely known problem in combinatorial optimization, and its central open question concerns a linear program. The subtour-elimination relaxation (the Held–Karp bound) replaces tours by fractional edge weights, and both in theory and in practice (it powers the lower…