Questions tagged [markov-chains]
The markov-chains tag has no usage guidance.
203
questions with no upvoted or accepted answers
16
votes
0
answers
985
views
representation theoretic interpretation of Jack polynomials
Monomial symmetric polynomials on $n$ variables $x_1, \ldots x_n$ form a natural basis of the space $\mathcal{S}_n$ of symmetric polynomials on $n$ variables and are defined by additive symmetrization ...
11
votes
0
answers
539
views
Does Chu and Hough's solution to the mixing time of the 15-puzzle carry over to the Rubik's cube?
In his 1988 book Group Representations in Probability and Statistics , Diaconis considers mixing times of the 15-puzzle. He states:
Here is a simplified version: Consider the blank as a $16$th block,...
9
votes
0
answers
237
views
Is the P.M.F. of the first return time of a random walk monotone?
Suppose $X_1,X_2,\ldots$ are i.i.d. $\mathbb Z$-valued random variables such that the random walk
$$S_n=\sum_{i=1}^nX_i$$
is recurrent with some period $k\geq1$ (i.e., $\Pr[S_n=0]>0$ if and only if ...
8
votes
0
answers
130
views
Functions between Markov chains that preserve local harmonicity
Given two Markov chains with respective state-spaces $S$ and $T$, say that a function $\phi$ from $S$ to $T$ is holomorphic iff for all states $t \in T$, every real-valued function $f$ on $T$ that is ...
6
votes
0
answers
217
views
Is there a "promise" at the heart of mixing times for random walks on Cayley-graphs?
I'm interested in some questions about the computational complexity of bounding the mixing time of random walks on Cayley-graphs of finite groups like that of the Rubik's Cube Group $G$. Determining ...
6
votes
0
answers
542
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 ...
6
votes
0
answers
1k
views
Coin Toss Probabilities like Penney's Game
Generate a binary number, using coin toss. Until you receive a predefined terminating sequence. What is the probability that the number is a multiple of some $k$.
For example, the terminating ...
6
votes
1
answer
216
views
Finding cohesive (low exit probability) sets in a Markov process
The following is a fact about Markov chains that came up in a game theory paper. The purpose of this question is to ask if related notions or similar results are found elsewhere in probability, or are ...
6
votes
1
answer
363
views
Idempotent splitting for Markov kernels
Let $X$ be a standard Borel space and $e : X \to X$ a Markov kernel. Suppose that $e$ is idempotent, that is $e \circ e = e$, or written out using the Chapman-Kolmogorov equation,
$$e(A|x) = \int_X e(...
5
votes
0
answers
234
views
How to play golf in one dimension?
One-dimensional golf is a function $g$ on $\mathbb R$ such that
$g(x)= 1+\min_\mu E[g(x+N(\mu,c\mu^2))]$ if $|x|>1$ and 0 if $|x|\le 1.$
Here $N$ is the normal distribution, whose mean $\mu$ you ...
5
votes
0
answers
295
views
Distance on Markov-chains/graphs and discrete Ricci-flow
I am trying to know if there is a notion of "distance" or pseudo-metric between markov-chains or graphs.
For the purpose of the question, the graph is weighted, and can be considered as labelled, so ...
5
votes
0
answers
469
views
Hierarchical Random Walk (also known as Hierarchical Hidden Markov Model)
Let us consider the following hierarchical (recursive) random walk model, which is also known as the hierarchical hidden Markov model in computer science (https://en.wikipedia.org/wiki/...
5
votes
0
answers
93
views
Most visited vertex in a random walk with place dependent drift
Consider the following Markov chain on $\mathbb{Z}$:
$$
P(x,x+1)=1-P(x,x-1)=\frac{1}{2}+e^{-|x|}\cdot \mathbf{1}_{\{x\neq 0\}}
$$
Do there exist constants $c,C>0$ such that
$$
c\cdot P^t(z,z) \...
5
votes
0
answers
325
views
Maximal inequalities for square of partial sums
Let $S_n = \sum_{i \leq n} X_i$ be the partial sums of a nice sequence of random variables $X_i$. In my application, $X_i$ is a functional of a finite-state, irreducible, aperiodic Markov chain, so ...
4
votes
0
answers
165
views
Random walk on hexagonal lattice. First return to the origin
I'm trying to come up with the formula describing the number of paths on hexagonal lattice of length $2n$ that start at the origin $O$ and go back to $O$ but doing so for the first time at step $2n$ (...
4
votes
0
answers
280
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) ...
4
votes
0
answers
545
views
Optimal transport between two distributions in a Markov chain
In a previous question, given an ergodic Markov chain, I'm interesting in sampling as short a path as possible with prescribed distributions for its endpoints. In a comment, I propose that the ...
4
votes
0
answers
144
views
Mixing time for dimers on the square-octagon graph
Consider the "fortress graph" of order $n$ (see Figure 9 of http://faculty.uml.edu/jpropp/tiling/www/mdblum/arctic.html). It's been known empirically for twenty years that if one turns the set of ...
4
votes
0
answers
263
views
Generalized Markov Processes on CW complexes of dimension > 1
Markov processes have a large variety of applications to physics and chemistry (as well as many other fields). Such processes are formulated on graphs, i.e., CW complexes of dimension one. It is ...
4
votes
0
answers
278
views
Markov operators and existence of ergodic measures
My question refers to the yesterday's question (see here)
of John Learner and goes as follows:
Can we deduce the existence of an ergodic measure if we know that an invariant measure exists, but the ...
4
votes
0
answers
182
views
Relaxation = absorption?
Let $A$ be a stochastic matrix, that is, the entries are non-negative and each row adds to $1$. Assume that it is primitive, that is, $A^n$ has only positive entries for sufficiently large $n$. We ...
4
votes
0
answers
1k
views
The spectrum of a Markov Operator and Invariant Measures
Suppose I have a discrete-time Markov Chain (in an infinite dimensional state space $\Omega$) with Markov operator $P$, a linear operator on the space of bounded measurable functions on $\Omega$. (Or ...
3
votes
0
answers
73
views
A stochastic matrix $B = \lambda(\lambda I - A)^{-1}$ such that $B-B^2$ has a non-negative diagonal
I apologize if this is too elementary a question, but I have not been able to make much progress.
Consider a real matrix $A$ with $A_{ij} >0$ for $i \ne j$ and $\sum_{j} A_{ij} = 0$ for each $j$. ...
3
votes
0
answers
62
views
Second eigenvalue of primitive matrix
Let $A$ be a primitive $N\times N$-matrix with positive entries, that is there is $n>0$ such that $(A^n)_{i,j}>0$ for all $i,j$. For brevity, assume the entries consist only of $0$ and $1$.
The ...
3
votes
0
answers
51
views
Multi-type Galton-Watson-like process where only majority-type is allowed to reproduce
Are you aware of any research papers that have explored a multi-type Galton-Watson process in which only particles of the majority type are permitted to reproduce in each generation?
I've been unable ...
3
votes
0
answers
150
views
Local dimension of stationary measures for iterated function systems with an expanding map
Consider the iterated function system (IFS) $X_n$ on $I = [0,1] $generated by the functions $\Phi = \{f_1,f_2,f_3\}$ and the probability vector $P = (p/2,p/2,1-p),$ where:
$f_1,f_2: I\to I$, where $...
3
votes
1
answer
302
views
Concentration of very dependent Markov chains
Consider the following simple Markov chain $ X_1\to X_2\to\cdots\to X_n $ where each $X_i$ is $\{-1,1\}$-valued and $X_1\sim\mathrm{Unif}(\{-1,1\})$ (such that the chain is stationary).
The flip ...
3
votes
0
answers
79
views
Rate of convergence of sojourn times of Markov chains
Let $(X_0,X_1,\dots)$ be a time-homogeneous Markov chain with finite state space $\Omega$.
Assume that $(X_0,X_1,\dots)$ is irreducible and aperiodic and let $\pi$ be its stationary distribution.
By ...
3
votes
0
answers
60
views
Mixing times for the exclusion process with rejection
Consider the following Markov chain on $k$-subsets of $\{1,\ldots, L\}$, equivalently, sequences $x\in \{0,1\}^L$ with $k$ 1's.
Let $p_1,\ldots, p_L\in (0,1)$ and $q_i=1-p_i$.
At each step, choose an ...
3
votes
0
answers
81
views
How does one define the gradient of a Markov semigroup?
In the context of functional inequalities for Markov semigroups $(\mathcal P_t)_{t\ge0}$, what is one denoting by $\nabla\mathcal P_tf$? For example, I've found the following assumption in this paper:
...
3
votes
0
answers
61
views
Algebraic property of a transition matrix
Consider the simple random walk on $\mathbb{Z}^2$. Given a finite $\Sigma \subset \mathbb{Z}^2$, one can induce the random walk on $\Sigma$: set $\tau_0 = 0$, and define recursively $\tau_{n+1} := \...
3
votes
0
answers
200
views
Maximize an $L^p$-functional subject to a set of constraints
Let
$(E,\mathcal E,\lambda)$ and $(E',\mathcal E',\lambda')$ be measure spaces
$f\in L^2(\lambda)$
$I$ be a finite nonempty set
$\varphi_i:E'\to E$ be bijective $(\mathcal E',\mathcal E)$-measurable ...
3
votes
0
answers
87
views
Joint drunkard walks
The drunkard walk is a game where two players have $a$ and $b$ dollars, respectively, and they play a series of fair games (both risking one dollar in each game) until one of them goes broke.
My ...
3
votes
0
answers
118
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^* = \...
3
votes
0
answers
103
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)...
3
votes
0
answers
115
views
Approximating the *conditional* probability of 1D discrete random walk not having revisited the origin given last position
I'm looking for a good closed form approximation to the following conditional probability, with provable approximation guarantees.
Consider a 1D random walk on the integers, starting at the origin, ...
3
votes
0
answers
174
views
Spectral radius of infinite substochastic upper triangular matrix
Let $M$ be a Markov chain on $\{0, 1, 2, \dots\} \cup \{\delta\}$, where $\Pr(i \to j) > 0$ for $i, j \in \mathbb{N}$ only if $j > i$, and $\Pr(\delta \to \delta) = 1$. This represents a birth-...
3
votes
0
answers
111
views
Conditional expectation with respect to paths of a Markov jump process
I'm having some trouble detangeling how the conditional expectation in equation (2.13) in the article https://arxiv.org/abs/cond-mat/9811220 (Lebowitz, Spohn) is defined.
The context is as follows: ...
3
votes
0
answers
151
views
Sequential generation of any random graph
The high-level question is: can we generate any random graph with size $d$ using a Markov chain?
For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{...
3
votes
0
answers
64
views
Memorylessness of residence times for a Markov process
I'm stuck on the trivial problem of showing memorylessness of holding (residence) times for a continuous time homogeneous Markov chain on finite state space.
I have a homogeneous Markov process $x(t),...
3
votes
0
answers
142
views
The spring Markov chain on $\mathbb{N}$
I'm trying to understand and learn more about "almost surely bounded" Markov chains on countable state spaces. I'm looking for references where I can learn how to work with more complicated examples ...
3
votes
0
answers
350
views
Spectral radius of a column stochastic matrix perturbed by a rank-1 matrix
$P\in \mathbb{R}^{n\times n}$ is an irreducible column stochastic matrix. $P$ is also diagonally dominant. $w \in \mathbb{R}^{n} $ is a strictly positive vector satisfying $w^T \mathbf{1} = 1$ where $\...
3
votes
0
answers
190
views
Effects of merging states on the limiting distribution of a Markov Chain
Consider a discrete time, homogeneous, finite state Markov chain given by a stochastic $n\times n$ matrix $M$.
We also have a cost vector $w$ of size $n$ with non-negative integer costs. The cost of ...
3
votes
0
answers
156
views
Worst-Case Solution to (Stochastic) Matrix Inequality
EDIT: Some specific conjectures added.
This problem comes with an associated stochastic process, but I phrase everything as linear algebra in case somebody from a non-probability community has seen ...
3
votes
0
answers
300
views
Nonlinear Markov process
Consider the following nonlinear $\mathbb{R}$-valued stochastic recursive sequence:
$ X_{n+1} = F(X_n) + W_{n+1}, \quad (W_n)_{n\ge1} \stackrel{ \scriptsize \mathrm{i.i.d.} }{ \sim } \phi. $
How can ...
3
votes
0
answers
2k
views
Closed-form solution to a system of linear equations
Consider the following $n \times n$ matrix with a particularly nice structure:
\begin{equation}\mathbf{P}=\begin{pmatrix}
0 & 0& \dots&0 & 0 &1\\
0 & 0& \dots&0 & \...
3
votes
0
answers
476
views
Maximization of a total variation distance subject to another total variation distance in Markov chain
Suppose two dependent random variables $X$ and $V$ from finite alphabets $\mathcal{V}$ and $\mathcal{X}$ with known joint and marginal distributions are given. Let $P_{XV}$ and $P_X$ and $P_V$ are the ...
3
votes
0
answers
95
views
Best convergence rate for convolutions on $\mathbb{Z}_p$
Suppose, that we have sequence of i.i.d variables $X_1,\ldots,X_n$ taking values in $\mathbb{Z}_p$ such that $d_{TV}(X_1,U) < \delta$.
How fast, in terms of $\delta$ and $n$ does the sum $X_1+\...
3
votes
0
answers
748
views
Kullback-Leibler Divergence of Stationary Distributions of Markov chains
Consider two finite Markov chains on the same state space, both assumed to be irreducible, with transition matrices $P$ and $Q$ and associated stationary distributions $\pi$ and $\tilde \pi$. Is it ...
3
votes
0
answers
340
views
maximum variance unfolding
Consider positive weights $\pi_1, \ldots, \pi_n$ (one can suppose that they add up to $1$) and $n-1$ lengths $d_1, \ldots, d_{n-1}$.
Is there an analytical solution to the following problem:
find the ...