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
Probability·Captain: WillR

Kyprianou (2006), Chapter 3: More Distributional and Path-Related PropertiesTextbook

Levy processes are continuous-time models with stationary independent increments that allow both diffusion and jumps. The structure developed by Andreas E. Kyprianou in Chapter 3 of his 2006 textbook is used in fluctuation theory, first-passage calculations, storage models, and insurance ruin models. The chapter starts with the behaviour of paths at random…

117 thms4 active usersReviewed
Computational ComplexityQuantum Information·Captain: iris

Quantum algorithms for stochastic nonlinear differential equationsResearch Paper

Fault-tolerant quantum computers are usually discussed for problems that are hard for classical computers in the absence of any noise. Bravyi, Byrne, Zayats, Zhuk and Zlokapa (arXiv:2606.08349) study a different role for noise: random perturbations of the problem rather than of the hardware. Their example is the estimation of an observable at the final time…

38 thms4 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: Shuze Chen

Bayesian Optimal Stopping: Invincible Prophets and Achievable PhilosophersResearch Paper

In a prophet inequality a decision-maker sees rewards X1,…,XnX_1,\dots,X_nX1​,…,Xn​ one at a time, must accept or reject each on arrival, and may accept only one. The classical theory assumes the distributions are known and compares an online rule with the offline maximum OFF=E[max⁡tXt]\mathrm{OFF}=\mathbb E[\max_tX_t]OFF=E[maxt​Xt​] (Samuel-Cahn 1984, Correa et al. 2017). In many applications the…

19 thms4 active usersReviewed
Operations ResearchProbability·Captain: iris

Processing Networks XV: A State-Dependent Foster–Lyapunov Drift Condition Implies Positive Recurrence of a Discrete-Time Markov ChainTextbook

Stability of a stochastic processing network (a queueing network, a switch, a wireless scheduler) is usually proved by representing the network as a Markov chain on a countable state space and showing that the chain is positive recurrent: every state is revisited after a finite expected time. Dai and Harrison's Processing Networks: Fluid Models and Stability…

10 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: iris

Cloud Cost Optimization: Model, Bounds, and Asymptotics: The Newsvendor Policy π* Has Optimality Gap at Most √θ Times the Bound (14), So It Is Asymptotically Optimal as Demand Scales by θResearch Paper

Cloud providers sell computing capacity in two ways: reserved resources, paid for every period whether used or not, and on-demand resources, rented one period at a time at a higher price. A firm that runs a stream of computing jobs with deadlines must decide how much capacity to reserve once, how much to rent each period, and which job runs on which…

48 thms4 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability+1·Captain: iris

Regret Analysis of a Markov Policy Gradient Algorithm for Multiarm Bandits: SAMBA Converges to the Optimal Arm Almost Surely with Regret at Most NαΔlog⁡T+Q\frac{N}{\alpha\Delta}\log T + QαΔN​logT+QResearch Paper

Policy-gradient methods adjust the probabilities with which a learner picks actions by following an estimated gradient of its expected reward. They underlie much of modern reinforcement learning (Williams 1992; Sutton–Barto 2018), yet regret guarantees for them are scarce even in the simplest setting, the stochastic multi-armed bandit, where the benchmark…

24 thms4 active usersReviewed
Dynamic ProgrammingOperations ResearchProbability·Captain: iris

Risk Averse Stochastic Programming: Time Consistency and Optimal Stopping: The Nested-Risk Snell Envelope Is the Optimal Stopping Value, Attained by the First Time It Meets the RewardResearch Paper

Optimal stopping asks when to stop a reward process Z0,…,ZTZ_0,\dots,Z_TZ0​,…,ZT​ so as to make the stopped reward ZτZ_\tauZτ​ as large as possible. In its classical form the criterion is the expectation E[Zτ]\mathbb E[Z_\tau]E[Zτ​], and the solution is the Snell envelope: the value process obtained by comparing, at each date, the reward for stopping now with the conditional expectation…

22 thms4 active usersReviewed
Operations ResearchProbability·Captain: iris

Heavy-Traffic Universality of Redundancy Systems with Assignment Constraints: The Scaled Stationary Job Counts Collapse onto One Exponential Variable Times the Critical Arrival ProportionsResearch Paper

Parallel-server systems in data centres cannot send every job everywhere: data locality and license restrictions tie each job to a subset of the servers. Redundancy scheduling copes with this by replicating a job to all of its compatible servers. Under cancel-on-completion (c.o.c.) the other replicas are discarded when the first one finishes; under cancel-on…

