Questions tagged [markov-chains]
Stochastic processes (with either discrete or continuous time dependence) on a discrete (finite or countably infinite) state space in which the distribution of the next state depends only on the current state. For Markov processes on continuous state spaces please use (markov-process) instead.
6,165 questions
0
votes
0
answers
34
views
Poincare constant
Assume that we have a markov chain with transition matrix (state space $E=\{0,1,…,n-1\}$)
$P_{ii}=1-2p,
P_{i,i+1} = p,
P_{i,i-1} = p,
P_{0,n-1} =p,
P_{n-1,0}=p,
0 \text{ elsewhere}$
Find poincare ...
- 51
2
votes
0
answers
84
views
Matrix with $k$ entries of $\dfrac{1}{k}$ per row (Markov chain transition matrix) — properties and eigenvalues?
I have a matrix where each row contains exactly $k$ nonzero elements, each equal to $\dfrac{1}{k}$. Therefore, the sum of each row is $1$.
Each row is essentially a permutation of zeros and $k$ ...
- 172
2
votes
1
answer
227
views
Limit of mean duration of the game "Tug of Luck"
In the game "Tug of Luck" $n$ coins are tossed. Player A gets the tails and B gets the heads. Thereafter they take turns rolling a die until one player has gotten rid of all their coins and ...
- 644
1
vote
1
answer
110
views
Defining a probability measure on the path space of a Markov chain
I have an irreducible finite-state Markov chain. Can I define a probability measure on the set of all paths that start from a fixed state $x_0$
and end in a given subset of the state space? How to ...
- 172
3
votes
0
answers
41
views
strong vs. weak infinitesimal generator
I am studying a continuous-time Markov chain $(X_t)_{t \ge 0}$ on a countable state space $E$
with transition semigroup $(P_t)_{t \ge 0}$ acting on bounded functions $B(E)$.
Strong (classical) ...
- 31
0
votes
0
answers
35
views
Markov mixing and coupling confusion: example in Markov Chains and Mixing times by Levin and Peres
Example 14.9 (p. 205) in Markov Chains and Mixing times describes a state space of $n$ $+$ or $-$ cards. The chain moves by interchanging two cards at random (side question: why is this a complete ...
- 13
2
votes
2
answers
119
views
Coupling time distribution
We are given a transition matrix $P$ for two Markov chains X and Y with state space {1,2}. Those Markov chains move accordingly to $P$ independently.
Assume that $X_0=2$ and $Y_0=1$ and define $T$ - ...
- 51
0
votes
1
answer
75
views
Understanding the effect of idempotence on mixing in a Markov chain
I'm trying to understand how to get mixing time results when transitions in a chain are idempotent i.e. $P^2=P$ for transition $P$. Following is a simplified example to illustrate my confusion.
Toy ...
- 13
0
votes
0
answers
35
views
Concentration for Markov chain with spectral gap
Sub-Gaussian concentration for reversible Markov chains with spectral gap
Setup.
Let $(X_i)_{i\ge1}$ be a stationary, $\pi$-reversible Markov chain on a measurable space with spectral gap $\gamma>0$...
- 178
0
votes
0
answers
59
views
Will hitting time of a random walk increase if it starts to occasionally get lazier?
Consider a simple lazy random walk on 0, 1, 2, ..., $n$. It starts at $k$ and at every step gets +1 or -1 with equal probabilities $p$, or stays where it is with probability $1-2p$. Except for when ...
- 324
7
votes
2
answers
177
views
Expected time to exit first quadrant in 2D random walk
Let $W \subseteq \mathbb{R}^2$ be a finite set of vectors, $ P$ be a probability distribution on $W$, and $V_0\in \mathbb{R}^2$ (for simplicity it suffices to consider $V_0$ where both coordinates are ...
- 101
0
votes
1
answer
82
views
Martingale approach for probabilities of consecutive coin flips
Original problem: Given a fair coin, suppose that we flip it until we see HH. What is the probability that we stop on exactly the tenth flip?
One way to solve this is by considering the state matrix
$$...
1
vote
1
answer
64
views
Limit case of Bernstein's inequalities for Markov chain with spectral gap
Context:
Let $\pi$ be a (potentially continuous) probability distribution.
Let $\mathcal{L}^2(\pi)$ be the set of square-integrable function (real-valued) with respect to $\pi$, equipped with the ...
- 178
0
votes
1
answer
46
views
Does this experiment really show Markov Chains with dependent events?
I'm not an expert on any of this, just curious. I'm trying to understand a Youtube video entitled "The Strange Math That Predicts (Almost) Anything" as it attempts to explain Markov Chains.
...
- 253
0
votes
0
answers
39
views
How is the strong Markov property applied here? (From chapter 1, §12, 'Probability-1' by Shiryaev.)
$\textbf{Proposition:}$ Let $\xi=(\xi_0,\ldots,\xi_n)$ be a homogeneous Markov chain with transition matrix $\|p_{ij}\|$, and let $$f^{(k)}_{ii}=P\{\xi_k = i,\xi_l \neq i, 1 \leq l \leq k-1 \vert \...
- 21