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

Implicit Renewal Theory and Tails of Solutions of Random Equations 3: Rate of Approach — t^κP(R > t) Equals C₊ Minus a Contour Integral Plus O(t^{−β/2})Research Paper

Random equations of the form R=LΨ(R)R \overset{\mathcal L}{=} \Psi(R)R=LΨ(R), with Ψ\PsiΨ a random function independent of RRR, describe the stationary laws of many stochastic recursions: perpetuities in insurance and finance, the stationary law of ARCH-type volatility models, random difference equations R=Q+MRR = Q + MRR=Q+MR, and the stationary workload of certain queueing and storage…

17 thms5 active usersReviewed
Operations ResearchProbability·Captain: mikedeng1

Implicit Renewal Theory and Tails of Solutions of Random Equations 2: Kesten's Theorem for R = Q + MR — Unique Stationary Law, Power Tails with Explicit C±, and C₊ + C₋ > 0 iff Q ≢ (1 − M)cResearch Paper

The random difference equation

16 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: mikedeng1

On the Gittins Index for Multiarmed Bandits 3: The Optimal Expected Discounted Reward Is a Submodular Function of the Set of Available BanditsResearch Paper

The multiarmed bandit problem asks how a gambler should allocate successive plays among nnn independent projects, each of which changes state only when it is played, so as to maximize the expected total-discounted reward. Gittins and Jones (1974) showed that it is optimal to play, at every epoch, a project of greatest Gittins index, a number computed from…

16 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Optimal Starting Times for End-of-Season Sales and Optimal Stopping Times for Promotional Fares 3: With One Markdown or Markup Allowed, Thresholds x_n < z_n Give the Optimal PolicyResearch Paper

Retailers of seasonal goods, home builders selling out a development, and airlines and cruise lines selling promotional fares all face the same operational question: inventory is fixed, the selling season is finite, and the price can be changed only rarely. Menu costs, advertising commitments and customer goodwill often restrict a seller to a single price…

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

Optimal Starting Times for End-of-Season Sales and Optimal Stopping Times for Promotional Fares 2: Markup Is Optimal Once Time-to-Go Exceeds an Increasing Threshold z_nResearch Paper

An airline may offer a low promotional fare while seats remain available, then raise the fare as departure approaches. The choice is dynamic: a sale changes both the number of seats left and the benefit of waiting. The same decision appears for hotel rooms and theater seats. Feng and Gallego study a policy with two fixed prices and at most one price change,…

6 thms5 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Poisson Arrivals See Time Averages: Under Lack of Anticipation, the Fraction of Time in B Converges a.s. iff the Fraction of Arrivals Finding B Does, to the Same LimitResearch Paper

Queueing analysis constantly moves between two kinds of long-run averages: the fraction of time a system spends in some set of states, and the fraction of arriving customers who find it there. Waiting-time formulas for the M/G/1 queue, blocking probabilities in loss systems and many decomposition arguments rest on the claim that, when arrivals form a…

13 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: mikedeng1

On the Gittins Index for Multiarmed Bandits 1: A Policy Falls Short of the Gittins Policy by at Most Its Expected Discounted Excess of the Greatest Prevailing Charge over Its RewardResearch Paper

The multiarmed bandit problem asks how to allocate a single resource, one play per period, among several alternative projects whose states evolve only while they are worked on. It models the scheduling of jobs on one machine, the sequencing of research projects, and the design of sequential clinical trials. Gittins and Jones (1974) showed that the problem…

12 thms5 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Loss Networks 1: The Primal Problem Has a Unique Optimum x_r = ν_r ∏_j (1 − B_j)^{A_jr}; the Conditions on B Are Solvable, Uniquely if rank A = J, and Biject with Dual OptimaResearch Paper

A loss network carries calls that require capacity on one or more links. A call is accepted only when every required link has enough free circuits; otherwise it is lost. This makes the traffic on different links dependent even when calls on different routes arrive independently. Network operators need to know where capacity constraints bind and how offered…

11 thms5 active usersReviewed
🏆Completed
Dynamical SystemsOperations Research·Captain: mikedeng1

