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 ResearchProbabilityStatistics·Captain: Shuze Chen

The Markov Chain Central Limit TheoremResearch Paper

Markov chain Monte Carlo turns hard integration problems into long simulations: to estimate an expectation EπfE_\pi fEπ​f one runs a Markov chain with stationary distribution π\piπ and reports the sample average fˉn\bar f_nfˉ​n​. The ergodic theorem guarantees fˉn→Eπf\bar f_n \to E_\pi ffˉ​n​→Eπ​f, but honest error bars require more: a central limit theorem

154 thms18 active usersReviewed
🏆Completed
AnalysisProbability·Captain: WillR

Foundations of Lévy Processes: Construction, Fluctuation Theory and Stochastic ControlTextbook

A real-valued Lévy process describes random evolution with stationary and independent increments. Brownian motion, compound-Poisson risk models and infinite-activity jump processes belong to this class. Their analytical theory is a foundation for insurance risk, mathematical finance and stochastic control. Lévy–Khintchine representation and the construction…

2,360 thms12 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchProbability·Captain: Shuze Chen

Stochastic Networks XVI: The Stability Region of Alpha-Fair Flow AllocationsTextbook

Bandwidth allocation determines how quickly a network transfers each file, but files also arrive and depart while the network operates. An allocation can be feasible at every instant and still allow the number of unfinished files to grow without an equilibrium. The relevant question is therefore about the interaction of the allocation rule with the changing…

15 thms7 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Stochastic Networks XII: Implied Costs and Sensitivity in Loss NetworksTextbook

An accepted call earns revenue but occupies circuits that could serve later calls. In a network, those consequences extend beyond the links used by the original call: a change in blocking on one link changes the traffic reaching other links. Network planning therefore needs a marginal value that accounts for these indirect effects. Chapter 4 of Kelly and…

9 thms6 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: Shuze Chen

Stochastic Networks XI: Gaussian Limits for Large Loss NetworksTextbook

A loss network accepts a request only when all resources needed by that request are available. An accepted telephone call, for example, occupies circuits on several links at once. A blocked request leaves immediately. Resource sharing makes route occupancies dependent, even when the arrival streams are independent. For a large network, its exact equilibrium…

15 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: mikedeng1

On the Gittins Index for Multiarmed Bandits 2: A Policy Falls Short of the Gittins Policy by at Most Its Expected Discounted Gap Between the Greatest Gittins Index and That of the Bandit It PlaysResearch Paper

The multiarmed bandit problem asks how to allocate a single resource, one play at a time, among several alternative projects whose states evolve only when they are worked on. It models the scheduling of jobs on a single machine, the design of sequential clinical trials and many problems of research planning. Gittins and Jones showed that it is optimal to…

11 thms6 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Loss Networks 2: The Erlang Fixed Point Is E_j = 1 − exp(−y_j) for the Unique Optimum y of the Strictly Convex Revised Dual ProblemResearch Paper

A loss network is a model of a circuit-switched network: telephone networks, and more generally any system in which a request seizes several resources at once and is lost if any of them is unavailable. Exact loss probabilities in such networks are given by a product-form distribution over a state space whose size grows exponentially with the number of…

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

Reversibility and Stochastic Networks I: Kolmogorov's Criterion — a Stationary Markov Process Is Reversible iff Its Rates Balance Around Every CycleTextbook

A stochastic process is reversible when a film of it run backwards is statistically indistinguishable from the film run forwards. For Markov processes in equilibrium this distributional symmetry has an algebraic counterpart, the detailed balance conditions, and that counterpart is what makes large classes of queueing networks, migration processes, loss…

30 thms6 active users
🏆Completed
Algorithmic Game TheoryDynamical SystemsProbability·Captain: mikedeng1

On the Global Convergence of Stochastic Fictitious Play IV: Almost Sure Convergence in Supermodular Games with a Unique Rest PointResearch Paper

Fictitious play is the oldest model of learning in games: each player repeatedly best-responds to the empirical frequencies of the opponents' past play. Stochastic fictitious play adds random payoff disturbances before each choice, so that players choose smoothed ("perturbed") best responses. It is a standard model in economics and in the study of learning…

19 thms6 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: Shuze Chen

