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

Maximum Pressure Policies in Stochastic Processing Networks I: Under the EAA Assumption, Maximum Pressure Is Pathwise Stable Whenever the Static Planning LP Has a Feasible Solution with ρ ≤ 1Research Paper

A processing network must decide which activities receive scarce processor capacity while jobs move among buffers. Such decisions matter in manufacturing, service systems, and switches: one activity can consume several processors at once, and a job can be routed to another buffer after processing. A policy that sees current buffer levels but does not need…

10 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

Maximum Pressure Policies in Stochastic Processing Networks III: Strict Leontief Networks Satisfy the Extreme-Allocation-Available (EAA) AssumptionResearch Paper

A stochastic processing network (Harrison 2000) models a system in which processors carry out activities and each activity draws jobs from one or more buffers. Manufacturing lines, call centers with cross-trained agents, and data switches all fit this model. A central question is which scheduling policies are throughput optimal, meaning they stabilize the…

7 thms3 active usersReviewed
Control TheoryOperations ResearchProbability·Captain: mikedeng1

Scheduling a Multi Class Queue with Many Exponential Servers: Asymptotic Optimality in Heavy Traffic: The HJB-Based Preemptive Policy Is Asymptotically Optimal Among Work-Conserving PoliciesResearch Paper

Large call centers route several types of customers to a common pool of agents. When the pool is large and highly utilized, the relevant asymptotic regime is the quality-and-efficiency-driven (QED) or Halfin–Whitt regime (Halfin & Whitt 1981). The number of servers nnn grows while the offered load stays within O(n)O(\sqrt n)O(n​) of nnn. Waiting is then neither…

18 thms3 active usersReviewed
Control TheoryDynamic ProgrammingOperations Research+2·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case IX: Imperfect State Information — Reduction to a Perfect-Information Model through a Statistic Sufficient for ControlTextbook

In most control problems the controller does not see the state of the system. It sees noisy observations, remembers its past controls, and must act on that record. Inventory systems with delayed or inaccurate counts, maintenance of machines whose wear is only inspected, target tracking, and medical treatment planned from test results all have this form. The…

15 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Reversibility and Stochastic Networks IX: Partial Balance — Equivalent Characterizations via Truncation, Rate Changes and Time ReversalTextbook

Equilibrium distributions of Markov models of networks are rarely computed by solving the full equilibrium equations directly. In the classical product-form results (migration processes, Jackson and Kelly networks, loss networks, clustering processes) the equilibrium distribution satisfies a stronger, local family of equations, and that is what makes it…

18 thms3 active users
Control TheoryDynamic ProgrammingOperations Research+1·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case VII: The Finite-Horizon Borel Model — over Universally Measurable Policies J*_K = T^K(J_0)Textbook

Finite-horizon stochastic control on general state and control spaces — inventory levels, queue lengths, positions, beliefs — cannot be written down without measure theory, and the measure theory turns out to be the hard part. The dynamic programming (DP) recursion "start from zero and minimise one stage at a time" is easy to state, but on uncountable…

19 thms3 active usersReviewed
🏆Completed
Graph TheoryMarkov ChainOperations Research+2·Captain: mikedeng1

Reversibility and Stochastic Networks VIII: Markov Fields — A Positive Random Field Is Markov iff It Factorizes over the Simplices of the GraphTextbook

Many systems consist of a finite number of sites whose states influence one another only locally: fruit trees in an orchard that are diseased or healthy, power sources that are working or broken, individuals holding one of several views. Chapter 9 of F. P. Kelly, Reversibility and Stochastic Networks (Wiley, 1979) asks which joint distributions such systems…

8 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchOptimization+1·Captain: mikedeng1

Reversibility and Stochastic Networks V: Optimal Capacity Allocation in a Network of QueuesTextbook

Chapter 4 of F. P. Kelly's Reversibility and Stochastic Networks (Wiley, 1979) applies the product-form theory of Chapter 3 to concrete systems. Two of its results have numbered statements, and they answer two practical questions.

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

