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

A First-Order Approach to Accelerated Value Iteration 1: For a Reversible Policy Chain, Accelerated Value Computation Converges at Rate 1 − √((1−λ)/(1+λ)) + η for Every η > 0Research Paper

Value iteration is the standard method for solving a discounted Markov decision process (MDP), and its policy-evaluation variant, value computation (VC), computes the value of a fixed policy by iterating an affine contraction. Both converge geometrically at rate λ\lambdaλ, the discount factor. When λ\lambdaλ is close to one, as in long-horizon…

18 thms7 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower BoundsResearch Paper

A graph can contain a large well-connected subsystem even when the rest of the graph has no useful global structure. For a graph algorithm that only inspects a small portion of its input, recognizing the existence of such a subsystem differs from recognizing expansion of the whole graph. The subsystem might occupy forty percent of the vertices while the…

31 thms6 active usersReviewed
Graph TheoryProbability·Captain: iris

A Tale of Two Walks: From Kac to KMP and BackResearch Paper

The Kipnis–Marchioro–Presutti (KMP) process was introduced as a microscopic model of heat conduction (Kipnis, Marchioro, Presutti 1982): each vertex of a graph holds energy, and at each step the energy at the two endpoints of a random edge is redistributed uniformly between them. Its discrete version moves ttt indistinguishable particles on the ddd vertices of…

34 thms6 active usersReviewed
🏆Completed
Graph TheoryProbability·Captain: mikedeng1

Geometric Bounds for Eigenvalues of Markov Chains 3: Canonical Paths Give β₁ ≤ 1 − 1/(8η²) via Cheeger's InequalityResearch Paper

A finite Markov chain moves among states according to transition probabilities. Its second largest eigenvalue measures how slowly some variation in the starting state can disappear. Directly computing that eigenvalue is often difficult when the state space is large. A geometric bound can be more useful: choose a route between each ordered pair of states and…

11 thms6 active usersReviewed
Dynamic ProgrammingOperations ResearchStochastic Systems·Captain: mikedeng1

Average Cost Optimal Stationary Policies in Infinite State Markov Decision Processes with Unbounded Costs: A Variable-Rate Queue Has an Average Cost Optimal Stationary Policy Whenever λ < max aβResearch Paper

Controlled queues are the standard testing ground for Markov decision processes with infinitely many states: the state is a queue length, which is unbounded, and the holding cost grows with it. The classical theory of the average cost criterion (Ross, Applied Probability Models with Optimization Applications, 1970) produces an optimal stationary policy only…

27 thms6 active usersReviewed
🏆Completed
Probability·Captain: mikedeng1

Geometric Bounds for Eigenvalues of Markov Chains 4: Variation Distance to Stationarity, 4‖Pⁿ(x,·) − π‖² ≤ ((1 − π(x))/π(x)) β_*²ⁿResearch Paper

Markov chain Monte Carlo methods, card-shuffling schemes and randomized counting algorithms all run a Markov chain until its distribution is close to the stationary distribution. The quantity a user needs is a number of steps nnn after which Pn(x,⋅)P^n(x,\cdot)Pn(x,⋅) is within a prescribed variation distance of π\piπ. For reversible chains the standard way to get such a…

11 thms6 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·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
ProbabilityStochastic Systems·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
ProbabilityStochastic Systems·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
ProbabilityStochastic Systems·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
ProbabilityStochastic Systems·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
Graph TheoryProbability·Captain: mikedeng1

Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancyResearch Paper

An independent set is a collection of vertices containing no adjacent pair. Large independent sets are a central object in extremal graph theory and graph algorithms. A graph with maximum degree Δ always has an independent set of size at least n/(Δ+1), where n is its number of vertices. Restrictions on the edges inside neighborhoods can improve this scale…

27 thms5 active usersReviewed
Computational ComplexityProbability·Captain: mikedeng1

How Hard Is It to Compute Cover Time?Research Paper

A cover time measures how long a random walk takes to visit every vertex of a graph. Its expectation distinguishes graphs that are explored quickly from graphs where some vertices remain unseen for much longer. Exact computation records information beyond a coarse estimate of exploration speed. The specified-start comparison problem asks whether the…

26 thms5 active usersReviewed
Convex OptimizationProbabilityTheoretical Computer Science·Captain: iris

Polytope Sampling at the Speed of IsoperimetryResearch Paper

Drawing a point uniformly at random from a polytope X={x∈Rn:Ax<b}\mathcal X=\{x\in\mathbb R^n: Ax<b\}X={x∈Rn:Ax<b} given by mmm linear inequalities is a basic primitive of high-dimensional computation. It is the inner loop of randomized volume computation and integration over convex sets, and it is used directly in systems biology (sampling flux polytopes of metabolic networks),…

35 thms5 active usersReviewed
🏆Completed
Operations ResearchReinforcement Learning·Captain: iris

Multi-agent Markov Entanglement: Exact Q-value Decomposition Holds for Every Reward iff the Agents Are Separable, with the Marginalized Local Q-values as the DecompositionResearch Paper

Many multi-agent reinforcement learning methods fit a local value function for each agent from that agent's own observations and approximate the global value by their sum. Value decomposition in this form underlies VDN (Sunehag et al., 2018) and QMIX (Rashid et al., 2018). It is also the basic approximation of weakly coupled MDPs and restless bandits in…

22 thms5 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: Shuze Chen

Stochastic Networks IX: Time Reversal on Countable State SpacesTextbook

