Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Stochastic Systems

635 missions · 329 completed

The mathematics of systems that evolve under randomness, modeled as families of random variables indexed by time — from Markov chains and martingales to Brownian motion and stochastic differential equations. The field spans stochastic analysis, filtering and optimal control under uncertainty, ergodic behavior of random dynamics, and concentration of measure, with models reaching across physics, engineering, finance, and biology.

Missions

Open306Completed329All635
🏆Completed
Markov ChainNumerical AnalysisOperations Research+1·Captain: mikedeng1

Fundamentals of Queueing Theory X: Uniformization of Continuous-Time Markov ChainsTextbook

Most Markovian queueing models have no closed-form transient solution. The M/M/1 queue already needs modified Bessel functions (Chapter 2 of the book), and a finite-capacity or multi-class model with state-dependent rates has no closed form at all. What an analyst can always write down is the system of forward equations p′(t)=p(t)Qp'(t)=p(t)Qp′(t)=p(t)Q for the state…

8 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems XIV: Conforming Approximating Sequences for Markov ChainsTextbook

Countable-state Markov chains are the standard model of queues with unbounded buffers, but any numerical computation of their long-run behaviour works on a finite state space. The usual remedy is truncation: restrict the chain to a finite set SNS_NSN​ and redistribute the probability of leaving SNS_NSN​ back into it. Whether the steady state probabilities and average…

10 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Computing Optimal (s, S) Inventory Policies I: The Renewal Closed Form for the Discounted Cost of a Stationary (s, S) PolicyResearch Paper

The periodic-review inventory problem with a fixed ordering cost is one of the basic models of operations research. A firm reviews its stock once per period, may order at a cost KKK per order plus a unit cost, and then faces a random demand; unmet demand is backlogged. Scarf (1960) and Iglehart (1963) showed that for this model an (s,S)(s, S)(s,S) policy is optimal:…

12 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

Markov-Renewal Programming. II: Infinite Return Models, Example II: Gain and Bias of the Infinite-Step ReturnResearch Paper

A Markov-renewal program is a sequential decision model in which a system moves among finitely many states, the time between transitions is random and may depend on both the current and the next state, and a reward accrues during each sojourn. It generalizes the Markov decision process, where every transition takes one time unit, and is the standard model…

10 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

Markov-Renewal Programming. II: Infinite Return Models, Example I: Policy Iteration Finds a Stationary Policy of Maximal Gain RateResearch Paper

Many controlled systems do not move in unit time steps. A machine runs for a random time before it breaks down, a repair takes a random time, a queue sits in a state until the next arrival or departure. A Markov-renewal program (in later terminology a semi-Markov decision process) models such a system: the sequence of visited states is a Markov chain…

7 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Exit Problems for Spectrally Negative Lévy Processes and Applications to (Canadized) Russian Options III: Optimal Stopping for the Canadized Russian OptionResearch Paper

The Russian option of Shepp and Shiryaev pays its holder, at an exercise time of their choosing, the running maximum of the stock price, discounted, with no fixed maturity. It is the standard example of a perpetual lookback option, and its value is a model problem of optimal stopping for a two-dimensional Markov process (the price and its running maximum).…

18 thms2 active usersReviewed
🏆Completed
AnalysisOperations Research·Captain: mikedeng1

Diffusion approximations for open queueing networks with service interruptions 1: explicit Lipschitz bounds for the oblique reflection mapResearch Paper

Heavy-traffic and fluid approximations for open queueing networks are obtained by writing the queue-content process as a deterministic function of a simpler netput process (arrivals minus potential service, corrected for routing) and then transferring a functional limit theorem for the netput through that function. The function is the multidimensional reflec…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: Shuze Chen

Processing Networks VII: Global Stability, Rings, and the Rybko–Stolyar BoundaryTextbook

Mission VI showed that two structural families of queueing networks — feedforward routing, and any network under HLSPS control — are stable throughout their entire subcritical region: no extra condition beyond the standard load condition is ever needed. Until the early 1990s it was widely conjectured that this held for every queueing network. Rybko and…

