Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Markov Chain

295 missions · 185 completed

Missions

Open110Completed185All295
🏆Completed
Machine LearningOptimizationReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction XII: The Policy Gradient TheoremTextbook

Policy gradient methods learn a parameterized policy π(a∣s,θ)\pi(a \mid s, \theta)π(a∣s,θ) directly, by stochastic gradient ascent on a scalar performance measure J(θ)J(\theta)J(θ), instead of deriving the policy from learned action values. They are how reinforcement learning handles continuous action spaces, stochastic optimal policies and prior knowledge built into the policy's…

14 thms3 active usersReviewed
🏆Completed
Machine LearningReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction VII: The Error Reduction Property of n-step ReturnsTextbook

Temporal-difference (TD) learning estimates the value of a policy by moving a current estimate toward a target built from observed rewards and from the estimate itself. Chapter 7 of Sutton and Barto's Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018) interpolates between the two extreme targets of the preceding chapters: the one-step TD…

10 thms3 active usersReviewed
🏆Completed
Machine LearningReinforcement LearningStatistics·Captain: mikedeng1

Reinforcement Learning: An Introduction VI: Batch TD(0) Converges to the Certainty-Equivalence EstimateTextbook

Temporal-difference (TD) learning estimates the value of each state of a Markov reward process from observed experience, updating an estimate toward a target built from the next reward and the current estimate of the next state. Monte Carlo (MC) methods instead update toward the full observed return. Both are standard prediction methods in reinforcement…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction II: The Bellman Optimality Equation and the Existence of an Optimal PolicyTextbook

Sutton and Barto's Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018) is the standard introductory text of the field. Its Chapter 3 sets up the model that the rest of Part I works in: the finite Markov decision process (MDP), the value functions of a policy, and the Bellman equations that relate the value of a state to the values of its…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Fundamentals of Queueing Theory VII: The Geometric Arrival-Point Law of the G/M/1 QueueTextbook

Most queueing models with a closed-form answer assume Poisson arrivals. In practice the times between arrivals are often far from exponential: scheduled appointments, batch releases from an upstream process, or arrivals timed by a machine cycle. The G/M/1 queue keeps the service side exponential and makes no assumption about the arrival stream beyond…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Fundamentals of Queueing Theory VI: The Pollaczek–Khintchine Transform for the M/G/1 QueueTextbook

The M/G/1 queue is the single-server queue with Poisson arrivals and an arbitrary service-time distribution. It is the first queueing model beyond the birth–death family in which exact formulas survive. It is also the model a practitioner reaches for when service times are measured and visibly not exponential: repair times, transmission times of…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Fundamentals of Queueing Theory V: Closed Jackson Networks and the Mean-Value RecursionTextbook

Networks of queues model systems in which a job visits several service stations in turn: jobs in a computer system alternating between CPU and disks, machines cycling between operation and repair, parts routed through a job shop. In a closed network no job enters or leaves; a fixed population of NNN customers circulates among kkk nodes. Closed networks are the…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Fundamentals of Queueing Theory IV: The Stationary Distribution of the M/M/1 Retrial QueueTextbook

In many service systems a customer who finds every server busy does not join a queue. A caller who hears a busy signal hangs up and redials later; a request rejected by a saturated server is resent after a timeout; an aircraft that cannot land circles and tries again. These retrial queues are the subject of a substantial literature in telephone traffic…

10 thms3 active usersReviewed
🏆Completed
AnalysisOperations ResearchProbability+1·Captain: mikedeng1

Fundamentals of Queueing Theory III: The Transient M/M/1 Queue via Modified Bessel FunctionsTextbook

Steady-state formulas describe a queue that has been running forever. Many practical questions are about a queue that has not: a call centre just after opening, a server just after a reset, a system under a burst of load. For these, the relevant quantity is the transient distribution pn(t)=Pr⁡{N(t)=n}p_n(t) = \Pr\{N(t) = n\}pn​(t)=Pr{N(t)=n} of the number N(t)N(t)N(t) in the system at a finite time …

15 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Fundamentals of Queueing Theory II: Erlang's Formulas and the Halfin–Whitt Square-Root Staffing LawTextbook

Every call center, hospital ward, cloud server pool and telephone exchange that is sized by formula is sized by one of a handful of explicit expressions from Markovian queueing theory. The two oldest are A. K. Erlang's: the Erlang-B (loss) formula of 1917, which gives the fraction of calls lost when ccc trunks carry an offered load of rrr erlangs, and the Erlang…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Fundamentals of Queueing Theory I: Foster's Criterion for Positive RecurrenceTextbook

Almost every model in queueing theory is analysed through a Markov chain. The number of customers in an M/M/c queue is a continuous-time birth–death chain; the number left behind by departing customers of an M/G/1 queue is a discrete-parameter chain on {0,1,2,… }\{0,1,2,\dots\}{0,1,2,…} (the imbedded Markov chain); networks of queues are chains on vectors of queue lengths.…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems XIII: Lyapunov Criteria and z Standard Markov Chains with CostsTextbook

Average cost control of queues rests on a small amount of Markov chain theory: when does a chain with costs have a well defined long-run average cost, and how can that be checked for a concrete model with an unbounded state space? Appendix C of L. I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999, doi:10.1002/9780470…

12 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems VIII: Computing Average Cost Optimal Policies by Approximating SequencesTextbook

Control problems for queueing systems (admission control, service rate control, routing to parallel servers) are naturally modelled as Markov decision chains whose state is a vector of queue lengths. The state space is therefore denumerably infinite, and the performance measure of interest is usually the long-run average cost per slot. For such models the…

14 thms3 active users
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems IV: Average Cost Optimal Stationary Policies Exist for Finite State SpacesTextbook

