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
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
Algorithmic Game TheoryDynamical SystemsProbability·Captain: mikedeng1

On the Global Convergence of Stochastic Fictitious Play III: Almost Sure Convergence to Linearly Stable Rest Points in Potential GamesResearch Paper

Stochastic fictitious play is a basic model of learning in repeated games. Each period every player best responds to the empirical frequencies of the opponents' past play, after the player's payoffs have been hit by a fresh random shock. It was introduced by Fudenberg and Kreps (1993), is a standard object in the theory of learning in games (Fudenberg and…

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

Weak Convergence and Optimal Scaling of Random Walk Metropolis Algorithms: Langevin Diffusion Limit of the First CoordinateResearch Paper

The random walk Metropolis algorithm is one of the most widely used Markov chain Monte Carlo methods for sampling from a density known up to a constant. Its one tuning parameter is the variance of the Gaussian proposal. If the variance is too small, the chain accepts almost every move but barely moves. If it is too large, it proposes long jumps that are…

15 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
🏆Completed
Markov ChainProbability·Captain: Shuze Chen

Markov Chains and Mixing Times VI: Networks, Hitting Times, and Cover TimesTextbook

A reversible Markov chain is an electrical network: states are nodes, and the conductance c(x,y)=π(x)P(x,y)c(x,y)=\pi(x)P(x,y)c(x,y)=π(x)P(x,y) turns hitting probabilities into voltages and hitting times into resistances. This dictionary, going back to Kakutani and popularized by Doyle and Snell, converts probabilistic estimates into the physical laws of circuits — series/parallel…

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

Markov Chains and Mixing Times I: Existence and Uniqueness of the Stationary DistributionTextbook

Finite Markov chains are the basic model for memoryless random dynamics: card shuffles, random walks on graphs and groups, Monte Carlo samplers, and queueing systems are all chains on a finite state space. The single most used fact about them is that an irreducible chain has exactly one stationary distribution — a probability vector π\piπ with π=πP\pi = \pi Pπ=πP —…

20 thms4 active usersReviewed
AnalysisMachine LearningProbability·Captain: Shuze Chen

Error accumulation in reverse diffusion with an imperfect score: beyond path-space analysesResearch Paper

Diffusion models generate samples from a data distribution ppp on Rd\mathbb R^dRd by running a stochastic differential equation backwards in time. The drift of the backward equation involves the score ∇log⁡pt\nabla\log p_t∇logpt​ of the noised data distribution, which is not known and is replaced by a neural-network estimate s^\hat ss^ trained by a squared loss. The standard…

18 thms3 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

The Minimum Bucket Capacity for Reliable Path ORAMResearch Paper

Oblivious RAM lets a client store data on an untrusted server and read and write it without revealing which locations it touches. Path ORAM (Stefanov, van Dijk, Shi, Chan, Fletcher, Ren, Yu and Devadas, 2013/2018), implemented for example in the ZeroTrace and Oblix systems, is the simplest practical construction: blocks live in a binary tree of buckets,…

25 thms3 active usersReviewed
Dynamic ProgrammingOperations ResearchTheoretical Computer Science·Captain: iris

Near-Optimal Adaptive Policies for Serving Stochastically Departing Customers: A Deterministic Quasi-Polynomial-Time Algorithm Computes a (1−ϵ)(1-\epsilon)(1−ϵ)-Optimal Adaptive Service PolicyResearch Paper

Providing timely service under high capacity utilization is a central issue in stochastic systems, and customer impatience has major economic consequences in data centers, healthcare, ride-hailing and call centers (Wang, Li, Jiang, 2010). Cygan, Englert, Gupta, Mucha and Sankowski (ITCS 2013) introduced one of the structurally simplest models of it: a…

24 thms3 active usersReviewed
Control TheoryOperations ResearchProbability·Captain: iris

The Exact Online Threshold for the Asymmetric Binary PerceptronResearch Paper

The asymmetric binary perceptron (ABP) is a random constraint satisfaction problem. Given a matrix G∈RM×NG\in\mathbb R^{M\times N}G∈RM×N with independent standard Gaussian entries and a margin κ∈R\kappa\in\mathbb Rκ∈R, one asks for a sign vector σ∈{±1}N\sigma\in\{\pm1\}^Nσ∈{±1}N with Gσ/N≥κ1MG\sigma/\sqrt N\ge\kappa\mathbf 1_MGσ/N​≥κ1M​ coordinatewise. When M/N→αM/N\to\alphaM/N→α, the largest density at which a…

36 thms3 active usersReviewed
Dynamic ProgrammingProbability·Captain: iris

On Strategic Measures and Optimality Properties in Discrete-Time Stochastic Control with Universally Measurable Policies: lower semianalytic optimal value and everywhere ε-optimal policiesResearch Paper

A discrete-time stochastic control problem (a Markov decision process, MDP) on general state and action spaces asks for a policy that minimizes some criterion of the random trajectory it generates. Once the state space is uncountable, measurability decides whether the problem is well posed at all. The optimal value may fail to be Borel measurable even when…

22 thms3 active usersReviewed
Markov ChainProbabilityTheoretical Computer Science·Captain: iris

Nearly-Optimal Time-Sample Trade-off in Consensus DynamicsResearch Paper

Consensus dynamics are simple local update rules by which the nodes of a network repeatedly revise their opinions until all of them agree. They model collective decision making and serve as lightweight distributed algorithms: a node keeps no state beyond its current opinion. In the synchronous PULL(hhh) model on nnn fully connected nodes, every node samples hhh no…

23 thms3 active usersReviewed
Graph TheoryMarkov ChainProbability+1·Captain: iris

Temporal Conductance and Bounds on the Voter Model for Dynamic NetworksResearch Paper

The voter model is one of the basic models of opinion dynamics and of distributed consensus: every vertex of a network holds an opinion and repeatedly copies the opinion of a random neighbour, until all vertices agree. How long this takes is the consensus time. On a fixed graph it is governed by the graph's conductance: Berenbrink, Giakkoupis, Kermarrec and…

26 thms3 active usersReviewed
Control TheoryDynamic ProgrammingOperations Research·Captain: iris

Condition-Based Production for Stochastically Deteriorating Systems: Optimal Policies and Learning: The Optimal Production Rate Decreases in Deterioration, Time to Maintenance and Base RateResearch Paper

Production systems such as wind turbines and assembly equipment can often be run faster or slower, and running faster usually wears them out faster. Between scheduled maintenance visits, an operator can therefore trade revenue now against deterioration later. Condition-based production, a term coined by Uit het Broek et al. (2020), makes this trade-off…

16 thms3 active usersReviewed
Control TheoryOperations ResearchProbability·Captain: iris

Managing Customer Churn via Service Mode Control: A Myopic-or-Sandwich Interval Policy Is Optimal Among All Admissible Service-Mode ControlsResearch Paper

Subscription businesses, online platforms and service providers lose revenue when customers leave, and the marketing literature models churn as a hazard driven by the customer's state, for instance through logit hazard functions (Rust, Lemon and Zeithaml, Return on marketing: Using customer equity to focus marketing strategy, Journal of Marketing 68(1),…

25 thms3 active usersReviewed
Dynamic ProgrammingOperations ResearchProbability·Captain: iris

Constant Regret Resolving Heuristics for Price-Based Revenue Management: Under Limited Inventory the Resolving Heuristic Earns Within a Horizon-Independent Constant of the Optimal Pricing PolicyResearch Paper

Price-based revenue management studies a seller with a fixed stock of a product and a finite selling season who adjusts prices over time to maximize expected revenue. The exact optimal policy solves a dynamic program whose state is the remaining inventory and time; it is rarely computed in practice, and the network version with many products and resources…

16 thms3 active usersReviewed
Linear OptimizationOperations ResearchProbability·Captain: iris

Understanding the Value of Fulfillment Flexibility in an Online Retailing Environment: A Spillover Limit Policy Costs at Most (1+O(T−1/2))(1 + O(T^{-1/2}))(1+O(T−1/2)) Times the DLP Lower BoundResearch Paper

An online retailer stores each product in several distribution centers (DCs) and tries to ship every order from the DC next to the customer. When that DC has run out, the order can often be shipped from another DC, at a higher cost and with a longer delivery time, and some customers then walk away. Allowing such spillover is the fulfillment flexibility of…

17 thms3 active usersReviewed
PreviousPage 5 of 26Next

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