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
ProbabilityTheoretical Computer Science·Captain: iris

Code Swendsen-Wang DynamicsResearch Paper

Sampling from Gibbs distributions near and below a phase transition is the hard regime for Markov chain methods, because local dynamics take exponentially long to cross energy barriers. For the Ising model the remedy is the global update of Swendsen and Wang. Quantum code Hamiltonians are the minimal models of topological phases, and Hangleiter, Ju and…

31 thms3 active usersReviewed
ProbabilityStatistical Mechanics·Captain: iris

A sharp threshold for Kawasaki mixing in a fixed-magnetization SOS modelResearch Paper

Many local Markov chains transport a conserved quantity rather than create or destroy it. Examples are interface dynamics with fixed magnetization and self-organizing particle systems with a fixed number of particles. Such a conservation law can slow mixing for two different reasons. An energy barrier can force every route between high-weight states through…

81 thms3 active usersReviewed
Graph TheoryProbabilityStatistical Mechanics+1·Captain: iris

Rapid mixing of Potts Glauber dynamics throughout uniquenessResearch Paper

The Potts model is the standard model of ferromagnetism with qqq spin values, and sampling from it is a basic task in statistical physics and in the theory of approximate counting. For q=2q=2q=2 (the Ising model) sampling is possible in polynomial time at every temperature, while for q≥3q\ge3q≥3 it is #BIS-hard even on bounded-degree graphs (Goldberg, Jerrum 2012). The…

35 thms3 active usersReviewed
ProbabilityStochastic SystemsTheoretical Computer Science·Captain: iris

Nearly-Optimal Time-Sample Trade-off in Consensus DynamicsResearch Paper

Consensus dynamics are simple local update rules by which the nodes of a network repeatedly revise their opinions until all of them agree. They model collective decision making and serve as lightweight distributed algorithms: a node keeps no state beyond its current opinion. In the synchronous PULL(hhh) model on nnn fully connected nodes, every node samples hhh no…

23 thms3 active usersReviewed
Graph TheoryProbabilityStochastic Systems+1·Captain: iris

Temporal Conductance and Bounds on the Voter Model for Dynamic NetworksResearch Paper

The voter model is one of the basic models of opinion dynamics and of distributed consensus: every vertex of a network holds an opinion and repeatedly copies the opinion of a random neighbour, until all vertices agree. How long this takes is the consensus time. On a fixed graph it is governed by the graph's conductance: Berenbrink, Giakkoupis, Kermarrec and…

26 thms3 active usersReviewed
Algorithmic Game TheoryCombinatoricsProbability·Captain: iris

Sampling from the Gibbs Distribution in Congestion Games: Relaxed Logit Dynamics in Extension Parallel Congestion Games Mix within n3(log⁡(nlog⁡∣P∣+TΦmax⁡)+log⁡(1/(2ϵ2)))n^3(\log(n\log|P|+T\Phi_{\max})+\log(1/(2\epsilon^2)))n3(log(nlog∣P∣+TΦmax​)+log(1/(2ϵ2))) StepsResearch Paper

Logit dynamics is the standard model of noisy best-response play: repeatedly, a uniformly random player revises their strategy, choosing each option with probability proportional to e−T⋅coste^{-T\cdot\text{cost}}e−T⋅cost, where the temperature T≥0T\ge0T≥0 measures rationality. In a potential game the dynamics is a reversible Markov chain whose stationary law is the Gibbs…

41 thms3 active usersReviewed
Bandit AlgorithmsDynamic ProgrammingOperations Research·Captain: iris

Unichain and Aperiodicity Are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits: The Set-Expansion Policy Has Optimality Gap at Most 256 r_max λ_W²|S|²/(β²√N)Research Paper

A restless bandit couples NNN identical Markov decision processes through a budget: at every time step exactly αN\alpha NαN of the NNN arms must be pulled, and every arm changes state whether it is pulled or not. The model, introduced by Whittle (1988), describes scheduling of machines or patients, sensor management, queueing control and recommendation. Computing…

23 thms3 active usersReviewed
Operations ResearchProbabilityStatistics·Captain: iris

Unbiased Time-Average Estimators for Markov Chains: the Debiased Estimator f̂ₖ Is Unbiased and Square-Integrable with T̂ₖVar(f̂ₖ) ≤ kVar(fₖ) + 8610ν̄(0)²max(q, √((b′(k)−b(k))/k))Research Paper

Steady-state means of Markov chains are estimated by simulation throughout operations research and statistics: queue lengths and waiting times in stochastic networks, posterior expectations in Markov chain Monte Carlo, volumes of convex bodies. The standard estimator is a time average of one long run after a burn-in period. It is biased, because the chain…

31 thms3 active usersReviewed
Operations ResearchProbability·Captain: iris