Controlled queues, inventories and communication links are run for a long time, and the quantity an operator usually cares about is the long-run average cost per period rather than a discounted total. The average cost criterion is harder to work with than the discounted one: its value is a lim sup⁡\limsuplimsup of Cesàro means, it is not given by a contraction, and for…

15 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Analysis and Algorithms for Service Parts Supply Chains VI: The Shortfall Distribution of Capacity-Limited SystemsTextbook

Service parts supply chains are often limited by a capacitated resource, such as a production line or a repair shop, instead of by lead times alone. Once capacity binds, the classical tools for setting stock levels (Palm's theorem and the Poisson distribution of units in resupply) no longer apply, and the quantity that determines how much stock is needed is…

15 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Analysis and Algorithms for Service Parts Supply Chains II: The Single-Unit Single-Customer DecompositionTextbook

A base-stock (order-up-to) policy orders, in every period, exactly enough to bring the inventory position (stock on hand plus stock on order minus backorders) up to a target level. It is the policy used in practice for repairable and consumable service parts, and the analysis of every later chapter of Muckstadt's book assumes it. Its optimality is therefore…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchStochastic Systems·Captain: mikedeng1

Computing Optimal (s, S) Inventory Policies III: Selecting an (s, S) Policy That Is Optimal for Every Starting StockResearch Paper

The periodic-review inventory model with a fixed ordering cost is one of the basic models of operations research. When every order incurs a set-up cost KKK in addition to holding and shortage costs, the optimal replenishment rule over an infinite horizon is, under standard convexity assumptions, a stationary (s,S)(s, S)(s,S) policy: whenever the stock falls below the…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Jobshop-Like Queueing Systems: The Equilibrium Distribution with State-Dependent Arrival and Service RatesResearch Paper

A jobshop is a factory in which each job visits a sequence of machine groups, the sequence differing from job to job. J. R. Jackson's 1963 paper Jobshop-Like Queueing Systems (Management Science 10(1), 131–142) models such a shop as a network of queues and computes its long-run distribution of queue lengths in closed form. It generalizes his 1957 paper Netwo…

6 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchStochastic Systems·Captain: mikedeng1

Markov-Renewal Programming. I: Formulation, Finite Return Models: Policy Iteration Finds an Optimal Stationary Policy for the Discounted Infinite-Horizon Markov-Renewal ProgramResearch Paper

Many operational systems move between a finite number of states at random times: a machine alternates between working and repair, a queue between occupancy levels, an inventory between stock positions. When the time spent in a state is not exponential and not a fixed period, neither discrete-time Markov decision processes nor continuous-time Markov chains…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: naimengye

Stochastic Networks II: Migration Processes and Product FormTextbook

A queueing network is a collection of service stations through which customers — jobs, packets, telephone calls, patients — move one at a time. The state of such a network is a vector of occupancy counts, one per station, and the number of states grows exponentially in the number of stations, so solving the equilibrium equations directly is hopeless for any…

11 thms3 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Exact Agreement Expansion up to the Top via Non-polarityResearch Paper

An agreement test checks whether a collection of local functions comes from one global function. Each set KKK of a weighted family carries a local function FK:K→ΣF_K:K\to\SigmaFK​:K→Σ. The test samples a smaller set HHH, then two sets K,K′⊇HK,K'\supseteq HK,K′⊇H, and accepts when FKF_KFK​ and FK′F_{K'}FK′​ agree on HHH. Soundness says that a test that rarely rejects forces most FKF_KFK​ to be…

12 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: iris

High-dimensional expanders, the sparsest cut problem, and Steurer’s conjectureResearch Paper

The O(log⁡n)O(\sqrt{\log n})O(logn​)-approximation of Arora, Rao and Vazirani for the sparsest cut problem rests on a structural theorem about unit vectors satisfying the squared triangle inequality (ℓ22\ell_2^2ℓ22​ metrics): if such vectors are spread out, two linear-sized sets of them are Ω(1/log⁡n)\Omega(1/\sqrt{\log n})Ω(1/logn​) apart (ARV09). Barak, Raghavendra and Steurer showed that higher…

30 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsDynamic ProgrammingOperations Research·Captain: iris

Relaxed Indexability and Index Policy for Partially Observable Restless Bandits: Relaxed Indexability Is Equivalent to a Passive-Time Inequality, and the Approximate Whittle Index Has a Closed FormResearch Paper

A restless multi-armed bandit has NNN arms, each a Markov chain that keeps evolving whether or not it is used; in every slot a decision maker activates some of the arms and collects rewards from them. Channel selection in wireless networks, machine maintenance, target tracking and patient monitoring are of this form. Finding an optimal policy is PSPACE-hard…

14 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents: Above Load b_max/t_{b_max} Every Scheduler Diverges, Below It Every Work-Conserving K-FCFS Scheduler Is Positive RecurrentResearch Paper

A large language model (LLM) answers a request in two phases. In the prefill phase it reads the whole prompt; in the decode phase it generates the answer one token at a time, because each new token depends on all previous ones. Serving engines such as vLLM, SGLang and Sarathi-Serve run the GPU in iterations: each iteration processes one batch that may mix…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Trust and Reciprocity in Firms’ Capacity Sharing: A Non-Trivial Trading-Favors Equilibrium Exists if and only if Each Firm’s Discounted Return on a Favor Exceeds Its Opportunity and Service CostResearch Paper

Service firms with idle capacity often turn away customers while a nearby competitor sits idle, and the reverse happens an hour later. Sharing capacity would help both, but contracting on every transfer is costly, and monitoring the partner's state is usually impossible. Informal arrangements in which favors are returned rather than paid for are a natural…

11 thms2 active usersReviewed
PreviousPage 5 of 8Next

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