Reversibility and Stochastic Networks III: Open Networks of Queues with General Customer Routes Have Product-Form EquilibriumTextbook

Networks of queues model systems in which jobs visit a sequence of service stations: items in a manufacturing job-shop, packets in a communication network, patients moving between hospital departments. The open migration process of Chapter 2 of F. P. Kelly, Reversibility and Stochastic Networks (Wiley, 1979), and the job-shop networks of Jackson (Jackson…

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

Reversibility and Stochastic Networks IV: Symmetric Queues with Gamma-Mixture Service RequirementsTextbook

The classical product-form results for queueing networks (Jackson, Kelly, Baskett–Chandy–Muntz–Palacios) assume exponentially distributed service requirements, because then the state of a queue need not record how much service each customer has received. Real service times are rarely exponential: telephone call lengths, job sizes in time-shared computers…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Stochastic Inventory Control Models 1: The Dual-Balancing Policy Costs at Most Twice the OptimumResearch Paper

Periodic-review inventory control with backorders is one of the basic models of operations research: in each period a manager decides how much to order, orders arrive after a lead time, unmet demand is backlogged at a penalty, and stock left over is charged a holding cost. When demands in different periods are independent, dynamic programming yields an…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Dimensioning Large Call Centers IV: Asymptotically Optimal Staffing under a Waiting-Cost ConstraintResearch Paper

A call center has to decide how many agents to staff. In practice the decision is often posed as a service-level constraint rather than a cost trade-off: use the fewest agents for which the expected waiting cost, or the fraction of customers who wait, stays below a target. Borst, Mandelbaum and Reiman (CWI Report PNA-R0015, 2000; journal version in Operation…

19 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Dimensioning Large Call Centers III: Asymptotically Optimal Staffing in the Quality-Driven RegimeResearch Paper

How many agents should a call center staff? Telephone call centers employ millions of people, and staffing is their largest cost, so the question is asked every half hour of every day (Gans, Koole & Mandelbaum, 2003). The classical model is the M/M/N (Erlang-C) queue: calls arrive at rate λ\lambdaλ, service times are exponential with mean 1/μ1/\mu1/μ, and NNN agents…

25 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Dimensioning Large Call Centers II: Asymptotically Optimal Staffing in the Efficiency-Driven RegimeResearch Paper

A call center must choose enough servers to limit waiting while paying for every server it staffs. When arrivals are heavy, small changes in the number of servers can change the probability of delay substantially. Borst, Mandelbaum, and Reiman study how to make this choice when the arrival rate grows and the costs of staffing and waiting need not grow at…

22 thms3 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchProbability·Captain: mikedeng1

Dynamics of Stochastic Approximation Algorithms 4: Subgaussian Martingale Noise with Σ exp(−c/γ_n) < ∞ for Every c > 0 Satisfies Assumption A1 Almost SurelyResearch Paper

A stochastic approximation algorithm is a recursion

10 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Stochastic Inventory Control Models 2: The Triple-Balancing Policy Costs at Most Three Times the Optimum for Stochastic Lot-SizingResearch Paper

Periodic-review inventory control with a fixed ordering cost is one of the oldest problems in operations research. A firm reviews its stock at the beginning of each of TTT periods, decides whether to place an order, pays a fixed cost KKK for every order it places, and pays holding costs on leftover stock and penalties on unmet (backlogged) demand. When demand…

7 thms3 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchProbability·Captain: mikedeng1

Dynamics of Stochastic Approximation Algorithms 6: An Attractor Whose Basin Meets the Attainable Set Contains the Limit Set with Positive ProbabilityResearch Paper

A stochastic approximation algorithm is a recursion xn+1=xn+γn+1(F(xn)+Un+1)x_{n+1}=x_n+\gamma_{n+1}\big(F(x_n)+U_{n+1}\big)xn+1​=xn​+γn+1​(F(xn​)+Un+1​) with decreasing step sizes γn\gamma_nγn​ and a noise term Un+1U_{n+1}Un+1​. Recursions of this form appear in stochastic gradient methods, adaptive control, learning in games (fictitious play, reinforcement learning) and urn models. The ODE method compares the iterates…

11 thms3 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchProbability·Captain: mikedeng1

Dynamics of Stochastic Approximation Algorithms 3: Martingale Noise with Bounded q-th Moments and Summable γ_n^(1+q/2) Satisfies Assumption A1 Almost SurelyResearch Paper

A stochastic approximation algorithm is a recursion

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

Dynamics of Stochastic Approximation Algorithms 5: If V(Λ) Has Empty Interior for a Lyapunov Function V, Every Internally Chain Transitive Set Lies in ΛResearch Paper

A stochastic approximation algorithm is a recursion xn+1=xn+γn+1(F(xn)+Un+1)x_{n+1}=x_n+\gamma_{n+1}\big(F(x_n)+U_{n+1}\big)xn+1​=xn​+γn+1​(F(xn​)+Un+1​) with decreasing steps γn\gamma_nγn​ and noise UnU_nUn​. Stochastic gradient descent, the Robbins–Monro procedure, reinforcement-learning updates and learning dynamics in games all have this form. The ODE method compares such a recursion with the deterministic dynamics …

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

Open Queueing Networks in Heavy Traffic: Reflected Brownian Motion Limit for the Queue Length ProcessResearch Paper

Open networks of single-server queues with general interarrival and service distributions are the standard model of job shops, communication networks and service systems. Outside the product-form (Jackson) case their queue-length distributions are not known in closed form. When every station is close to saturation, a heavy-traffic limit replaces the network…

18 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Quantifying the Bullwhip Effect in a Simple Supply Chain: The Impact of Forecasting, Lead Times, and Information 1: Centralizing Demand Information Does Not Eliminate the Bullwhip EffectResearch Paper

The bullwhip effect is the observation that the variability of orders increases as one moves up a supply chain, from the retailer towards the manufacturer and its suppliers. It was documented in industry and in classroom experiments such as the Beer Game (Sterman 1989), and analysed by Lee, Padmanabhan and Whang (1997), who named demand forecasting, lead…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

An Efficient Algorithm for Computing an Optimal (r, Q) Policy in Continuous Review Stochastic Inventory Systems: Algorithm OPT Returns an Optimal Reorder Point and Order QuantityResearch Paper

(r, Q) policies are the standard replenishment rule for a single item under continuous review: whenever the inventory position (stock on hand plus on order minus backorders) drops to the reorder point rrr, an order of size QQQ is placed. They are known to be optimal in the classical models with Poisson or compound renewal demand, constant or exogenous lead…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Dimensioning Large Call Centers I: The Rationalized Staffing Function Is Asymptotically OptimalResearch Paper

A call center with NNN agents facing Poisson arrivals at rate λ\lambdaλ and exponential service at rate μ\muμ is the M/M/N (Erlang-C) queue. Choosing NNN trades the cost of agents against the cost of customers waiting, and in practice it is done with the square-root safety-staffing rule N≈R+yRN \approx R + y\sqrt RN≈R+yR​, where R=λ/μR = \lambda/\muR=λ/μ is the offered load. Borst,…

22 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Fundamentals of Queueing Theory IX: Kingman's Upper Bound on the G/G/1 Queue WaitTextbook

The single-server queue with general independent interarrival and service times, the G/G/1 queue, is the basic model of a congested resource: a machine, a link, a checkout. For Markovian arrivals or services the mean wait has a closed form (the Pollaczek–Khintchine formula for M/G/1, the geometric law for G/M/1). For general distributions it has none, and…

10 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

Optimization of Multiclass Queueing Networks: Polyhedral and Nonlinear Characterizations of Achievable Performance II: An O(n²) Extended Formulation of the Multiclass M/M/1 Performance PolymatroidResearch Paper

A single server shared by several classes of customers is the basic model of scheduling under uncertainty: jobs of different types arrive at random, need random amounts of work, and a scheduler decides at every moment which type to serve. A classical way to optimize such a system, the achievable region approach, describes the set of all performance vectors…

5 thms3 active usersReviewed
PreviousPage 11 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