# Questions tagged [markov-chains]

The markov-chains tag has no usage guidance.

**-1**

votes

**1**answer

116 views

### What's the probability of two independent events in time domain?

Suppose there are two independent events A and B. The probability that A or ...

**0**

votes

**0**answers

49 views

### Self-correcting Random Walks

Vincent Granville, in his $Analytic\ Bridge$ blog posed a problem on self-correcting random walk.
Quoting from the post:
Let's start with $X(1)=0$, and define $X(k)$ recursively as
follows, for $...

**1**

vote

**0**answers

57 views

### Discrete Markov process on finite interval

Consider an contiguous array of $N$ states, numbered from $1$ to $N$.
At every time step $t$, the process should transition to an adjacent state.
The probability of moving to the right (from state $n\...

**2**

votes

**0**answers

71 views

### How can we treat the generator of a discrete-time Markov chain as the generator of a Markov-jump process?

In the popular paper Weak Convergence and Optimal Scaling of Random Walk Metropolis Algorithms by Roberts, Gelman and Gilks, the authors state (see below) that "in the Skorokhod topology, it does not ...

**3**

votes

**2**answers

153 views

### Probability of one species reaching zero before the other in a Markov process on a 2d lattice

$\textbf{Background}$: Say we've got a two-variable system of stochastic chemical reactions, with quantities $\vec{x}(t) = (x_1(t),x_2(t)) \in \mathbb{N}^2$ evolving according to the following system, ...

**0**

votes

**0**answers

27 views

### Is there a Markov family that does not have an associated semigroup?

After reading some references, I found that many probabilists are cautious about whether or not a Markov family is associated with a semigroup, while many others assume its existence for granted.
So ...

**1**

vote

**0**answers

55 views

### Construction of Feller's pseudo-poisson process

Let
$(\Omega,\mathcal A,\operatorname P)$ be a probability space
$(E,\mathcal E)$ be a measurable space
$(Y_n)_{n\in\mathbb N_0}$ be a $(E,\mathcal E)$-valued time-homogeneous Markov chain on $(\...

**0**

votes

**0**answers

32 views

### Expression for the Markov Chain CLT variance for an arbitrary initial distribution

Let
$(\Omega,\mathcal A,\operatorname P)$ and $(E,\mathcal E,\pi)$ be probability spaces
$(X_n)_{n\in\mathbb N}$ be a $(E,\mathcal E)$-valued stochastic process on $(\Omega,\mathcal A,\operatorname P)...

**2**

votes

**1**answer

132 views

### non-backtracking random walk in regular (finite) graphs

I know that many things are known when dealing with random walks on a finite (or even infinite) graph: mixing time, returns to origin, etc. All is based in the use of the Markovian property of such a ...

**1**

vote

**0**answers

49 views

### Existence of Time-Reversed Markov Kernels

Suppose I have a probability measure $\pi$ and a Markov kernel $q$ which leaves $\pi$ invariant, in the sense that
\begin{align}
\int_x \pi(dx) q(x \to dy) = \pi(dy)
\end{align}
Then, a (the) time-...

**0**

votes

**1**answer

85 views

### how to derive stationary distribution of maximal entropy random walk

I was reading the paper 0810.4113v2, burda, which analyzed the stationary distribution maximal entropy random walk on the irregular lattice. I am confused on some of the steps.
Description:
The ...

**2**

votes

**0**answers

34 views

### Reference request: semimarkov processes

What are some good modern introductions to the theory of semimarkov processes? To be clear, by a semimarkov processes, I mean a Markov chain, together with "waiting times" between transitions, the ...

**0**

votes

**0**answers

16 views

### Semi-Markov Process sojourn time

I am having hard time to clearly understand a point related to Semi Markov Processes, based on this link.
From my understanding, in a Semi Markov Process, you have a probability $p_{ij}$ to ...

**11**

votes

**2**answers

482 views

### Reference Request: Theoretical Mixing Times Research in Machine Learning / Artificial Intelligence (AI)

I'm doing a PhD in probability theory, focusing mostly on mixing times. It's a pure maths PhD, considering precise models and showing rigorous mixing results. I'm also interested in stuff like machine ...

**3**

votes

**1**answer

76 views

### Bounds on $\|(P+\Delta)^n - P^n\|_F$ for stochastic matrices

Let us suppose that $P$ is a stochastic matrix (non-negative matrix with $P \mathbf{1} = \mathbf{1}$).
Let $\Delta$ such that $P + \Delta$ is a stochastic matrix (which means $P + \Delta$ is non-...

**4**

votes

**1**answer

212 views

### An interesting Markov chain with uniform marginals

Consider the Markov chain $(\theta_n, \phi_n)$ on $S^1 \times S^1$ constructed in the following way. For $\xi_n$ a sequence of i.i.d. normal random variables and $\kappa > 0$ a fixed number, we set
...

**0**

votes

**0**answers

45 views

### Invariant measures for a renewal process driven by Interarrival times bounded away from zero

Good morning, I apologize in advance if my question sounds too basic but after some research I was unable to come up with satisfactory answers to my doubts.
I am currently studying a model which ...

**2**

votes

**0**answers

49 views

### Random contractions and contractions on the space of measures

Let $(S,d)$ be some separable and complete metric space, and let $\mathbb{F}$ be some collection of functions from $S$ to $S$. Endow $\mathbb{F}$ with a suitable sigma algebra such that everything I ...

**4**

votes

**2**answers

164 views

### Lower bound on the entries of the Perron vector

Let $A$ be a matrix that satisfies all the conditions of Perron- Frobenius theorem. From the theorem it is known that the entries of the eigenvector corresponding to the largest eigenvalue will be ...

**2**

votes

**2**answers

92 views

### Central limit theorem for weak dependent bernoulli random variables

Suppose $\epsilon_1,\epsilon_2,...$ are i.i.d bounded random variables with compact support. Let $X_k=g_k(\epsilon_k,...,\epsilon_1)$ be Bernoulli random variables with the covariance between $X_i$ ...

**1**

vote

**0**answers

54 views

### Condition on $f := (I-\delta P)^{-1}g$ to ensure convexity of $f$?

Consider the following extension of the notion of convexity of continuous functions to functions defined over $\mathcal{I} = \{0,\ldots,n \}$ — that is, to vectors: $f$ is convex if for any $\alpha \...

**1**

vote

**1**answer

58 views

### Transition of probability in duality and its properties

Let $(E,\mathscr{E})$ be a measurable space. Two transition of probabilities
$p, q\colon E\times\mathscr{E}\to [0,1]$ are said to be in duality relative to
a probability measure $m$ if for every ...

**4**

votes

**2**answers

218 views

### Probability question about random shuffling of piles of rocks

I have $k$ piles of rocks placed on a circle so that every pile has exactly two neighboring piles. We know that initially the piles have $x_1,\dots,x_k$ rocks in each respectively. A monkey plays the ...

**3**

votes

**1**answer

81 views

### Positive and Null recurrence of Markov Chains on a General State Space

Suppose $X_n$ is an irreducible, aperiodic and Harris recurrent Markov chain. It is well known that in this case, $X_n$ has a stationary distribution $\pi$.
Are there any conditions that are ...

**1**

vote

**1**answer

45 views

### Measurability of kernel on generating set

Suppose $(X, \Sigma_X)$ and $(Y, \Sigma_Y)$ are measurable spaces such that $\Sigma_Y$ is generated by a set $B$.
Suppose $k : X \times \Sigma_Y \to [0, 1]$ has the property that $k(x, -)$ is a (...

**5**

votes

**1**answer

204 views

### Eigenvalue and eigenvector of ergodic Markov operator for continuous space Markov chain

As we know that the transition matrix $P$ of a Markov chain with finite space is a stochastic matrix, and from Perron-Frobenius Theorem, we know that the spectral radius of the matrix $P$ is $1$, and ...

**5**

votes

**0**answers

127 views

### 'Permutation Coupling' for Markov Chains

Suppose I have a Markov chain (discrete time, finite state space) on $[N] = \{1, 2, \cdots, N\}$, with Markov kernel given by a doubly stochastic matrix $P$. The double-stochasticity guarantees that ...

**2**

votes

**1**answer

104 views

### Stationary distribution for a Markov Chain on an uncountable space

Suppose $X_n$ are i.i.d. random variables on $\mathbb{R}$ with compact support, and define the Markov chain $Y_n=X_n +\frac{1}{Y_{n-1}}$ on $\Omega=\mathbb{R}\cup \{\infty\}$. Does the chain $Y_n$ ...

**0**

votes

**0**answers

37 views

### random walk in power set configuration space

I found a special random walk process description in context of artificial intelligence. The GenI process basically simulates decision taking in teams. It describes a time-discrete stochastic process
$...

**1**

vote

**0**answers

35 views

### Comprehensive reference for lumped or projected markov chains

Consider a Markov chain $X_n$ taking values in finite countable set $\mathcal{X}$ with transition matrix $P$. Consider a function $f:\mathcal{X}\to\mathcal{Y}$ inducing a partition $\mathcal{Y}=\{\...

**1**

vote

**1**answer

68 views

### Markov processes: Construction of the state variables

I have asked this question on stats.se.com but I did not receive an answer. Given is the description of a probabilistic finite state machine and I want to 'translate this' into a Markov process 'on it'...

**5**

votes

**1**answer

95 views

### Theory of random walks / spectral analysis of non-symmetric Markov chains

I'm reading about markov chains and how to analyze and bound their hitting / mixing times. However many of the useful results seem to require that the analyzed markov chain be symmetric. For reference,...

**2**

votes

**0**answers

75 views

### Ruelle-Perron-Frobenius for continuous time

I'm looking for a proof (or a reference for it) of the following result:
Let $L$ be a $n \times n$ $Q$-matrix, $p_0$ probability vector such that $L(p_0) = p_0$ and $V\colon \Omega \rightarrow \...

**2**

votes

**1**answer

102 views

### Computing the pseudo-spectral gap

In the paper "Concentration inequalities for Markov chains by Marton couplings and spectral methods", https://projecteuclid.org/euclid.ejp/1465067185, D. Paulin defines the pseudo-spectral gap for any ...

**3**

votes

**0**answers

116 views

### Finding a mixture of 1st and 0'th order Markov models that is closest to an empirical distribution

I am interested in finding the distribution "$p^*$" closest to an empirical distribution $\hat{p}$ where $p^*$ is a mixture of first and zeroth order Markov models. That is, I want to find $$
p^* = \...

**2**

votes

**1**answer

83 views

### Concentration of emperical conditional probability

Assume sequence $(X_1,X_2, X_3, \ldots)$ is a first-order Markov sequence of real random variables where $X_i \in \mathcal{X}$ for some alphabet $\mathcal{X}$ of finite size $k$. Define emperical ...

**10**

votes

**2**answers

217 views

### For which number of pairs is it an advantage to start in memory

Players A and B play memory starting with $n$ pairs of cards. We assume that they can remember all cards which have been turned. At his turn a player will first recall if two cards already turned ...

**1**

vote

**1**answer

65 views

### Does marginal Markov sequences imply jointly Markov property?

Assume sequence $(X_1,X_2, X_3, \ldots)$ is Markov sequence of real random variables where $X_i \in \mathcal{X}$ for some alphabet $\mathcal{X}$ of finite size $k$. Define random variable $Y_i = (X_{i-...

**3**

votes

**0**answers

72 views

### Find the generator of a markov process with constant decay and exponential jumps

Suppose we have a continuous time Markov process $(X_t)_{t\in [0,\infty)}$. This Markov process represents the queue length in amount of work left, therefore its state space is given as $S = [0,\infty)...

**13**

votes

**1**answer

399 views

### Does Lackenby's polynomial bound on knot moves imply polynomial mixing in “Quantum Money From Knots?”

In the 2010 paper Quantum Money from Knots Farhi, Gosset, Hassidim, Lutomirski, and Shor give a doubly stochastic Markov chain acting on grid diagrams. Transitions in the Markov chain are permutations ...

**1**

vote

**0**answers

70 views

### If the diameter of a bounded degree, directed graph is polynomial in the degree of the graph, is the mixing time also polynomial?

Given a directed graph $G=(V,E)$, with no self-loops, with a vertex that has a maximal out-degree $\le d\in O(\log |V|)$, and with a diameter $\text{diam}(G)\in O(\text{poly }d)$, consider converting ...

**0**

votes

**0**answers

196 views

### Time-inhomogeneous Markov chain

Let $(X_n)_{n\geq1}$ be a Markov chain over a finite state space $\Omega$, that is not time-homogeneous.
Suppose there exists $\epsilon>0$ such that for all $n\geq1$ and all $x,x'\in\Omega$ either ...

**1**

vote

**0**answers

47 views

### Non-homogeneous Markov chain on a finite state space

Let $\Omega$ be a finite state space. We consider a non-homogeneous Markov chain $(X_n)_{n\geq1}$ on $\Omega$. We denote for all $n\geq 1 $ and all $x,y\in\Omega$, $Q_n(x,y)=P(X_{n+1}=y|X_n=x)$.
Let $...

**9**

votes

**1**answer

392 views

### Is there a zero knowledge protocol for knottedness, similar to the GMW protocol for graph non-isomorphism?

In the very easy-to-read [1], Kuperberg shows that, conditioned on the Generalized Riemann Hypothesis, knottedness is in $\mathsf{NP}$. As I understand the proof, given a knot-diagram of a knot $K$, ...

**4**

votes

**0**answers

91 views

### Stationary distribution of mixture of Markov Chain with “complete” Markov Chain

I already asked this question in StackExchange, but found little attention. So I'm just going to copy-paste my original question here.
Let $P$ be a stochastic matrix (of an irreducible Markov Chain) ...

**1**

vote

**0**answers

43 views

### How to translate the triviality of computable Pareto optimality?

I asked this question on regular Math, and got the "Tumbleweed" badge for it (basically, it was ignored). I hope to get a better (any) response here.
I recently stumbled upon a paper relating to AI. ...

**1**

vote

**1**answer

115 views

### Upper Bound Lemma implies the Ergodic Theorem for Random Walks on Groups?

Cross-Posted from Math Stackexchange.
Ergodic Theorem A random walk on a finite group $G$ driven by a probability $\nu\in M_p(G)$ is ergodic if $\operatorname{supp}(\nu)$ is not concentrated
on a ...

**3**

votes

**2**answers

133 views

### Extinction of a Markov process with strong drift towards (a neighbourhood of) the absorbing state

Let $(X_t)_{t\in\mathbb{R}\geqslant 0}$ be a Markov Jump Process on a discrete state space $S\cup \{0\}$, with $0$ an absorbing state. If $T_0$ is the hitting time of $0$, I want to prove that
$$ \...

**1**

vote

**0**answers

146 views

### Difference between largest two eigenvalues of a graph Laplacian

The difference between the smallest eigenvalue and the next-smallest of a graph Laplacian (equivalently, the difference between the largest and next-largest of the random walk Markov chain on the ...

**1**

vote

**2**answers

337 views

### Proof of the existence of an optimal MDP with a stochastic reward signal?

I'm following Sutton's book on Reinforcement Learning, and he casually states that "There is always at least one policy that is better than
or equal to all other policies" for a given finite MDP. This ...