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: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling XV: Independence of Level and Phase in QBDsTextbook

A Jackson network of exponential single-server queues has a stationary distribution of product form: the numbers of customers at the nodes are independent in steady state, each geometric (Jackson, 1957; Jackson, 1963). The same property holds for a large family of networks (Kelly, Reversibility and Stochastic Networks, 1979), and it is what makes…

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

Introduction to Matrix Analytic Methods in Stochastic Modeling XIII: M/G/1- and GI/M/1-Type Chains as QBDsTextbook

Many queueing, inventory and storage models are Markov chains on a two-dimensional state space (n,i)(n, i)(n,i): a level n≥0n \ge 0n≥0 (a queue length, a stock level) and a phase iii (the state of an arrival or service environment). When customers arrive in batches, the level can jump up by several units in one step but comes down one unit at a time; when services are…

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

Introduction to Matrix Analytic Methods in Stochastic Modeling XIV: The Matrix-Product Form for Tree-Structured ProcessesTextbook

A quasi-birth-and-death process moves on levels 0,1,2,…0, 1, 2, \dots0,1,2,… and, within a level, among finitely or infinitely many phases; its stationary distribution is matrix-geometric, πn=π0Rn\pi_n = \pi_0 R^nπn​=π0​Rn, which is the central result of the matrix analytic method (Neuts, Matrix-Geometric Solutions in Stochastic Models, 1981; Latouche & Ramaswami 1999, Chapter 6).…

15 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisOperations Research+2·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling XI: First Passage Times by Reduction and BisectionTextbook

In a quasi-birth-and-death process (QBD) a queue length or buffer content (the level) moves up or down by at most one per step while an auxiliary Markov environment (the phase) modulates the rates. When buffers are bounded the level lives in {0,1,…,M}\{0,1,\dots,M\}{0,1,…,M}, and a basic performance question is how long it takes, on average, for an initially empty buffer to…

8 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisOperations Research+2·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling VIII: The Logarithmic Reduction Series for GTextbook

Quasi-birth-and-death processes (QBDs) are Markov chains on pairs (level, phase) in which the level moves by at most one at each step. They model queues in random environments, priority queues, and many other systems treated by matrix-analytic methods (Latouche & Ramaswami 1999). Their stationary distribution, when it exists, is matrix-geometric, and…

8 thms2 active usersReviewed
🏆Completed
Linear algebraOperations ResearchProbability+1·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling IX: The Roots of det(x²A₀ + x(A₁ − I) + A₂) and the Eigenvalues of GTextbook

A quasi-birth-and-death process (QBD) is the matrix generalization of a birth-and-death chain: a Markov chain on pairs (level, phase) that moves at most one level per step. QBDs model queues in random environments, multi-server and priority systems, and communication links with correlated traffic, and their analysis rests on two matrices: the first-passage…

12 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisOperations Research+2·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling X: Linear Level Reduction for Finite QBDsTextbook

In a queue with a finite buffer, a multi-server system with a capacity limit, or a communication link with a bounded number of packets in transit, the number of customers is a level that takes only finitely many values, and the rest of the state (service phase, arrival phase, environment) is a phase. The resulting Markov chain is a finite…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling V: The Matrix-Geometric Stationary Distribution of a QBDTextbook

Quasi-birth-and-death processes (QBDs) are the workhorse models of queueing theory, telecommunications and inventory systems whenever a counting variable (the number of customers, packets or items) moves up or down by one while a second, finite or countable, phase variable records the state of the environment: the phase of a service-time distribution, of an…

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

Introduction to Matrix Analytic Methods in Stochastic Modeling VI: The Mean-Drift Stability Criterion for QBDsTextbook

