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

Comparison is All You Need: Settling the ttt-wise independence of AESResearch Paper

A block cipher maps fixed-length plaintext blocks to ciphertext blocks using a secret key. One way to study its statistical behavior is to fix several distinct plaintexts and ask whether their ciphertexts resemble the outputs of a uniformly random permutation. This is approximate t-wise independence: it controls every test of the joint outputs at those…

21 thms1 active userReviewed
Probability·Captain: mikedeng1

Learning AI Agents, Market Makers, and Stress in Automated MarketsResearch Paper

Two markets can exhibit the same distribution of individual returns while arranging losses differently in time. For a monitor concerned with consecutive losses, the duration of a stressed interval is a separate object from the frequency of stressed periods. The question here is whether this distinction survives a model in which trades respond to the…

5 thms1 active userReviewed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: iris

Efficient Stable Word-RAM Simulation by Population ProtocolsResearch Paper

Population protocols model computation by many identical, anonymous agents with small memory that interact in randomly chosen pairs: chemical reaction networks, sensor swarms, molecular programming AAD+06. Inputs and outputs are unary counts of agents in designated states. With a constant number of states, the predicates that can be computed stably (correctl…

31 thms1 active userReviewed
ProbabilityStochastic SystemsTheoretical Computer Science·Captain: iris

Fast Minority Dynamics with Θ(log⁡2n)\Theta(\log^2 n)Θ(log2n)-Size SamplesResearch Paper

Binary consensus asks nnn agents, each holding opinion 000 or 111, to agree on one value by exchanging information. In the synchronous kkk-Pull model every agent observes, in each round, the opinions of kkk agents chosen independently and uniformly at random, and updates its opinion by a fixed local rule. For the MAJORITY rule, where an agent adopts the majority of…

30 thms1 active userReviewed
ProbabilityStochastic SystemsTheoretical Computer Science·Captain: iris

Minority Dynamics with Small SamplesResearch Paper

Consensus and bit dissemination are basic tasks for populations of simple agents that interact through random samples: biological collectives, chemical reaction networks and gossip protocols in distributed systems. In consensus, a population holding two opinions must come to agree on one of them. In bit dissemination, one or more sources hold a fixed…

23 thms1 active userReviewed
Operations ResearchProbabilityReinforcement Learning·Captain: iris

A Policy Gradient Algorithm for the Risk-Sensitive Exponential Cost MDP: The Trajectory-Based Algorithm Drives the Truncated and Untruncated Cost Gradients to Zero Almost SurelyResearch Paper

The risk-sensitive exponential cost of a Markov chain replaces the long-run average of the one-step cost by the exponential growth rate of the expected exponential of the accumulated cost. It penalizes rare sample paths with high cost, and it goes back to Howard and Matheson (1972). For a finite chain the growth rate is the logarithm of a Perron eigenvalue (…

19 thms1 active userReviewed
Operations ResearchProbabilityStochastic Systems·Captain: Shuze Chen

Stability of Queueing Networks III: Fluid-Limit Stability Implies Positive Harris RecurrenceTextbook

A queueing network can have spare capacity at every station and still accumulate an ever-growing population of jobs. Service priorities and routing can prevent the available capacity from being used where it is needed. For networks with general interarrival and service distributions, an explicit stationary distribution is usually unavailable. The stability…

17 thms1 active userReviewed
Operations ResearchProbabilityStochastic Systems·Captain: Shuze Chen

Stability of Queueing Networks I: Product-Form Stationary DistributionsTextbook

A queueing network describes jobs that receive service at several stations and move between them before leaving. A stationary distribution answers questions about the network at a typical time: how many jobs are waiting, which classes they belong to, and how jobs are arranged at each station. Such distributions can be difficult to determine because a…

9 thms1 active userReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOptimization+1·Captain: QianJaneXie

Cost-aware Bayesian Optimization via the Pandora's Box Gittins IndexResearch Paper

Formal verification complete: all 12 mission targets, including Theorem 2, are Proved. These results apply to the formalized independent-box model described below. Paper: Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index, NeurIPS 2024. The formalization follows Theorem 2 and Appendix B.5 of the paper.

13 thms1 active userReviewed
Numerical AnalysisProbabilityStatistics·Captain: mikedeng1

Multilevel Langevin Pathwise Average for Gibbs Approximation III: C² Strongly Contractive Drift, 𝔞 = 2 — L²-Error ≲ [f]₁ε at Cost ((½+√2)/(√2−1))Υ₂²log(γ₀⁻¹)ε⁻²/(γ₀α)Research Paper

Sampling from a Gibbs distribution πU∝e−U dλd\pi_U\propto e^{-U}\,d\lambda_dπU​∝e−Udλd​ on Rd\mathbb R^dRd is a basic task in Bayesian statistics, statistical physics and machine learning. A standard approach simulates the Langevin diffusion dXt=−∇U(Xt) dt+2 dBtdX_t=-\nabla U(X_t)\,dt+\sqrt2\,dB_tdXt​=−∇U(Xt​)dt+2​dBt​, whose invariant distribution is πU\pi_UπU​, through its Euler scheme, and averages a test function fff along…

16 thms1 active userReviewed
Numerical AnalysisProbabilityStatistics·Captain: mikedeng1

Multilevel Langevin Pathwise Average for Gibbs Approximation II: Strongly Contractive Drift, 𝔞 = 1 — L²-Error ≲ [f]₁ε at Cost (5log γ₀⁻¹/2αγ₀)Υ₁²ε⁻²⌈log₂(Υ₁²ε⁻²)⌉³Research Paper

Sampling from a Gibbs distribution πU∝e−U dλd\pi_U \propto e^{-U}\,d\lambda_dπU​∝e−Udλd​ on Rd\mathbb R^dRd, or computing integrals π(f)\pi(f)π(f) against it, is a basic task of Bayesian statistics, statistical physics and stochastic optimization. A standard route is to simulate a diffusion whose invariant law is the target, for instance the overdamped Langevin equation …

15 thms1 active userReviewed
🏆Completed
ProbabilityReinforcement LearningStatistics+1·Captain: Wenqian Xing

Estimation of Treatment Effects Under Nonstationarity via the Truncated Policy Gradient EstimatorResearch Paper

Randomized experiments (A/B tests) on ride-sharing marketplaces, recommendation systems and digital-health services assign each arriving user to treatment or control. The assignment changes the system state seen by later users, so observations are not independent: this is temporal interference, or carryover. The difference-in-means estimator ignores it, and…

17 thms1 active userReviewed
ProbabilityStatistics·Captain: mikedeng1

Spectral Gaps for a Metropolis–Hastings Algorithm in Infinite Dimensions II: The pCN Algorithm Has a Wasserstein Spectral Gap Uniform in the Dimension When the Potential Is Locally LipschitzResearch Paper

Bayesian inverse problems for functions — the initial condition of a PDE, a permeability field, a diffusion coefficient — lead to posterior measures μ\muμ on an infinite-dimensional Hilbert space HHH, given by a density exp⁡(−Φ)\exp(-\Phi)exp(−Φ) with respect to a Gaussian prior γ\gammaγ. In practice μ\muμ is sampled by Markov chain Monte Carlo on an mmm-dimensional discretisation …

13 thms1 active userReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Nonasymptotic Convergence Analysis for the Unadjusted Langevin Algorithm: Explicit Total-Variation Bound for ULA with Nonincreasing Step Sizes When the Potential Is Strongly Convex Outside a BallResearch Paper

Bayesian inference, statistical physics and machine learning all ask for samples from a probability distribution π\piπ on Rd\mathbb R^dRd whose density is known only up to a constant, π(dx)∝e−U(x)dx\pi(dx)\propto e^{-U(x)}dxπ(dx)∝e−U(x)dx. The unadjusted Langevin algorithm (ULA) is the Euler–Maruyama discretisation of the Langevin diffusion, whose invariant law is π\piπ. It needs only…

13 thms1 active userReviewed
Mathematical PhysicsProbability·Captain: mikedeng1

The Endpoint Distribution of Directed Polymers 2: Geometric Localization with Positive Density Holds Exactly in the Low-Temperature PhaseResearch Paper

A directed polymer in random environment is a random walk path reweighted by a random potential that is refreshed at every time step. It is a basic model of a one-dimensional object (a polymer, an interface, a flux line) pinned by impurities, and a discrete version of the KPZ universality class in dimension 1+11+11+1. A central question is localization: whether…

15 thms1 active userReviewed
ProbabilityReinforcement LearningStochastic Systems·Captain: mikedeng1

On Actor-Critic Algorithms: Convergence of Actor-Critic Algorithms with TD(1) and TD(λ) Critics on Finite MDPsResearch Paper

Reinforcement-learning methods for Markov decision processes split into critic-only methods, which learn an approximate value function and act greedily with respect to it, and actor-only methods, which adjust a parameterized policy along a simulated estimate of the gradient of its performance. Critic-only methods with function approximation can fail to…

14 thms1 active userReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

Random Walks in a Random Environment 2: lim X_n/n = (1 − Eσ)/(1 + Eσ) if Eσ < 1, −(1 − E(σ⁻¹))/(1 + E(σ⁻¹)) if E(σ⁻¹) < 1, and 0 OtherwiseResearch Paper

A random walk in a random environment is a walk whose step probabilities are sampled once at each site and then reused whenever the walk returns there. Repeated visits therefore reveal the same local bias instead of drawing a fresh probability. This makes the walk different from an ordinary random walk with a single averaged step probability. Solomon's 1975…

8 thms1 active userReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

The Two-Parameter Poisson–Dirichlet Distribution Derived from a Stable Subordinator 6: n·Y_n → (1 − α)/α Almost Surely under PD(α, θ)Research Paper

In a population divided into many species, a ranked frequency VnV_nVn​ is the fraction belonging to the nnnth most common species. The Poisson–Dirichlet distribution is a model for such random ranked frequencies. It also arises from ranked jumps of a stable subordinator, which gives the model its connection to random interval partitions. Pitman and Yor's 1997…

8 thms1 active userReviewed
Dynamic ProgrammingOperations ResearchStochastic Systems·Captain: mikedeng1

The Complexity of Optimal Queuing Network Control I: NETWORK OF QUEUES is EXP-completeResearch Paper

Multiclass queueing networks model manufacturing lines, computer systems and communication networks. In these systems jobs of several types move between shared resources, and a controller decides where to send a job next (routing) and which waiting job a free resource works on (sequencing). The central design question is to find a control policy that…

10 thms1 active userReviewed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems V: The Average Cost Optimality Equation and Value Iteration for Finite State SpacesTextbook

Average cost Markov decision chains model systems that run indefinitely and are judged by their long-run cost per step: admission and routing control in queues, inventory replenishment, machine maintenance. For a finite state space the classical tool is the average cost optimality equation (ACOE)

13 thms1 active userReviewed
PreviousPage 12 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