54 thms4 active usersReviewed
Algorithmic Game TheoryControl TheoryProbability+1·Captain: iris

Exploration Noise for Learning Linear-Quadratic Mean Field Games: With Common Noise, the Tilted Geometric Fictitious Play Converges to the Equilibrium at Rate ϖ−nexp⁡(C/ε2)\varpi^{-n}\exp(C/\varepsilon^2)ϖ−nexp(C/ε2)Research Paper

A mean field game (MFG) describes a continuum of identical players, each controlling its own state and paying a cost that depends on the statistical distribution of the population. An equilibrium is a population flow that is reproduced when every player best responds to it. Computing equilibria is the central numerical question of the field, and fictitious…

16 thms4 active usersReviewed
Markov ChainOperations ResearchProbability·Captain: iris

Stability of Parallel Server Systems: if jobs that find all servers busy go to the second-shortest queue with probability p, the system is unstable for every ρ ≥ V_cr(p)Research Paper

A parallel-server system has sss identical servers, each with its own queue, and a dispatcher that sends every arriving job to one of them. With Poisson arrivals of rate λ\lambdaλ and exponential services of rate μ\muμ, the traffic intensity is ρ=λ/(sμ)\rho=\lambda/(s\mu)ρ=λ/(sμ), and ρ<1\rho<1ρ<1 is necessary for any dispatcher to keep the queues finite. For the classical policies —…

14 thms4 active usersReviewed
Operations ResearchProbability·Captain: iris

Appointment Scheduling for Multiple Servers: the phase-type recursion gives the exact waiting-time and makespan laws and the cost of every schedule of the D/PH/s appointment systemResearch Paper

An appointment schedule fixes in advance when each of nnn clients should arrive for a service of random length. Clinics, MRI suites, legal counselling and visa offices all use one, and the schedule trades off clients' waiting time against the idle time and overtime of the servers. Pooling physicians or machines so that any client can be served by any of sss serv…

46 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: Shuze Chen

Markov Decision Processes (Puterman) VIII: Average Optimality for Semi-Markov ModelsTextbook

A controller may make decisions whenever a machine fails, a customer arrives, or a service finishes. The time between two decisions then depends on the state and the chosen action. Counting decisions alone does not measure elapsed operating time: a policy earning a large reward per decision may spend so long between decisions that its reward per unit time…

7 thms4 active usersReviewed
🏆Completed
AnalysisProbability·Captain: WillR

Feynman–Kac Formula: Diffusion PDE Representation and UniquenessTextbook

The Feynman–Kac formula links solutions of parabolic partial differential equations to expectations of functionals of diffusion processes. It provides the probabilistic meaning of a differential equation containing drift, diffusion, discounting and a source term. The Feynman–Kac article presents the one-dimensional terminal-value formula and a martingale…

45 thms4 active usersReviewed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Lyapunov Conditions for Differentiability of Markov Chain Expectations: Differentiability of Random-Horizon Discounted ExpectationsResearch Paper

Many performance measures of stochastic models in operations research are expectations computed along a Markov chain until a random time. Examples are the expected discounted cost until a queue empties, the expected reward until a system enters a failure set, and the price of a claim that pays at a hitting time. When the transition law depends on a…

11 thms4 active usersReviewed
Control TheoryOperations ResearchProbability·Captain: mikedeng1

Stationary Discounted and Ergodic Mean Field Games with Singular Controls: The Discounted Equilibria and Their Rescaled Values Converge to the Ergodic Equilibrium as the Discount Rate VanishesResearch Paper

Firms invest to raise their productivity, investment is irreversible, and the return on productivity depends on what the rest of the market does. Cao, Dianetti and Ferrari model this as a stationary mean field game (MFG) of singular control: a representative firm controls a one-dimensional diffusion through a nondecreasing investment process. Its running…

19 thms4 active usersReviewed
Operations ResearchProbability·Captain: mikedeng1

To Pool or Not to Pool: Queueing Design for Large-Scale Service Systems: In Moderate Overload, Dedicated Queues Under JSQ Match Pooled Abandonment While Their Delay Probability Stays Below OneResearch Paper

Large service systems (call centers, hospital wards, emergency departments) must decide how customers wait. In a pooled queue (PQ) all customers wait in one line served by nnn agents; in dedicated queues (DQ) each server has its own line, which is what physical layouts, server-specific information and accountability often force. Classical queueing theory says…

18 thms4 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Tail-Optimized Caching for LLM Inference: Expected-Tail-Optimized LRU Is an Optimal Online Caching Policy for Tail Excess Latency in the Stochastic Conversation ModelResearch Paper