13 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: Shuze Chen

Processing Networks VI: Feedforward and Generalized Jackson Network StabilityTextbook

Mission V supplied the general Lyapunov machinery — the extinction criteria of Lemmas 8.5, 8.6 and 8.11 — but a Lyapunov function does not construct itself. For a specific network structure and control policy, one must exhibit a concrete function and verify the drift condition. J. G. Dai and J. Michael Harrison's Processing Networks: Fluid Models and…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchPartial Differential EquationsProbability·Captain: mikedeng1

Revenue Management of a Make-to-Stock Queue: Exponential Stationary Density under Normal Reflection (Proposition 2)Research Paper

A make-to-stock manufacturer who also sells on a spot market must decide, at every moment, whether to keep producing and whether to accept or reject incoming orders at the prevailing price. Caldentey and Wein (Revenue Management of a Make-to-Stock Queue, Operations Research 54(5), 2006) study this problem in heavy traffic. The limit is a two-dimensional…

10 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Open, Closed, and Mixed Networks of Queues with Different Classes of Customers: The Product-Form Equilibrium DistributionResearch Paper

Networks of queues model computer systems, communication networks and manufacturing lines: customers (jobs, packets, parts) move between service centers, wait, receive service and move on. Their equilibrium behaviour determines throughputs, utilizations and response times, and for most networks it can only be computed by solving the full balance equations…

9 thms2 active usersReviewed
🏆Completed
Linear Optimization·Captain: mikedeng1

Stochastic Linear Programming 02: Finiteness and Smoothness of Expected Fixed RecourseTextbook

A two-stage stochastic linear program chooses a first-stage decision before uncertain coefficients are known and then uses recourse variables to repair the decision after the data are observed. The resulting expected recourse cost is central to existence, stability, and numerical methods: if it can be infinite, an apparently feasible model may still have no…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Stochastic Orders VIII: Closure of the Convexity Orders Under Random SumsTextbook

Chapters III and IV formalize what it means for one random variable to be "more spread out" or "larger and more spread out" than another. Chapter VIII asks a different kind of question: if the number of terms in a sum of i.i.d. random variables is itself random, and one count is larger than another in one of these orders, does the resulting random sum…

4 thms2 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: naimengye

Introduction to Stochastic Networks II: Kolmogorov's Criterion for ReversibilityTextbook

A Markov process is reversible when, in equilibrium, transitions from xxx to yyy occur at the same average rate as transitions from yyy to xxx. Algebraically this is the detailed balance condition π(x)q(x,y)=π(y)q(y,x)\pi(x)q(x,y)=\pi(y)q(y,x)π(x)q(x,y)=π(y)q(y,x), and it is the single most useful structural property a network process can have: it replaces a global linear system by one equation per pair of…

6 thms2 active usersReviewed
🏆Completed
AnalysisProbability·Captain: naimengye

Probability Theory and Examples VI: Donsker's TheoremTextbook

The central limit theorem says that Sn/nS_n/\sqrt nSn​/n​ converges to a normal random variable. Donsker's theorem says something much stronger: the whole rescaled path of the random walk converges to the whole path of a Brownian motion, as a random element of C[0,1]C[0,1]C[0,1].

8 thms2 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: naimengye

Probability Theory and Examples III: The Markov Chain Convergence TheoremTextbook

A Markov chain forgets. Run it long enough and the distribution of its position stops depending on where it started — that is the intuition behind shuffling a deck, behind Markov chain Monte Carlo, behind PageRank, and behind the stationary analyses of every queueing model. Chapter 5 of Rick Durrett's Probability: Theory and Examples (Version 5, 2019) makes…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: naimengye

Stochastic Networks VIII: Flow Level Models and the Stability of alpha-Fair AllocationsTextbook

