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
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey 3: A Uniform Lower Bound on the Probability of Moving to State 0 Reduces Average Cost to Discounted CostResearch Paper

A controller acting over an indefinite horizon must decide whether a lower cost today is worth a higher cost later. Average cost measures the expected expenditure per stage as the horizon grows. It is appropriate when operation has no natural terminal date, but its limiting definition makes it difficult to compute an optimal policy directly. Discounted cost…

7 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey 1: Uniformly Bounded Differential Discounted Values Give a Bounded Solution of the Average Cost Optimality EquationResearch Paper

Many control problems in queueing, inventory and communication systems run indefinitely, and the quantity of interest is the long-run cost per unit time rather than a discounted total. The average cost criterion is harder to analyse than the discounted one: the discounted dynamic programming operator is a contraction, while the average cost problem has no…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

Reversibility and Stochastic Networks VI: The Ewens Sampling Distribution Is Consistent Under Sampling Without ReplacementTextbook

The neutral theory of molecular evolution holds that much of the genetic variation observed at the molecular level is caused by selectively neutral mutations rather than by selection. To test it against data one needs the distribution of allele frequencies that a neutral model predicts, and in practice that distribution has to be compared with a sample from…

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

On the Stochastic Matrices Associated with Certain Queuing Processes 1: The M/G/1 Imbedded Chain Is Ergodic iff ρ < 1 and Recurrent iff ρ ≤ 1Research Paper

Many queues observed at well-chosen instants are Markov chains on the nonnegative integers. For the single-server queue with Poisson arrivals and general service times (M/G/1), D. G. Kendall showed in 1951 that the number of customers left behind at successive departure epochs is such a chain, the imbedded Markov chain (Kendall 1951; Kendall 1953). Whether…

9 thms2 active usersReviewed
🏆Completed
ProbabilityReinforcement Learning·Captain: mikedeng1

Linear Least-Squares Algorithms for Temporal Difference Learning II: Probability-One Convergence of LS TD on Ergodic Markov ChainsResearch Paper

Temporal-difference (TD) learning estimates the value function of a Markov chain — the expected discounted sum of future rewards from each state — from a single stream of observed transitions, without knowing the transition probabilities. With a linear function approximator the value of state xxx is represented as ϕx′θ\phi_x'\thetaϕx′​θ for a feature vector ϕx\phi_xϕx​ and…

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

Optimization of Multiclass Queueing Networks: Polyhedral and Nonlinear Characterizations of Achievable Performance I: Quadratic Potential Functions Bound Mean Response Times in Open NetworksResearch Paper

Scheduling in a multiclass queueing network asks which waiting job a server should work on next when jobs of several types share stations and revisit them along fixed routes. Such networks model semiconductor wafer fabs, job shops and communication switches. Optimal policies are rarely computable: the state space is countably infinite, and even deciding…

8 thms2 active usersReviewed
🏆Completed
Linear algebraMachine LearningReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction VIII: The TD Fixed Point of Linear Semi-gradient TD(0) and Its Error BoundTextbook

Reinforcement learning methods estimate the value function vπv_\pivπ​ of a policy π\piπ: the expected discounted sum of future rewards from each state. When the state space is large, vπv_\pivπ​ cannot be stored as a table and is approximated by a parametrized function. The most studied case is linear function approximation, where each state sss carries a feature vector …

11 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchProbability+1·Captain: mikedeng1

Fundamentals of Queueing Theory X: Uniformization of Continuous-Time Markov ChainsTextbook

Most Markovian queueing models have no closed-form transient solution. The M/M/1 queue already needs modified Bessel functions (Chapter 2 of the book), and a finite-capacity or multi-class model with state-dependent rates has no closed form at all. What an analyst can always write down is the system of forward equations p′(t)=p(t)Qp'(t)=p(t)Qp′(t)=p(t)Q for the state…

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

Stochastic Dynamic Programming and the Control of Queueing Systems XIV: Conforming Approximating Sequences for Markov ChainsTextbook