A large language model serving a multi-turn conversation re-reads the whole conversation history at every turn. The intermediate attention state of that history, the KV cache, can be stored in GPU memory and reused, so that only the uncached part of the prompt must be recomputed before the first output token appears. GPU memory is scarce, so a server must…

8 thms4 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability·Captain: Shuze Chen

Stochastic Networks X: Stationary Open Migration Processes Under Time ReversalTextbook

A network of queues records both how many customers occupy each location and how they move between locations. These are different kinds of information. A simple distribution for the occupancies at one time need not make the arrival streams simple, or make the queues independent over time. Open migration processes provide a setting in which the distinction…

10 thms4 active usersReviewed
Operations ResearchProbability·Captain: mikedeng1

On the SRPT Scheduling Discipline in Many-Server Queues with Impatient Customers: In the Overloaded Many-Server Limit, SRPT Serves Short Jobs Without Waiting While Long Jobs AbandonResearch Paper

Shortest remaining processing time first (SRPT) is the scheduling rule that always works on the jobs closest to completion. For a single server it minimizes the number of jobs in the system at every time, on every sample path (Schrage 1968). Service systems with many parallel servers and customers who leave when they wait too long, such as call centers,…

11 thms4 active usersReviewed
EconomicsProbability·Captain: mikedeng1

Incomplete Information, Debt Issuance, and the Term Structure of Credit Spreads: Once Debt Capacity Is Exhausted, Creditors Face a Jump-to-Default Intensity Given in Closed Form by Equation (32)Research Paper

Creditors can observe a firm's liabilities while learning its asset value only after a delay. In the model of Benzoni, Garlappi, and Goldstein, this gap matters when the firm has exhausted its ability to issue more debt: creditors know that the firm has stayed above its default boundary, but do not know how close it is to that boundary now. Even though…

9 thms4 active usersReviewed
🏆Completed
Linear algebraMarkov ChainNumerical Analysis+2·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling VII: G, U and R as Minimal Nonnegative SolutionsTextbook

A quasi-birth-and-death process (QBD) is the Markov chain behind queues with phase-type service or arrivals, priority queues, and many models of telecommunication and inventory systems: a level that moves up or down by at most one per step, and a phase that carries the rest of the state. Its stationary distribution is determined by three matrices indexed by…

19 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: Shuze Chen

Average Cost Markov Decision Processes with Weakly Continuous Transition Probabilities: Assumptions (W*) and (B̲) Give the Average Cost Optimality Inequality and a Stationary Optimal PolicyResearch Paper

A Markov decision process (MDP) with the average cost per unit time criterion models a controller who runs a stochastic system indefinitely and cares about long-run cost rather than any finite horizon: inventory control, queueing control, and maintenance are standard examples. The basic questions are whether an optimal policy exists, whether it can be taken …

15 thms4 active usersReviewed
Control TheoryOperations ResearchProbability·Captain: mikedeng1

On System-Wide Safety Staffing of Large-Scale Parallel Server Networks: Positive SWSS Makes the Limiting Diffusion Exponentially Ergodic, Negative SWSS Makes It Transient Under Every Markov ControlResearch Paper

Large service systems such as call centres, hospital wards and cloud server farms route several customer classes to several server pools, with each pool trained for only some of the classes. Staffing such a network sits between two failure modes: too few servers make queues explode, and too many waste capacity. In the Halfin–Whitt (quality-and-efficiency-dri…

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

We Are on the Way: Analysis of On-Demand Ride-Hailing Systems: In the One-Direction Approximation, the No-Call Mechanism Never Has a Longer Average Waiting Time Than the Call MechanismResearch Paper

On-demand ride-hailing platforms replaced street-hailing on the promise that matching a passenger to a car at the moment of the request shortens the wait. Feng, Kong and Wang (SSRN 2960991, later published in Manufacturing & Service Operations Management, doi:10.1287/msom.2020.0880) ask whether that is true in a stylized model and find that it need not be:…

14 thms4 active users
🏆Completed
EconomicsOperations ResearchProbability·Captain: mikedeng1

Providing Data Samples for Free: Free Samples Strictly Beat Selling in One Round When the Seller-Side Drift of the Buyer's Bayes Risk Is Initially PositiveResearch Paper

Firms that own data increasingly sell it as a product: market research panels, consulting reports, datasets for training demand models. A common commercial practice is to hand out a free sample of the data before quoting a price for the rest. Under standard Bayesian reasoning this practice looks self-defeating. Every free data point reduces the buyer's…

16 thms4 active users
PreviousPage 3 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