Chapter 7 of Frank Kelly and Elena Yudovina's Stochastic Networks (Cambridge University Press, 2014) studies a network with a fixed set of users, and shows that a decentralized rate control converges to a fair allocation. Chapter 8 asks the question one time scale up. Files finish and their flows leave; new files arrive and new flows appear. The number of…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: naimengye

Stochastic Networks V: Random Access and the Critical Rate of Backoff SchemesTextbook

When many stations share one broadcast channel, something has to decide who transmits. A token passed around the stations works when there are few of them and none is silent for long, but it scales badly and breaks if the token is lost. The alternative is to let stations transmit whenever they like and use randomness to recover from the resulting…

8 thms2 active usersReviewed
🏆Completed
Markov ChainOperations Research·Captain: naimengye

Stochastic Networks I: Erlang's Formula for a Single LinkTextbook

In the early twentieth century Agner Krarup Erlang worked for the Copenhagen Telephone Company and faced a sizing question that every shared-resource operator still faces: how many parallel circuits must a telephone link carry so that an arriving call is almost never turned away? The answer he published — the Erlang loss formula — is still the standard…

9 thms2 active usersReviewed
🏆Completed
Markov ChainOperations Research·Captain: tianyipeng

Markov Entanglement: Index Policies for Restless Bandits are Asymptotically SeparableResearch Paper

Restless multi-armed bandits are the standard model for allocating a scarce resource across many independently-evolving agents: N arms, each a small Markov chain, and a budget that lets you activate only a fixed fraction of them at each step. The joint problem is PSPACE-hard, so practice runs on index policies — score each arm by a priority index computed…

12 thms2 active usersReviewed
🏆Completed
Statistics·Captain: Shuze Chen

Vector Space Methods III: Recursive EstimationTextbook

The final sections of Chapter 4 of Luenberger's Optimization by Vector Space Methods (Wiley, 1969) derive the discrete-time Kalman filter (§4.7 Theorem 1, attributed to Kalman 1960) purely from Hilbert space geometry: the optimal estimate of a linearly evolving random state is an orthogonal projection onto the span of past measurements, and the projection…

4 thms2 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: Shuze Chen

Markov Chains and Mixing Times XIII: Coupling from the PastTextbook

Every sampling guarantee in this series so far is approximate: run the chain for tmix(ε)t_{\mathrm{mix}}(\varepsilon)tmix​(ε) steps and the output is within ε\varepsilonε of stationarity. In 1996 Propp and Wilson showed that, astonishingly, one can often sample exactly from the stationary distribution of a chain — with no error at all and no knowledge of the mixing time —…

5 thms2 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: Shuze Chen

Markov Chains and Mixing Times II: The Convergence TheoremTextbook

The first mission of this series established that an irreducible finite Markov chain has a unique stationary distribution π\piπ. The present mission, covering Chapters 3–4 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009), answers the two questions that make that fact useful. First, the inverse problem of sampling: given a target distribution …

14 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: wenxinzhang

Single-Server Queueing Convergence via Forward CouplingTextbook

Formalize sample-path stability for a continuous-time, unit-rate, infinite-buffer single-server queue. Starting from cumulative arriving service work, define the reflected transient workload, the workload constructed from the infinite past, long-run offered load, and two-time stationarity. Prove that subcritical load forces finite-time coupling and…

5 thms2 active usersReviewed
🏆Completed
Inventory TheoryOperations Research·Captain: Ming Hu

A 1.9321.9321.932 Guarantee for (r,Q)(r,Q)(r,Q) Policies in Continuous-Review Lost-Sales Inventory SystemsResearch Paper

In many retail and spare-parts settings a customer who finds the shelf empty buys elsewhere: unmet demand is lost, not backlogged. When replenishment takes a positive lead time, the state of an optimally managed lost-sales system is the whole pipeline of outstanding orders, and optimal policies are not known in closed form (Zipkin 2008). Practice therefore…

31 thms1 active userReviewed
PreviousPage 13 of 14Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me