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
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Contact Interactions on a Lattice I: A Contact Process with (2d − 1)λₖ < kμ Dies Out from Every Finite Initial SetResearch Paper

The contact process is the basic model of an infection spreading on a lattice: each infected site recovers at a constant rate, and each healthy site becomes infected at a rate that depends on how many of its neighbours are infected. It was introduced by T. E. Harris in Contact Interactions on a Lattice (Ann. Probab. 2, 1974), and it became one of the…

13 thms3 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: mikedeng1

On the Generalized “Birth-and-Death” Process 1: For Rates λ(t), μ(t) ≥ 0 the Population Size Is Geometric with a Modified Zero Term, ξ_t = 1 − e^{−ρ}/W, η_t = 1 − 1/WResearch Paper

Population models often allow each individual to produce a new individual or die at rates that change over time. Seasonal conditions, exposure to an epidemic, and changing conditions in a laboratory population all make a constant rate a restrictive assumption. In Kendall's 1948 paper, the question is how the entire distribution of the population size…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research+1·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems VII: Bias Optimality — Four Equivalent Characterizations of a Bias Optimal Pure Stationary PolicyTextbook

A finite Markov decision problem can have several policies with the same long-run average reward even though they behave differently before reaching a recurrent class. Average reward discards a finite initial advantage: dividing total reward by the horizon sends any fixed transient contribution to zero. In applications where the process runs for a long but…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research·Captain: mikedeng1

Linear Programming and Markov Decision Chains 3: The Representative of a Pure Stationary Policy Is an Extreme Point of the Dual LPResearch Paper

A Markov decision chain is a controlled Markov chain: in each state the controller picks an action, collects a reward and moves to a random next state with probabilities that depend on the state and the action. Under the average reward criterion, the long-run reward per step, an optimal policy can be computed by linear programming. For chains in which every…

9 thms3 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: mikedeng1

Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model: The Discrete-Time Proximity Process Is Dual to the Branching Process with InterferenceResearch Paper

Many models in probability, statistical physics and the theory of stochastic networks are interacting particle systems: infinitely many sites, each in state 0 or 1, each updating at random according to the states of a few other sites. A basic question about such a system is ergodicity: does it have a unique stationary distribution, and does its law converge…

6 thms3 active usersReviewed
🏆Completed
Linear algebraMachine LearningReinforcement Learning·Captain: mikedeng1

Learning to Predict by the Methods of Temporal Differences: Linear TD(0) Converges in Expected Value to the Ideal Predictions on Absorbing Markov ChainsResearch Paper

Temporal-difference (TD) methods learn to predict an eventual outcome from the differences between successive predictions rather than from the difference between each prediction and the final outcome. Sutton's 1988 paper Learning to predict by the methods of temporal differences introduced the TD(λ\lambdaλ) family and gave the first convergence proof for a TD…

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

Denumerable State Markovian Decision Processes—Average Cost Criterion: Every Limit Point of Policy Improvement Is a Deterministic Stationary Rule That Is Optimal over All RulesResearch Paper

Markovian decision processes with the long-run average cost criterion model systems run indefinitely: inventories, queues, maintenance schedules, communication links. For a finite state space the theory was settled by the early 1960s. Howard's policy improvement (policy iteration) procedure (1960) finds an optimal stationary rule in finitely many steps, and…

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

Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey 4: Under Sennott's Conditions an Average-Cost Optimal Stationary Policy ExistsResearch Paper

Many controlled queueing, inventory and maintenance systems are modelled as controlled Markov processes (CMPs) on a countable state space whose one-stage cost grows without bound: the holding cost of a queue grows with its length. For such systems the natural performance measure is the long-run average cost, and the basic question is whether some simple…

11 thms3 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingOperations Research·Captain: mikedeng1

Optimal Control of Markov Processes with Incomplete State Information 1: Reduction to Complete State Information on the Conditional State Distributions, with the Same Optimal LawResearch Paper

A controller often cannot see the state of the system it steers. It sees only measurements that are noisy functions of that state. In operations research this happens in machine maintenance and inspection, in queues observed only partially, and in inventory systems with inexact stock records. In control engineering it is the usual case. The question is what…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·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
🏆Completed
Graph TheoryOperations ResearchProbability+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
Operations ResearchOptimizationProbability+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
Operations ResearchProbabilityStochastic Systems·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
Operations ResearchProbabilityStochastic Systems·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
ProbabilityReinforcement Learning·Captain: mikedeng1

Linear Least-Squares Algorithms for Temporal Difference Learning I: Probability-One Convergence of Trial-Based LS TD on Absorbing Markov ChainsResearch Paper

Temporal-difference learning estimates the value of a policy from observed state transitions and rewards. In a finite Markov decision process, fixing a policy produces a Markov chain, so policy evaluation becomes the task of estimating the expected return from each state. Bradtke and Barto's 1996 paper introduced a least-squares temporal-difference method, L…

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

Discrete Dynamic Programming 2: A Stationary Policy Is Nearly Optimal as the Discount Factor Tends to 1 Exactly When It Maximizes x(g) and, Among Those, y(g)Research Paper

A finite Markov decision problem with discounting is solved by Howard's policy improvement routine: start from a stationary policy, switch to actions that do better against its value, repeat. When the discount factor β\betaβ tends to 111 the total discounted income typically diverges, and the natural targets become the long-run average income and, among…

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

Discrete Dynamic Programming 1: Every Finite Markov Decision Problem Has a Stationary Policy That Is Optimal for All Discount Factors Sufficiently Near 1Research Paper

A Markov decision problem models a system that is observed once per period and controlled by choosing an action: the action earns an immediate income and determines the probabilities of the next state. Inventory control, machine replacement, queue admission and many reinforcement-learning benchmarks are of this form. With future income discounted by a…

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

Reinforcement Learning: An Introduction IX: Average Reward and the Futility of Discounting in Continuing ProblemsTextbook

Reinforcement learning formulates control as maximizing reward accumulated over time. For continuing tasks, where interaction never terminates, the standard textbook objective is the discounted return with a discount rate γ<1\gamma < 1γ<1. Chapter 10 of Sutton and Barto, Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018), argues that once values…

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

An Inventory Model with Limited Production Capacity and Uncertain Demands I. The Average-Cost Criterion: With Finite Storage a Modified Base-Stock Policy Is Strongly Average-Cost OptimalResearch Paper

A manufacturer that makes one product to stock faces random demand, can produce at most bbb units per period, and can store at most UUU units. The classical result without the production limit is that a base-stock policy is optimal: raise inventory to a fixed level yˉ\bar yyˉ​ each period. With a production limit, the natural modification is to produce up to yˉ\bar yyˉ​ w…

10 thms3 active usersReviewed
🏆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
PreviousPage 6 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