Quasi-birth-and-death processes (QBDs) are the standard Markov models of queues with structured arrivals and service: a queue fed by a Markovian arrival process, a server with phase-type service times, a buffer in a telecommunication link with a fluctuating source. Their stationary distribution has the matrix-geometric form πn=π0Rn\pi_n = \pi_0 R^nπn​=π0​Rn (Neuts, Matrix-G…

20 thms2 active usersReviewed
🏆Completed
Linear algebraOperations ResearchProbability+1·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling IV: The Censored Markov Chain and Its Stationary DistributionTextbook

Matrix analytic methods compute the stationary distribution of structured Markov chains (quasi-birth-and-death processes, M/G/1- and GI/M/1-type chains) by working on one block of states at a time. Every such computation rests on one device: watch the chain only while it is in a subset TTT of the state space, and describe what happens in between through…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling III: Recurrence of Birth-and-Death Chains and the Minimal Solution of G = a₂ + a₁G + a₀G²Textbook

Birth-and-death chains are the simplest Markov chains with an unbounded state space. They model a queue that gains or loses one customer at a time, a population that grows or shrinks by one, and a random walk with a reflecting barrier. In matrix analytic methods they serve as the scalar model for quasi-birth-and-death processes (QBDs). A QBD is a chain on…

10 thms2 active usersReviewed
🏆Completed
Linear algebraOperations ResearchProbability+1·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling II: The Renewal Function of a PH Renewal ProcessTextbook

Renewal processes model ordered sequences of events on [0,∞)[0,\infty)[0,∞): arrivals to a queue, service completions, equipment failures. Their defining feature is that successive intervals between events are independent and identically distributed. Two quantities answer most practical questions about such a process: the renewal function R(x)R(x)R(x), the expected number of…

9 thms2 active usersReviewed
🏆Completed
Linear algebraOperations ResearchProbability+1·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling I: PH Distributions and the Absorption CriterionTextbook

Phase-type (PH) distributions are the distributions of absorption times of finite Markov chains. Introduced by Neuts in the 1970s (the book follows his framework, Latouche–Ramaswami, §2.3), they are the standard way to put non-exponential service times, interarrival times and lifetimes into a model while keeping it Markovian: a PH random variable is a walk…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Diffusion of New Products with Heterogeneous Consumers: In a Complete Network, Heterogeneity in the External Influence Rates Always Slows Down the Expected AdoptionResearch Paper

The Bass model describes how a new product spreads when consumers can adopt through external exposure and through contact with previous adopters. A homogeneous model assigns the same response rates to everyone. Actual networks can have consumers who respond at different rates, even when the average rate is known. For a fixed average, it is therefore useful…

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

Robust Markov Decision Processes: Beyond Rectangularity 2: With Polyhedral r-Rectangular Factor Sets, One Deterministic Policy and Factor Matrix Stay Robust-Optimal for All Discount Factors Near 1Research Paper

A Markov decision process (MDP) models sequential decisions under uncertainty: in each state a decision maker picks an action, collects a reward, and the system moves to a random next state according to a transition kernel. In applications the kernel is estimated from data, and an optimal policy for the estimated kernel can perform poorly under a slightly…

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

Robust Markov Decision Processes: Beyond Rectangularity 1: Under r-Rectangular Factor Uncertainty, Robust Value Iteration Converges to the Optimal Worst-Case Value, Attained by a Deterministic PolicyResearch Paper

A Markov decision process (MDP) is optimized for a transition kernel that, in practice, is estimated from data, and the optimal policy for the estimated kernel can perform poorly under small perturbations of it. The robust MDP approach replaces the single kernel by an uncertainty set of kernels and asks for the policy with the best worst-case expected…

12 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Robust Markov Decision Processes 1: Over s-Rectangular Ambiguity Sets, Robust Policy Improvement Is Solved by a Stationary Randomized Policy and the Fixed Point of the Robust Bellman MapResearch Paper

A Markov decision process (MDP) is evaluated with a transition kernel that, in practice, is estimated from data. The expected total reward of a policy can be very sensitive to small errors in that estimate (Mannor, Simester, Sun and Tsitsiklis, 2007). Robust MDPs address this by letting the kernel range over an ambiguity set and optimizing the worst-case…

14 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Partially Observable Total-Cost Markov Decision Processes with Weakly Continuous Transition Probabilities 2: Setwise-Continuous Observations Do Not Make the Belief Transition Weakly ContinuousResearch Paper

A partially observable Markov decision process describes a controlled system whose state is hidden but whose observations are available to a decision maker. The distribution of the hidden state conditional on the observations is the belief state. Replacing the hidden state by this distribution turns the model into a fully observed decision process, provided…

6 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchProbability·Captain: mikedeng1

Routing Betweenness Centrality: Under Source-Oblivious Loop-Free Routing, the Betweenness of a Node Sequence Is a Sum over Targets of Chained Pairwise DependenciesResearch Paper

Betweenness centrality measures how much of the communication in a network passes through a node. Freeman's original measure (Freeman 1977) counts the fraction of shortest paths between each pair of nodes that pass through it, and Brandes' algorithm (Brandes 2001) made it computable on large graphs. Variants replace shortest paths by maximum flows (Freeman,…

8 thms2 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingOperations Research·Captain: mikedeng1

Optimal Control of Markov Processes with Incomplete State Information 2: The Minimal Expected Cost Lies Between the Complete-Information and Open-Loop ValuesResearch Paper

When a controller acts on a system whose state is hidden, measurements may help it choose later actions, but the value of those measurements depends on the transition law, the observation mechanism, and the available controls. Åström's 1965 paper gave a finite-state formulation of this problem and compared the best expected loss under incomplete…

5 thms2 active usersReviewed
🏆Completed
ProbabilityRepresentation Theory·Captain: marwahaha

Random coordinate frames and partial permutation lawsOpen Problem

Random coordinate frames allow comparison between different sequences of matching directions in a shuffle. The source uses partially observed card lists to obtain estimates for the full permutation law. The source is OpenAI's September 2026 manuscript.

7 thms2 active usersReviewed
🏆Completed
Probability·Captain: marwahaha

Cutoff throughout the high-temperature Sherrington–Kirkpatrick phaseOpen Problem

Cutoff means that a Markov chain’s transition from far from equilibrium to near equilibrium occurs in a negligible fraction of its mixing time. The source studies heat-bath dynamics for a disordered mean-field Ising model. The source is OpenAI's September 2026 manuscript.

8 thms2 active usersReviewed
🏆Completed
ProbabilityRepresentation Theory·Captain: wurtle

Conditional coordinate sweeps and analytic transferResearch Paper

The Thorp shuffle cuts a deck in half, pairs cards in corresponding positions, and lets an independent fair coin order each pair before the pairs are interleaved. On N=2dN=2^dN=2d cards, removing the deterministic rotation of coordinates turns ddd physical shuffles into one binary coordinate sweep: in each coordinate direction, in order, every pair of positions…

10 thms2 active usersReviewed
🏆Completed
ProbabilityRepresentation Theory·Captain: wurtle

Random-subspace tests and trace smoothing for coordinate sweepsResearch Paper

The Thorp shuffle is a simple card-shuffling rule: cut a deck of nnn cards into two equal halves, pair cards in corresponding positions, and let an independent fair coin decide the order within each pair when the pairs are interleaved. It is a standard test case for mixing-time methods and a building block in small-domain enciphering schemes. For n=2dn=2^dn=2d every…

5 thms2 active usersReviewed
🏆Completed
Mathematical PhysicsProbability·Captain: wurtle

Stretched-exponential barriers for typical SK initial statesResearch Paper

In the low-temperature phase β>1\beta>1β>1 of the Sherrington–Kirkpatrick (SK) spin glass, the Gibbs measure is believed to split into many nearly separated pieces, and local dynamics such as heat-bath (Glauber) updates should take a very long time to move between them. Worst-case slow mixing (some bad starting state) is a weak statement: it says nothing about…

16 thms2 active usersReviewed
PreviousPage 6 of 8Next

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