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
Operations ResearchProbability·Captain: mikedeng1

Revenue Management Without Forecasting or Optimization: An Adaptive Algorithm for Determining Airline Seat Protection Levels: Fill-Event Updates Converge to the Optimal Protection LevelsResearch Paper

Airlines sell seats on a single flight in several fare classes. Discount classes book first, so the carrier must decide how many seats to protect for later, higher-paying passengers. The classical answer, from Littlewood's rule for two classes to the nested optimality conditions of Brumelle and McGill (1993), computes optimal protection levels from a…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Understanding the Efficiency of Multi-Server Service Systems I: With Poisson Arrivals and Finitely Many Service-Time Values of Mean 1, the Number of Busy Servers in M/G/∞ Is Poisson(λ)Research Paper

Call centers, hospital wards, telephone exchanges and server farms all face the same staffing question: given an arrival rate λ\lambdaλ, how many servers sss are needed to keep congestion at a fixed level? A widely used answer is the square-root staffing rule

9 thms4 active usersReviewed
🏆Completed
AnalysisOperations Research·Captain: mikedeng1

The G/GI/N Queue in the Halfin–Whitt Regime 1: The Regulator Equation z(t) = x(t) + ∫₀ᵗ (z(t−s)+a)⁺ dB(s) Has a Unique Càdlàg Solution, Lipschitz on Bounded Intervals and Measurable in xResearch Paper

The G/GI/NG/GI/NG/GI/N queue has NNN identical servers, a general arrival process, and independent service times with a common distribution FFF. In the Halfin–Whitt regime the number of servers and the offered load grow together, so that the fraction of delayed customers stays strictly between 000 and 111. This is the standard asymptotic model of large call centers and service…

13 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Stochastic Inequalities on Partially Ordered Spaces 3: Ornstein's d̄-Distance of Stationary Real Processes Equals ∫ω⁰dP + ∫ω⁰dQ − 2 sup{∫ω⁰dR : R ≺ P, R ≺ Q}Research Paper

Two stationary random sequences can have identical distributions at each individual time while differing in their dependence across time. Comparing only their one-time marginals therefore misses a feature relevant to stochastic-process comparison. Ornstein's dˉ\bar ddˉ measures the cost of matching two whole stationary processes: it minimizes the expected…

16 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Shock Models and Wear Processes II: If the Probabilities of Surviving k Shocks Have Decreasing Successive Ratios, the Poisson Shock Life Distribution Is IHRResearch Paper

A component may be exposed to shocks that arrive at random times. Its chance of lasting for a given time depends both on how often shocks arrive and on how likely it is to survive successive shocks. Reliability calculations often begin with the latter, discrete sequence, while replacement and life-testing questions concern the resulting lifetime…

8 thms4 active usersReviewed
🏆Completed
Probability·Captain: mikedeng1

Random Walks in a Random Environment 4: For Z_n = σ_n(1 + Z_{n−1}) with i.i.d. σ_n ≥ 0, (Z_1 + ⋯ + Z_n)/n → Eσ/(1 − Eσ) a.s. if Eσ < 1, and → ∞ if Eσ ≥ 1Research Paper

A random walk in a random environment on Z\mathbb ZZ moves one step right with probability αx\alpha_xαx​ and one step left with probability 1−αx1-\alpha_x1−αx​ from site xxx, where the αx\alpha_xαx​ are themselves i.i.d. random variables. In his 1975 paper, F. Solomon (Ann. Probab. 3(1):1–31, DOI 10.1214/aop/1176996444) decided recurrence and transience of this walk and computed…

9 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Renewal Theory and Its Ramifications: The Elementary Renewal Theorem H(t)/t → 1/μ₁ as t → ∞, Including the Case μ₁ = ∞Research Paper

A renewal process models the successive replacements of an article that fails and is replaced at once: light bulbs, machine components, the inter-arrival times of a queue. The central quantity is the renewal function H(t)H(t)H(t), the expected number of replacements up to time ttt. Long-run average costs of maintenance and inventory policies, the throughput of…

8 thms4 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchProbability·Captain: mikedeng1

Subadditive Ergodic Theory 3: A Separable Continuous-Parameter Subadditive Process with E(Ω_I) < ∞ Has x₀ₜ/t → ξ with Probability One and in Mean, E(ξ) = γResearch Paper