Stability and Instability of Fluid Models for Reentrant Lines 4: The Lu–Kumar Network Has an Unstable Work-Conserving Fluid Model iff m₂ + m₄ ≥ 1Research Paper

A reentrant line is a queueing network in which every customer follows one fixed route but may return to a station after visiting another one. A manufacturing line can have this pattern when a product revisits the same machine at different processing stages. A station can then have little nominal workload and still face unstable queues under an unfortunate…

14 thms5 active usersReviewed
🏆Completed
Dynamical SystemsOperations Research·Captain: mikedeng1

Stability and Instability of Fluid Models for Reentrant Lines 5: Without Immediate Feedback, Every Work-Conserving Fluid Model of a Two-Station Kelly-Type Line Is StableResearch Paper

A multiclass queueing network can be unstable even when every station has enough capacity on average: the queue lengths grow without bound although each server's nominal load is below one. Kumar and Seidman, Lu and Kumar (1991) and Rybko and Stolyar (1992) exhibited such networks under simple priority disciplines. This raised the question of which networks…

11 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Asymptotic Optimality of Order-up-to Policies in Lost Sales Inventory Systems: Ordering Up to the Newsvendor Level for Penalty b + τh Is Asymptotically Optimal as b → ∞Research Paper

Periodic-review inventory systems face a simple choice each period: how much to order before the next demand is known. When unmet demand is lost, the order can affect the stock available several periods later without preserving a backlog that records earlier shortages. This makes the optimal policy difficult to describe when replenishment takes time. An orde…

16 thms5 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Reversibility and Stochastic Networks II: Migration Processes with Blocking — Reversibility and Product-Form EquilibriumTextbook

A migration process is a continuous-time Markov model of a population spread over JJJ sites, called colonies, in which individuals move one at a time: between colonies, out of the system, or into it from outside. The model was introduced by Whittle (1967) and Kingman (1969) and is the framework of Chapter 2 of F. P. Kelly, Reversibility and Stochastic Networks…

10 thms5 active usersReviewed
Control TheoryOperations ResearchOptimization·Captain: mikedeng1

Resource Allocation and Cross-Layer Control in Wireless Networks IV: The Energy-Constrained Control AlgorithmTextbook

Battery-powered and energy-harvesting wireless devices cannot treat transmission power as free: a control algorithm that maximizes throughput without regard to energy will drain a device long before the network's other resources are exhausted. Chapter 6 of Georgiadis, Neely & Tassiulas's survey Resource Allocation and Cross-Layer Control in Wireless Networks…

15 thms5 active users
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Stochastic Orders VII: The Multivariate Convex OrderTextbook

Chapter III's convex order compares two real-valued random variables by "how spread out" they are, holding the mean fixed. Chapter VII lifts the same idea to random vectors: XXX is smaller than YYY in the multivariate convex order if every convex function of XXX has smaller expectation than the same function of YYY. This mission formalizes that order, its…

12 thms5 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Stochastic Orders VI: The Multivariate Stochastic OrderTextbook

Chapter I's usual stochastic order compares two real-valued random variables by "how large" they tend to be. Chapter VI lifts the same idea to random vectors: XXX is smaller than YYY in the usual multivariate stochastic order if XXX is less likely than YYY to land in any upper set of Rn\mathbb{R}^nRn — any region defined by "at least this large in every coordinate."…

9 thms5 active users
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Stochastic Orders IV: The Increasing Convex and Increasing Concave OrdersTextbook

Chapter I's usual stochastic order compares "how large" two random variables tend to be; Chapter III's convex order compares "how spread out" they are, holding the mean fixed. Chapter IV's increasing convex and increasing concave orders combine the two: X≤icxYX \le_{icx} YX≤icx​Y says XXX is both smaller and less variable than YYY in a single comparison, without forcing…

10 thms5 active users
🏆Completed
Convex OptimizationMachine LearningOperations Research+1·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning IV: Variance-Reduced Mirror Descent for Finite-Sum ProblemsTextbook