Improving Blockchain Consistency by Assigning Weights to Random Blocks: Ironclad's Normalized Minimal Adversarial Mining-Power Requirement Strictly Exceeds Nakamoto's (R > 1)Research Paper

Proof-of-work blockchains such as Bitcoin keep a ledger consistent only while the honest parties hold enough mining power relative to an adversary. Network delay erodes that margin: when two honest blocks are mined within the delay bound Δ\DeltaΔ, honest parties extend different chains, and an adversary can exploit the fork. The consistency bound of a…

15 thms3 active usersReviewed
ProbabilityReinforcement LearningStatistics·Captain: mikedeng1

Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity: Under Geometric Mixing the Empirical Estimator Is ε-Accurate After Order dT/ε² Samples, and This Rate Is MinimaxResearch Paper

Offline reinforcement learning and off-policy evaluation start from a single logged trajectory of a controlled system. The policy that generated the log is often unknown, history-dependent and not stationary. Model-based methods first estimate the transition probabilities of the system from this log, then plan or evaluate policies in the estimated model (Aga…

14 thms3 active usersReviewed
Control TheoryDynamic ProgrammingStochastic Systems·Captain: mikedeng1

Strong and Weak Equilibria for Time-Inconsistent Stochastic Control in Continuous Time 4: Limits of Equilibria of the Time-Discretized Problems Are Weak Equilibria in Continuous TimeResearch Paper

A decision maker is time-inconsistent when the plan that is optimal today stops being optimal tomorrow. The standard source is non-exponential discounting: a reward ttt units of time ahead is weighted by δ(t)\delta(t)δ(t), and unless δ\deltaδ is exponential the relative weight of two future dates changes as time passes. Hyperbolic and pseudo-exponential discount…

8 thms3 active usersReviewed
ProbabilityStatistics·Captain: mikedeng1

Spectral Gaps for a Metropolis–Hastings Algorithm in Infinite Dimensions III: The L²-Spectral Gap of Random Walk Metropolis for a Gaussian Target Vanishes Faster Than Any Power of the DimensionResearch Paper

Bayesian inverse problems and conditioned diffusions lead to probability measures on function spaces, and these are sampled in practice through finite-dimensional approximations on Rm\mathbb R^mRm with mmm large. A Markov chain Monte Carlo method is useful in this setting only if its convergence rate does not deteriorate as the discretisation is refined. Random…

12 thms3 active usersReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

Generalized Couplings and Ergodic Rates for SPDEs and Other Markov Models: A Generalized Coupling and a Lyapunov Function Give a Unique Invariant Measure and Wasserstein Ergodic RatesResearch Paper

Many Markov processes that arise as solutions of stochastic partial differential equations, stochastic delay equations, or other infinite-dimensional models are not strong Feller: their transition probabilities from two nearby starting points can be mutually singular. For such processes convergence to equilibrium cannot hold in total variation, and the…

15 thms3 active usersReviewed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: mikedeng1

More Risk-Sensitive Markov Decision Processes 5: Under Positive Harris Recurrence a Risk-Neutral Optimal Stationary Policy Is Optimal for Power-Utility Average CostResearch Paper

Classical Markov decision theory minimizes expected cost. A decision maker who dislikes variability, such as an insurer, a portfolio manager or an operator of a service system, may instead evaluate a random cost YYY by its certainty equivalent U−1(E[U(Y)])U^{-1}(\mathbb E[U(Y)])U−1(E[U(Y)]) for an increasing utility (disutility) function UUU. Bäuerle and Rieder (More Risk-Sensitive…

9 thms3 active usersReviewed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Optimality of (s, S) Policies in Inventory Models with Markovian Demand II: In the Nonstationary Discounted Infinite-Horizon Problem, a State-Dependent (s, S) Policy Is OptimalResearch Paper

Periodic-review inventory models with a fixed ordering cost are the setting in which the (s,S)(s,S)(s,S) policy is optimal: when the stock falls below a reorder point sss, order up to a level SSS, otherwise order nothing. Scarf (1960) proved this for independent demands over a finite horizon by introducing KKK-convexity, and Iglehart (1963) extended it to the discounted…

11 thms3 active usersReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

The Two-Parameter Poisson–Dirichlet Distribution Derived from a Stable Subordinator 5: PD(α, θ) Is a Y_1^θ-Tilt of Independent beta(θ + nα, 1) Ratios, and (Y_n) Is a Markov ChainResearch Paper

The two-parameter Poisson–Dirichlet distribution PD(α,θ)\mathrm{PD}(\alpha,\theta)PD(α,θ) is a law on decreasing sequences V1≥V2≥⋯>0V_1 \ge V_2 \ge \cdots > 0V1​≥V2​≥⋯>0 with ∑nVn=1\sum_n V_n = 1∑n​Vn​=1. It describes the ranked frequencies of species in Bayesian nonparametric models (the Pitman–Yor process), the ranked lengths of excursions of Bessel processes and bridges, and the ranked cycle or block…

15 thms3 active usersReviewed
Machine LearningProbabilityReinforcement Learning·Captain: mikedeng1

An Analysis of Temporal-Difference Learning with Function Approximation 2: For Every Sampling Distribution q and 5/6 < α < 1, Off-Line q-Sampled TD(0) Can Diverge in ExpectationResearch Paper

Temporal-difference learning estimates the future cost of a system from observed transitions. In a Markov model, a state has a distribution of possible successors and each transition carries a cost. An agent may approximate the future cost with a small number of basis functions rather than store one number per state. This is useful when the state set is…

9 thms3 active usersReviewed
Operations ResearchStochastic Systems·Captain: mikedeng1

Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks I: Policy π₀ Is Throughput-Optimal, C′ ⊂ C_π₀ ⊂ C ⊂ C̄′Research Paper

In a wireless multihop network, a switch, or a parallel computer, transmissions interfere: two links that share a receiver, or two crossbar paths that share a port, cannot be active in the same time slot. The scheduler must choose, slot by slot, a set of links that may operate together and decide which traffic each one carries. The basic question is which…

9 thms3 active usersReviewed
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Average Optimality in Dynamic Programming with General State Space: Under (W) or (S) and Bounded Relative Discounted Values, a Limit of Discount-Optimal Policies Is Average OptimalResearch Paper

A Markov decision process with the average cost criterion asks for a policy that minimizes the long-run expected cost per unit time. The criterion is the natural one for inventory, queueing and maintenance systems that run indefinitely without a meaningful discount rate, and it is the standard benchmark in the theory of controlled Markov chains (Arapostathis…

15 thms3 active usersReviewed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems VII: The (BOR) Assumptions and Positive Recurrence of Optimal PoliciesTextbook

Queueing control problems (admission control, routing, service rate selection) are naturally modelled as Markov decision chains with a countably infinite state space and unbounded costs, for instance a holding cost that grows with the queue length. For such models the long-run average cost criterion is often the relevant one, and the central question is…

15 thms3 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local UniformityResearch Paper

Counting the proper kkk-colorings of a graph approximately, and sampling one nearly uniformly, are equivalent problems, and both are classical test cases for Markov chain Monte Carlo. The simplest sampler is the Glauber dynamics, which recolors one vertex at a time. Jerrum (Jer95) showed that it mixes in O(nlog⁡n)O(n\log n)O(nlogn) steps whenever k>2Δk>2\Deltak>2Δ, where Δ\DeltaΔ is…

24 thms2 active usersReviewed
Graph TheoryProbability·Captain: mikedeng1

Sampling Matchings in Near-linear TimeResearch Paper

A matching is a collection of edges in a graph such that no vertex belongs to two selected edges. Random matchings are basic examples in sampling and approximate counting: when every matching has equal weight, the normalizing constant counts all matchings. More generally, edge weights specify a distribution that favors some matchings over others. The…

30 thms2 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: Shuze Chen

Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part I: Glauber DynamicsResearch Paper

In tensor PCA (the spiked tensor model of Richard and Montanari, 2014) one observes an order-kkk tensor that is a rank-one signal buried in Gaussian noise and must recover the hidden direction. The model is a standard testbed for the gap between what is statistically possible and what efficient algorithms achieve. Weak recovery is information-theoretically…

21 thms2 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

An O~(n3)\widetilde{O}(n^3)O(n3)-time FPRAS for the PermanentResearch Paper

The permanent of an n×nn\times nn×n matrix A=(aij)A=(a_{ij})A=(aij​) is per(A)=∑σ∈Sn∏i=1nai,σ(i)\mathrm{per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}per(A)=∑σ∈Sn​​∏i=1n​ai,σ(i)​. For a 0/1 matrix it counts the perfect matchings of the bipartite graph G=(V1∪V2,E)G=(V_1\cup V_2,E)G=(V1​∪V2​,E) whose adjacency matrix is AAA. Valiant showed in 1979 that computing it exactly is #P-complete even for 0/1 matrices, so the question became how fast it…

30 thms2 active usersReviewed
Probability·Captain: Shuze Chen

Fine-Grained Complexity Across the Computational Phase TransitionResearch Paper

The hard-core model on a graph GGG is the law of a random independent set III with probability proportional to λ∣I∣\lambda^{|I|}λ∣I∣. It is the basic repulsive spin system of statistical physics and a central test case for approximate sampling and counting. For graphs of maximum degree d≥3d\ge3d≥3 the threshold λc(d)=(d−1)d−1/(d−2)d\lambda_c(d)=(d-1)^{d-1}/(d-2)^dλc​(d)=(d−1)d−1/(d−2)d, the uniqueness threshold of…

22 thms2 active usersReviewed
PreviousPage 2 of 5Next

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