Many random growth models attach a cost, distance, or accumulated quantity to each time interval. If the quantity over a long interval is at most the sum over two adjacent intervals, it is subadditive. A stable rate over long intervals is useful even when the underlying random system does not have a simple independent-increment description. Kingman's 1973…

8 thms4 active usersReviewed
🏆Completed
CombinatoricsMarkov ChainProbability·Captain: mikedeng1

On the Generalized “Birth-and-Death” Process 2: For Constant Rates λ₀ ≤ μ₀ the Cumulative Population M_∞ Has Law Q_M = ((λ₀+μ₀)/2λ₀)(2M)! x^M/(2^{2M}(M!)²(2M−1))Research Paper

A birth-and-death process describes a population in which each individual independently gives birth and dies at given rates. Kendall's 1948 paper (doi:10.1214/aoms/1177730285) solved the process with arbitrary time-dependent rates and, in its §4, introduced a second random variable alongside the population size: the cumulative population MtM_tMt​, the number of…

5 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

Maximum Pressure Policies in Stochastic Processing Networks IV: In Reversed Leontief Networks Extreme Allocations Are Integral and Maximum Pressure Separates by ProcessorResearch Paper

Maximum pressure policies schedule a stochastic processing network by choosing, at each decision time, an allocation of processors to activities that maximizes a linear "pressure" built from the current buffer levels and the network's input-output matrix. Dai and Lin (Oper. Res. 53(2), 2005) prove that such policies are throughput optimal: they stabilize…

7 thms4 active usersReviewed
🏆Completed
Control TheoryOperations Research·Captain: mikedeng1

Maximum Pressure Policies in Stochastic Processing Networks II: Under Assumptions 1 and 2, the Maximum Pressure Fluid Model Empties in Finite Time When the Static Planning LP Has ρ < 1Research Paper

Stochastic processing networks (Harrison 2000) model manufacturing lines, data switches, call centers and multiclass queueing networks in one framework: jobs wait in buffers, activities process jobs from one or several buffers at once, each activity may need several processors simultaneously, and routing after service may depend on the activity used. A…

10 thms4 active usersReviewed
🏆Completed
Dynamical SystemsOperations Research·Captain: mikedeng1

Stability and Instability of Fluid Models for Reentrant Lines 1: Every Work-Conserving Fluid Model of the Three-Buffer Line 1→2→1 Is Stable When m₁ + m₃ < 1 and m₂ < 1Research Paper

A reentrant line is a queueing network in which every job follows the same route and visits some stations more than once. It is the standard model of a semiconductor wafer fab, where a wafer returns to the same lithography station for each of its layers (Kumar, Re-entrant lines, Queueing Systems 13, 1993). Because jobs at different stages compete for the…

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

On the Stochastic Matrices Associated with Certain Queuing Processes 2: The GI/M/1 Imbedded Chain Is Ergodic iff ρ < 1 and Recurrent iff ρ ≤ 1Research Paper

A single-server queue in which customers arrive according to a renewal process and are served in exponentially distributed times is the system GI/M/1. Observed just before successive arrivals, its queue length is a Markov chain on {0,1,2,… }\{0, 1, 2, \dots\}{0,1,2,…}, the imbedded chain introduced by D. G. Kendall (Kendall 1953, Ann. Math. Statist. 24, pp. 338–354). Whether…

12 thms4 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Reversibility and Stochastic Networks VII: Clustering Processes — Poisson Product-Form Equilibrium of the Open Clustering ProcessTextbook

Many systems consist of units that form themselves into clusters: individuals at a gathering forming conversational groups, monomers forming polymers, particles coagulating and fragmenting. Chapter 8 of F. P. Kelly, Reversibility and Stochastic Networks (Wiley, 1979) treats such clustering processes as Markov processes whose state counts the clusters of…

8 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

A Characterization of Waiting Time Performance Realizable by Single-Server Queues: The Conservation-Law Polytope Is the Convex Hull of the Preemptive Priority VectorsResearch Paper

A single server shared by several classes of jobs must decide, at every moment, which class to serve. Different scheduling rules give different mean response times to the classes, and a system designer often starts from the other end: a target vector of mean response times, one per class, and the question whether any rule can meet it. Coffman and Mitrani…

32 thms4 active users
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems III: Approximating Sequences for the Discounted Cost CriterionTextbook