Countable-state Markov chains are the standard model of queues with unbounded buffers, but any numerical computation of their long-run behaviour works on a finite state space. The usual remedy is truncation: restrict the chain to a finite set SNS_NSN​ and redistribute the probability of leaving SNS_NSN​ back into it. Whether the steady state probabilities and average…

10 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

A Note on Metropolis–Hastings Kernels for General State Spaces III: The Maximal Kernel of a Mixture Proposal Dominates the Mixture of Maximal Kernels Off the DiagonalResearch Paper

A Markov chain Monte Carlo sampler is often assembled from simpler parts. A practitioner who has several proposal mechanisms Q1,Q2,…Q_1, Q_2, \dotsQ1​,Q2​,… for a Metropolis–Hastings sampler can combine them in two ways. Either each QiQ_iQi​ drives its own Metropolis–Hastings kernel PiP_iPi​ and the sampler picks kernel PiP_iPi​ with probability βi\beta_iβi​ at each step, or the mixture …

16 thms2 active usersReviewed
🏆Completed
Functional AnalysisProbabilityStatistics·Captain: mikedeng1

A Note on Metropolis–Hastings Kernels for General State Spaces II: Off-Diagonal Domination Orders the Asymptotic Variances of Reversible Kernels (Peskun's Theorem)Research Paper

Markov chain Monte Carlo (MCMC) estimates an expectation ∫f dπ\int f\,d\pi∫fdπ by the average of fff along a Markov chain whose invariant distribution is π\piπ. Many chains share the same π\piπ: every Metropolis–Hastings acceptance rule that satisfies detailed balance, every mixture of such kernels, every choice of proposal. Practitioners need a criterion for preferring…

12 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

A Note on Metropolis–Hastings Kernels for General State Spaces I: Necessary and Sufficient Conditions for a Metropolis–Hastings Kernel to Satisfy Detailed BalanceResearch Paper

The Metropolis–Hastings algorithm (Metropolis et al. 1953; Hastings 1970) is the basic construction of Markov chain Monte Carlo. It turns a target probability distribution π\piπ, known only up to a constant, into a Markov chain that has π\piπ as its invariant distribution. Bayesian computation depends on it, and a sampler is usually designed by proving one…

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

Markov-Renewal Programming. II: Infinite Return Models, Example II: Gain and Bias of the Infinite-Step ReturnResearch Paper

A Markov-renewal program is a sequential decision model in which a system moves among finitely many states, the time between transitions is random and may depend on both the current and the next state, and a reward accrues during each sojourn. It generalizes the Markov decision process, where every transition takes one time unit, and is the standard model…

10 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchStochastic Systems·Captain: mikedeng1

Markov-Renewal Programming. II: Infinite Return Models, Example I: Policy Iteration Finds a Stationary Policy of Maximal Gain RateResearch Paper

Many controlled systems do not move in unit time steps. A machine runs for a random time before it breaks down, a repair takes a random time, a queue sits in a state until the next arrival or departure. A Markov-renewal program (in later terminology a semi-Markov decision process) models such a system: the sequence of visited states is a Markov chain…

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

Open, Closed, and Mixed Networks of Queues with Different Classes of Customers: The Product-Form Equilibrium DistributionResearch Paper

Networks of queues model computer systems, communication networks and manufacturing lines: customers (jobs, packets, parts) move between service centers, wait, receive service and move on. Their equilibrium behaviour determines throughputs, utilizations and response times, and for most networks it can only be computed by solving the full balance equations…

9 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: naimengye

Fundamentals of Supply Chain Theory X: Supply UncertaintyTextbook

Every model in the earlier chapters of this series treats demand as the uncertain quantity and supply as given. Chapter 9 of Snyder and Shen's Fundamentals of Supply Chain Theory (2019) reverses the roles: demand is deterministic and the supplier fails. A disruption is a binary event, modeled as a two-state Markov process between up and down periods, during…

6 thms2 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: naimengye

Introduction to Stochastic Networks II: Kolmogorov's Criterion for ReversibilityTextbook

A Markov process is reversible when, in equilibrium, transitions from xxx to yyy occur at the same average rate as transitions from yyy to xxx. Algebraically this is the detailed balance condition π(x)q(x,y)=π(y)q(y,x)\pi(x)q(x,y)=\pi(y)q(y,x)π(x)q(x,y)=π(y)q(y,x), and it is the single most useful structural property a network process can have: it replaces a global linear system by one equation per pair of…

6 thms2 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: naimengye

Probability Theory and Examples III: The Markov Chain Convergence TheoremTextbook

A Markov chain forgets. Run it long enough and the distribution of its position stops depending on where it started — that is the intuition behind shuffling a deck, behind Markov chain Monte Carlo, behind PageRank, and behind the stationary analyses of every queueing model. Chapter 5 of Rick Durrett's Probability: Theory and Examples (Version 5, 2019) makes…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: naimengye

Stochastic Networks I: Erlang's Formula for a Single LinkTextbook

In the early twentieth century Agner Krarup Erlang worked for the Copenhagen Telephone Company and faced a sizing question that every shared-resource operator still faces: how many parallel circuits must a telephone link carry so that an arriving call is almost never turned away? The answer he published — the Erlang loss formula — is still the standard…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: tianyipeng

Markov Entanglement: Index Policies for Restless Bandits are Asymptotically SeparableResearch Paper

Restless multi-armed bandits are the standard model for allocating a scarce resource across many independently-evolving agents: N arms, each a small Markov chain, and a budget that lets you activate only a fixed fraction of them at each step. The joint problem is PSPACE-hard, so practice runs on index policies — score each arm by a priority index computed…

12 thms2 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: Shuze Chen

Markov Chains and Mixing Times XIII: Coupling from the PastTextbook

Every sampling guarantee in this series so far is approximate: run the chain for tmix(ε)t_{\mathrm{mix}}(\varepsilon)tmix​(ε) steps and the output is within ε\varepsilonε of stationarity. In 1996 Propp and Wilson showed that, astonishingly, one can often sample exactly from the stationary distribution of a chain — with no error at all and no knowledge of the mixing time —…

5 thms2 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: Shuze Chen

Markov Chains and Mixing Times II: The Convergence TheoremTextbook

The first mission of this series established that an irreducible finite Markov chain has a unique stationary distribution π\piπ. The present mission, covering Chapters 3–4 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009), answers the two questions that make that fact useful. First, the inverse problem of sampling: given a target distribution …