Queueing models describe systems that repeatedly change state: a customer arrives, a service completes, or a circuit becomes free. Their long-run behaviour depends both on how frequently states are visited and on how long each visit lasts. Looking at an equilibrium trajectory backwards produces another process, whose transitions can expose relationships…

6 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingEconomicsOperations Research·Captain: mikedeng1

An Analysis of “Buy X, Get One Free” Reward Programs: Without Transaction Utility, a Redemption Threshold Alone Cannot Raise the Firm's Long-Run Profit Above max{λqv, λ(v − v̄)}Research Paper

"Buy XXX, get one free" (BXGO) programs are among the most common loyalty schemes: coffee shops, car washes, golf courses and hotel chains hand out a free unit after a fixed number of paid purchases. A long empirical literature documents that such programs change behaviour, most visibly through point pressure, the acceleration of purchases as a customer…

19 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

A First-Order Approach to Accelerated Value Iteration 2: For a Reversible Policy Chain, Momentum Value Computation Converges at Rate (1 − √(1/κ))/(1 + √(1/κ)) + η for Every η > 0Research Paper

Value iteration and its policy-evaluation special case, value computation, are the basic algorithms of dynamic programming for Markov decision processes (MDPs). Both are fixed-point iterations of a λ\lambdaλ-contraction, so they converge at the geometric rate λ\lambdaλ, the discount factor. When λ\lambdaλ is close to 111, which is the regime of long effective…

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

Lightning Network Economics: Channels IV: The Long-Run Number of Channel Transactions per On-Chain Transaction in Closed FormResearch Paper

A blockchain such as Bitcoin settles a limited number of transactions per unit of time, and every on-chain transaction pays a fee that rises with congestion. The Lightning Network moves payments off the chain. Two parties lock funds in a payment channel with one on-chain transaction, and they can then pay each other any number of times by updating the…

13 thms5 active usersReviewed
Algorithmic Game TheoryControl TheoryStochastic Systems·Captain: mikedeng1

Strong and Weak Equilibria for Time-Inconsistent Stochastic Control in Continuous Time 1: Weak and Strong Equilibria Exist When the Admissible Generator Rows Form Convex Compact SetsResearch Paper

An agent whose preferences change over time cannot simply optimize. Under non-exponential discounting, for instance hyperbolic or pseudo-exponential discount functions, a plan that is optimal today stops being optimal tomorrow, and a later self deviates from it. Strotz (1955) proposed that a sophisticated agent treat future selves as players in a game and…

17 thms5 active usersReviewed
Control TheoryDynamic ProgrammingStochastic Systems·Captain: mikedeng1

Strong and Weak Equilibria for Time-Inconsistent Stochastic Control in Continuous Time 3: Discrete-Time Equilibria Exist on an Infinite Horizon for Closed Convex Admissible Transition RowsResearch Paper

In many dynamic decision problems the criterion an agent uses today is not the one it will use tomorrow. The standard example is non-exponential discounting: if a payoff received ttt periods from now is weighted by δ(t)\delta(t)δ(t) and δ\deltaδ is not geometric, then the plan that is optimal from today's point of view will be abandoned by the agent's future selves.…

11 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Optimality of (s, S) Policies in Inventory Models with Markovian Demand I: With Markov-Modulated Demand and Fixed Ordering Costs, a State-Dependent (s, S) Policy Is Optimal over a Finite HorizonResearch Paper

Single-item inventory theory asks how much stock to order each period when the order carries a fixed cost KKK on top of a per-unit cost and demand is random. With independent, identically distributed demand, Scarf (1960) showed that the optimal finite-horizon policy has the (s,S)(s,S)(s,S) form: when the stock falls below the reorder point sss, order up to the level SSS;…

20 thms5 active usersReviewed
🏆Completed
Functional AnalysisProbability·Captain: mikedeng1

Logarithmic Sobolev Inequalities for Finite Markov Chains 5: The Log-Sobolev Constant of K(x, y) = π(y) Is (1 − 2π_)/log(1/π_ − 1)Research Paper

The log-Sobolev constant α\alphaα of a finite Markov chain controls how fast the chain forgets its starting point in relative entropy and in ℓ2\ell^2ℓ2, and it gives sharper mixing-time bounds than the spectral gap λ\lambdaλ when the stationary distribution has very small atoms. Diaconis and Saloff-Coste (Ann. Appl. Probab. 6 (1996)) made this constant a standard…

16 thms5 active usersReviewed
🏆Completed
Functional AnalysisProbability·Captain: mikedeng1

Logarithmic Sobolev Inequalities for Finite Markov Chains 4: The Metropolis Chain for the Binomial Distribution Is Within e^{1−c} of Stationarity after (n/2)(log n + 2c) StepsResearch Paper

The Metropolis algorithm turns a simple random walk into a Markov chain with a prescribed stationary distribution, by accepting or rejecting the walk's proposals. It is the basic tool of Markov chain Monte Carlo, and the practical question it raises is quantitative: how many steps are needed before the chain's distribution is close to the target? For most…

23 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research·Captain: mikedeng1

Linear Programming and Sequential Decisions: An Optimal Solution of the Equilibrium LP Yields a Stationary Decision Rule of Least Expected Monthly CostResearch Paper

Alan S. Manne's Linear Programming and Sequential Decisions (Management Science 6(3), 1960, pp. 259–267) is the first formulation of an infinite-horizon, average-cost sequential decision problem as a linear program. The illustration is a single-item inventory problem, but the construction, with unknowns indexed by a state and a decision and constraints…

13 thms5 active usersReviewed
PreviousPage 1 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