Optimal control of queueing systems leads to Markov decision problems whose state space is countably infinite (buffer contents, numbers of customers) and whose costs are unbounded (holding costs grow with the queue). Such a problem cannot be solved on a computer as it stands. The standard remedy is to truncate: solve a finite problem on the states …

12 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: Shuze Chen

Processing Networks VIII: Maximal Stability of Back-Pressure ControlTextbook

Every stability result up through mission VII proves that a particular control policy — a fixed priority list, HLSPS, a policy tailored to one network's topology — keeps a specific processing network stable throughout its subcritical region. None of them answer a more practical question a system designer actually faces: given an arbitrary Leontief network…

14 thms4 active usersReviewed
🏆Completed
Probability·Captain: mikedeng1

Markov Processes: Characterization and Convergence VII: Strong approximation of independent sumsTextbook

A sum of independent random increments is a basic model for accumulated noise. A continuous Gaussian process offers a different description of that noise, one that can be studied at every nonnegative time. To compare their individual trajectories, both objects must live on the same probability space. The question is whether their paths can remain close over…

29 thms4 active usersReviewed
🏆Completed
Control TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

Resource Allocation and Cross-Layer Control in Wireless Networks I: The Network Layer Capacity RegionTextbook

Every wireless network control algorithm — routing, scheduling, power control, admission control — is ultimately judged against one question: which traffic loads can it keep stable? Answering that question requires a precise, algorithm-independent notion of queueing stability under random arrivals and a randomly time-varying, possibly non-ergodic-looking…

8 thms4 active users
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Stochastic Orders I: The Usual Stochastic Order and Its Coupling CharacterizationTextbook

Operations research and applied probability are full of questions of the shape "is X riskier, larger, or later than Y?" when X and Y are random: two queueing disciplines' waiting times, two inventory policies' shortfall, two insurance portfolios' claim size. Comparing their means answers a weaker question than the modeler usually wants, since two…

13 thms4 active users
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Stochastic Orders IX: The PQD and Supermodular OrdersTextbook

The first eight chapters of Shaked and Shanthikumar's Stochastic Orders (Springer, 2007) compare single random variables — location, variability, convexity. Chapter IX turns to a different question: given two coordinates of a random vector, how strongly do they tend to move together? "Large values of X1X_1X1​ go with large values of X2X_2X2​" is a qualitative…

5 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Stochastic Orders V: The Laplace Transform OrderTextbook

Many of the orders in Shaked and Shanthikumar's Stochastic Orders (Springer, 2007) are built by fixing a class of test functions φ\varphiφ and declaring X≤YX \le YX≤Y whenever E[φ(X)]≤E[φ(Y)]E[\varphi(X)] \le E[\varphi(Y)]E[φ(X)]≤E[φ(Y)] for every φ\varphiφ in that class: all increasing functions give the usual stochastic order, all convex functions give the convex order. This mission formalizes…

8 thms4 active usersReviewed
🏆Completed
AnalysisProbability·Captain: naimengye

Probability Theory and Examples V: Blumenthal's 0-1 Law and the Local Behaviour of Brownian PathsTextbook

A Brownian path is continuous, and that is essentially all it is. It has no derivative anywhere, it crosses zero infinitely often in every interval (0,ϵ)(0,\epsilon)(0,ϵ), and it becomes positive and negative immediately after time zero. None of this is visible from the finite-dimensional distributions; it is a statement about the germ of the path at a point, and the…

9 thms4 active usersReviewed
🏆Completed
Markov ChainOperations Research·Captain: naimengye

Stochastic Networks III: Loss Networks and the Erlang Fixed PointTextbook

Erlang's formula, the subject of mission I of this series, sizes a single telephone link. Real networks are not single links: a call occupies a circuit on every link of its route simultaneously, and it is lost unless every one of those links has a free circuit. That is the loss network, the model of Chapter 3 of Frank Kelly and Elena Yudovina's Stochastic…

16 thms4 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: Shuze Chen

Markov Chains and Mixing Times VIII: Path Coupling and Approximate CountingTextbook

The coupling method of Mission III asks for a coupling of two copies of a chain from every pair of starting states — often painful to construct globally. Chapter 14 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) replaces that global demand by a local one. The path coupling technique of Bubley and Dyer says: put a connected graph structure…

9 thms4 active usersReviewed
PreviousPage 3 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