Markov Chains and Mixing Times XI: The Cutoff Phenomenon and Lamplighter WalksTextbook

For many natural chains, convergence to stationarity is not gradual: the distance stays near its maximum for a long time and then collapses to zero in a comparatively negligible window. A deck of cards under riffle shuffles is "not at all mixed" for six shuffles and "essentially mixed" after eight. This abrupt transition is the cutoff phenomenon, discovered…

18 thms6 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: Shuze Chen

Markov Chains and Mixing Times X: Martingales and Evolving SetsTextbook

Every mixing bound in Missions II–IX ultimately leaned on either coupling or the spectrum, and the spectral route demanded reversibility. Chapter 17 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) opens a third route: martingales — processes whose conditional expected increment vanishes — and the beautiful evolving-set process of Morris…

14 thms6 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: Shuze Chen

Markov Chains and Mixing Times IX: The Ising ModelTextbook

The Ising model is statistical mechanics' fruit fly: spins ±1\pm1±1 on the vertices of a graph, neighbours preferring to agree, a single parameter — the inverse temperature β\betaβ — tuning the strength of that preference. Chapter 15 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) studies the Glauber dynamics for this model and exhibits, on…

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

Markov Chains and Mixing Times V: Shuffling CardsTextbook

How many shuffles does a deck of cards need? The question created the modern theory of mixing times: Diaconis and Shahshahani's analysis of random transpositions (1981) and the Bayer–Diaconis "seven shuffles suffice" analysis of the riffle shuffle (1992) are its founding results. Chapters 8 and 16 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS,…

19 thms6 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: iris

Processing Networks XVI: The Foster–Lyapunov Criterion for Continuous-Time Markov Chains with Bounded Transition RatesTextbook

Stability of a queueing or processing network is usually established by representing the network as a continuous-time Markov chain (CTMC) on a countable state space and showing that the chain is positive recurrent. Direct computation of a stationary distribution is rarely possible, so the working tool is a Foster–Lyapunov criterion: exhibit a non-negative…

18 thms5 active usersReviewed
🏆Completed
Control TheoryOperations ResearchReinforcement Learning·Captain: mikedeng1

Convergence of Finite Memory Q Learning for POMDPs and Near Optimality of Learned Policies Under Filter Stability: Finite-Window Q-Learning Converges Almost Surely, with a Filter-Stability Loss BoundResearch Paper

A partially observed Markov decision process (POMDP) is a controlled Markov chain whose state the controller never sees. Only noisy observations are available. Such models describe sensor-based control, maintenance under imperfect inspection, and most reinforcement-learning tasks in which the agent sees an image or a measurement rather than the system's…

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

On the Stability of Redundancy Models: With i.i.d. Exponential Copies, the Redundancy-d System under Processor Sharing or Random Order of Service Is Stable Whenever ρ = λ/(µK) < 1Research Paper

Redundancy (sending several copies of a job to different servers and keeping the first one to finish) is a standard way to cut response times in parallel computing systems whose servers have variable speeds: replicated requests in data centres, speculative execution in MapReduce-type frameworks, duplicated queries in distributed storage (Vulimiri et al.,…

14 thms5 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Pricing in On-Demand and One-Way Vehicle-Sharing Networks 3: The K/(N+K−1+Λ/μ) Guarantee Holds When Static Prices Split the Network into ComponentsResearch Paper

One-way vehicle-sharing systems (car sharing, bike sharing, on-demand fleets) move a fixed fleet of KKK vehicles among NNN locations. Customers take a vehicle at one location and leave it at another, so prices shape both revenue and where the fleet ends up. The optimal dynamic pricing policy, which reacts to the current position of every vehicle, solves a…

26 thms5 active users
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Designing a Call Center with Impatient Customers I: The Steady-State Fraction of Abandoning Callers Tends to max(0, 1 − 1/ρ) as the Number of Agents GrowsResearch Paper

Telephone call centers are among the largest employers of service labour, and their staffing decisions are made with queueing models. The classical model is the Erlang-C queue M/M/NM/M/NM/M/N: Poisson arrivals, NNN agents, exponential service, infinitely patient callers. Real callers hang up. Garnett, Mandelbaum and Reiman (M&SOM 2002) argued that a model ignoring…

14 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
PreviousPage 1 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