Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [markov-chains]

The tag has no usage guidance.

-1
votes
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
2answers
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
2answers
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
2answers
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 ...