Empirical-risk-minimization objectives in machine learning are finite sums: Ψ(x)=1m∑i=1mfi(x)+h(x)\Psi(x) = \frac{1}{m}\sum_{i=1}^m f_i(x) + h(x)Ψ(x)=m1​∑i=1m​fi​(x)+h(x), one smooth term fif_ifi​ per training example (or per worker, in a distributed setting), plus a simple nonsmooth regularizer hhh. Chapter 4's basic stochastic mirror descent handles this by sampling a single random component gradient …

10 thms5 active users
🏆Completed
Markov ChainProbability·Captain: Shuze Chen

Markov Chains and Mixing Times XII: Continuous Time and Countable State SpacesTextbook

The whole series so far lived in discrete time on finite state spaces. Chapters 20–21 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) lift both restrictions. Running the jumps of a chain at the arrivals of a rate-one Poisson clock produces the continuous-time chain, whose transition semigroup — the heat kernel — converges to stationarity…

17 thms5 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: Shuze Chen

Markov Chains and Mixing Times VII: Eigenvalues and the Cheeger InequalityTextbook

How fast does a Markov chain forget its starting point? For a reversible chain the complete answer is coded in the eigenvalues of its transition matrix: the largest eigenvalue is always 111, and the size of the gap between 111 and the rest of the spectrum is the chain's fundamental time constant — a large gap means fast mixing, a small gap means slow mixing.…

24 thms5 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: Shuze Chen

Markov Chains and Mixing Times IV: Lower Bounds on Mixing TimesTextbook

Missions II–III produce upper bounds on mixing times. Whether such a bound is sharp is a different question: an O(n2)O(n^2)O(n2) bound on a chain that actually mixes in nlog⁡nn\log nnlogn steps hides the truth. Chapter 7 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) develops the standard toolkit of lower bounds: the counting and diameter bounds (a chain…

12 thms5 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: Shuze Chen

Markov Chains and Mixing Times III: Coupling and Strong Stationary TimesTextbook

The Convergence Theorem of Mission II says an irreducible aperiodic chain mixes geometrically, but with constants coming from a crude Doeblin decomposition — useless for actual chains, whose state spaces are exponentially large. Chapters 5–6 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) develop the two classic probabilistic techniques…

22 thms5 active usersReviewed
🏆Completed
Machine LearningOperations ResearchQuantum Information·Captain: tianyipeng

Markov Entanglement: Value Decomposition Error in Multi-agent MDPsResearch Paper

Value decomposition — approximating the value of a joint state by a sum of per-agent local values — is a staple of multi-agent dynamic programming and reinforcement learning, from index policies for restless bandits to modern MARL architectures, yet it is normally used without justification. Chen and Peng (arXiv:2506.02385) supply one. They show a…

25 thms5 active usersReviewed
Probability·Captain: WillR

Kyprianou (2006), Chapter 2: Lévy–Itô Decomposition and Path StructureTextbook

A Lévy process is a stochastic process whose increments are stationary and independent and whose sample paths have right limits and left limits. It unifies Brownian fluctuations, isolated jumps and infinitely many small jumps in a single model. This structure is useful in insurance risk, quantitative finance, queuing systems and the fluctuation identities…

74 thms4 active usersReviewed
Probability·Captain: WillR

Kyprianou (2006), Chapter 5: Subordinators at First Passage and Renewal MeasuresTextbook

A subordinator is a non-decreasing Lévy process, and its renewal measure records the accumulated occupation of levels. Together they provide a fundamental route to understanding first-passage times, overshoots and undershoots of jump processes. The principal motivation is Chapter 5 of Andreas E. Kyprianou's 2006 first-edition textbook, which gives a unified…

66 thms4 active usersReviewed
Probability·Captain: WillR

Kyprianou (2006), Chapter 4: General Storage Models and Paths of Bounded VariationTextbook

General storage models turn a net-input path into a nonnegative workload by a minimal Skorokhod regulator. In Chapter 4 of Andreas E. Kyprianou, Introductory Lectures on Fluctuations of Lévy Processes with Applications (Springer Universitext, first edition, 2006, printed pp. 87–109), this construction connects idle time, bounded-variation Lévy processes,…

79 thms4 active usersReviewed
PreviousPage 2 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