14 thms2 active usersReviewed
Mathematical PhysicsQuantum Information·Captain: iris

Rapid mixing of quantum spin chains at any finite temperatureResearch Paper

Thermal (Gibbs) states describe quantum systems in equilibrium, and preparing them on a quantum computer is a basic task for quantum simulation. A common route is a quantum Gibbs sampler: a Lindbladian whose dynamics converges to the Gibbs state σβ=e−βH/tr⁡e−βH\sigma_\beta=e^{-\beta H}/\operatorname{tr}e^{-\beta H}σβ​=e−βH/tre−βH from any initial state, the quantum analogue of a Markov…

27 thms1 active userReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

Tight Variable-Occurrence Bounds and Exponential Separations for Moser–Tardos and WalkSAT on 3-CNFResearch Paper

WalkSAT and the Moser–Tardos algorithm (MT) are the two standard clause-driven local-repair procedures for satisfiability. Both keep a complete assignment and repeatedly pick an unsatisfied clause. WalkSAT flips one variable of it (Papadimitriou 1991, Schöning 1999); MT resamples all of its variables with fresh random bits, which is the algorithmic form of…

28 thms1 active userReviewed
Computational GeometryProbabilityTheoretical Computer Science·Captain: Shuze Chen

An FPRAS for Mixed VolumesResearch Paper

For compact convex sets K1,…,Km⊆RnK_1,\dots,K_m\subseteq\mathbb{R}^nK1​,…,Km​⊆Rn, Minkowski showed that the volume of a weighted Minkowski sum is a homogeneous polynomial of degree nnn in the weights,

27 thms1 active userReviewed
PreviousPage 11 of 12Next

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