Questions tagged [markov-chains]
The markov-chains tag has no usage guidance.
564 questions
77
votes
3
answers
5k
views
Gromov's list of 7 constructions in differential topology
At the 2010 Clay Research Conference, Gromov explained that we know of only 7 different methods for constructing smooth manifolds. Working from memory, and hence not necessarily respecting the order ...
- 1,614
60
votes
10
answers
14k
views
"Surprising" examples of Markov chains
I am looking for examples of Markov Chains which are surprising in the following sense: a stochastic process $X_1,X_2,...$ which is "natural" but for which the Markov property is not obvious at first ...
- 708
19
votes
9
answers
3k
views
How can I generate random permutations of [n] with k cycles, where k is much larger than log n?
I've been thinking a lot lately about random permutations. It's well-known that the mean and variance of the number of cycles of a permutation chosen uniformly at random from Sn are both ...
- 14k
19
votes
5
answers
18k
views
Time-inhomogeneous Markov chains
I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...
- 191
18
votes
4
answers
3k
views
Markov chain on groups
Let $G$ be a permutation group on the finite set $\Omega$. Consider the Markov chain where you start with an element $\alpha \in \Omega$ chosen from some arbitrary starting probability distribution. ...
- 85.6k
17
votes
2
answers
2k
views
Random walk is to diffusion as self-avoiding random walk is to ...?
One can view a random walk as a discrete process whose continuous
analog is diffusion.
For example, discretizing the heat diffusion equation
(in both time and space) leads to random walks.
Is there a ...
- 151k
17
votes
2
answers
953
views
Convexity of spectral radius of Markov operators, Random walks on non-amenable groups
Let $P_1,P_2$ denote stochastic transition matrices on a countable set $I$.
Consider $P_1,P_2$ as operators on $\ell^2(I)$ given by multiplication.
Question
Under which conditions can we show that ...
- 171
16
votes
5
answers
4k
views
Where to publish a paper on the Mafia game?
I wrote a research paper "A mathematical model of the Mafia game" (arXiv:1009.1031 [math.PR]). However, I do not know where to publish it. As an undergraduate studying majorly physics, I have little ...
- 1,612
16
votes
0
answers
1k
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 ...
- 4,466
15
votes
2
answers
1k
views
Diagonalizing some matrices arising from Fourier transform on $S_n$.
Consider the function $f$ on $S_n$ which equals $1/n$ on all adjacent transpositions $(i,i+1)$, where we let $n+1 = 1$, and $0$ otherwise, and its Fourier transform $\hat{f}(\rho)$ evaluated at the ...
- 4,466
14
votes
4
answers
3k
views
Eigenvectors of a particular transition matrix
I am considering a Markov chain with $n$ states with a particularly nice structure. The transition matrix is as follows:
\begin{equation}\mathbf{P}=\begin{pmatrix}
0 & 0& \dots&0 & 0 &...
- 41
14
votes
3
answers
9k
views
Solving a Rubik's cube via a series of randomly selected (quarter-turn) Singmaster moves
In July of 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge demonstrated (computationally) that a $3\times3\times3$ Rubik's cube, starting in an arbitrary configuration, can ...
- 173
14
votes
1
answer
587
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 ...
- 2,185
14
votes
2
answers
2k
views
Markov chains: invariant measures and explosion
The following seems like such an elementary question, but I didn't get anywhere with it.
Suppose you are considering a Markov chain in continuous time which is transient and has an invariant measure (...
14
votes
1
answer
555
views
Ising model - phase transition vs rapid mixing
Consider a graph $G=(V,E)$ and Ising model on that graph, i.e. configuration space is $\Omega=${$-1,+1$}$^V$ and energy of a configuration $s \in \Omega$ is given by:
$H(s) = -\beta \sum_{u \sim v}s(u)...
- 3,323
13
votes
2
answers
697
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 ...
- 560
13
votes
1
answer
2k
views
Different uses of the word "ergodic"
There appear to be two definitions of the word ergodic.
The dynamical systems definition says that a measure space $(X,\mathit B, \mu)$ and measure preserving transformation $T: X \mapsto X$ is ...
- 718
12
votes
3
answers
1k
views
How to sample a uniform random polyomino?
A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, ...
- 7,857
12
votes
3
answers
4k
views
How to explain "Feller process" to an undergraduate student?
I had to explain in informal terms what a Feller process was, to undergraduate students who understand Markov property, Poisson processes and such. It was easy to define Levy process as generalisation ...
- 519
11
votes
4
answers
3k
views
What is the cover time of a random walk on a cube?
I can't quite figure this problem yet. There is an ant at one vertex of a cube. The ant goes from one vertex to another by choosing one of the neighboring vertices uniformly at random. What is the ...
- 241
11
votes
2
answers
2k
views
Can ergodic theory help to prove ergodicity of general Markov chain?
I am a beginner in ergodic theory. I have read some lecture notes(such as this and this) about it in hope that I could find something which helps to prove the ergodicity of some Markov chain taking ...
- 221
11
votes
1
answer
642
views
Random walk origin return monotinicity
Consider a Markov chain on $\mathbb{Z}^d$ with transition kernel $P$ for adjacent vertices (non-diagonal). Essentially this is a $d$ dimensional random walk with the probability of a transition ...
- 4,952
11
votes
0
answers
575
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,...
- 2,185
10
votes
1
answer
1k
views
Bounds on $\|P^{k+1} - P^k\|$ for $n$ by $n$ stochastic matrix $P$ with trace $n-1$ and integer $k\gg n$
The problem:
We have a $n$-state Markov chain with arbitrary initial distribution and transition matrix $P$ that is arbitrary except that we know that $P$ has trace $n-1$. Of course $P$ is also a ...
- 303
10
votes
2
answers
328
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 ...
- 883
10
votes
3
answers
3k
views
Trace inequality for non-reversible Markov chain
Let $P \in \mathbb{R}^{d \times d}$ be the transition kernel for a Markov chain with stationary measure $\pi$ and define $P^\ast$ to be the time-reversed transition kernel defined by $P^\ast_{ij} := ...
- 101
9
votes
2
answers
953
views
Direct proof of unique invariant distribution for ergodic, positive-recurrent Markov chain
I posted the following question on MSE, feeling that it perhaps isn't research level mathematics, but didn't get any bites. So, I am crossposting here.
The following ergodic theorem is well known.
...
- 165
9
votes
2
answers
3k
views
Is this a situation where triple mutual information is always non-negative?
Suppose I have three identically-distributed homogeneous continuous-time discrete state space Markov chains $X_1(t), X_2(t), X_3(t)$, $t\geq 0$. They evolve independently but share a common random ...
- 599
9
votes
1
answer
501
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$, ...
- 2,185
9
votes
0
answers
239
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 ...
- 891
8
votes
7
answers
1k
views
One observation of special type of square matrix exponentiation
I was studying the following type of matrices,
$$
A = \begin{pmatrix}
1 & x_{12} & \cdots &x_{1n}\\
0 & x_{22} & \cdots &x_{2n}\\
\vdots\\
0&\cdots&0&x_{nn}
\end{...
- 271
8
votes
3
answers
404
views
All two-point correlations equal to $0$, three-point correlation not $0$?
Let $a_1,a_2,a_3,\dotsc \in \{-1,1\}$ be a sequence. Suppose that, for all $j>0$ and all
$\epsilon, \epsilon'\in \{-1,1\}$, the proportion of $n\geq 1$ such that $(a_n,a_{n+j}) = (\epsilon,\epsilon'...
- 20.2k
8
votes
2
answers
748
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 ...
- 183
8
votes
2
answers
377
views
A family of skew-symmetric matrices corresponding to cycles in graphs
When investigating loops in Markov chains I ran into the following observation.
A cycle in a graph $G$ with $n$ vertices may be represented by a matrix $\Gamma \in \mathbb R^{n \times n}$ having the ...
- 985
8
votes
1
answer
429
views
Ising model on a cycle
The Ising model on $\mathbb{Z} / 2d\mathbb{Z}$ gives to the configuration $x=(x_0, \ldots, x_{2d-1}) \in \{-1,+1\}^{2d}$ a probability proportional to $\exp\\big(\beta \sum_i x_ix_{i+1} \\big)$. The ...
- 2,133
8
votes
4
answers
8k
views
Is there MDPs (Markov Decision Process) which have a non deterministic optimal policy?
I'm working on Markov Decision Process and I have not found yet an example of MDP that has a stochastic (non deterministic) optimal policy. Is there MDPs that have a stochastic optimal policy or is it ...
- 254
8
votes
1
answer
174
views
Equalizing Geometric means of Graph Cycles
Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are ...
- 183
8
votes
4
answers
1k
views
Invariant measure of Euler-Maruyama Discretisation of an Ito diffusion
Let $(X_t)_{t \geq 0}$ be a diffusion process with dynamics governed by the stochastic differential equation
\begin{equation}
dX_t = b(X_t)dt + \sigma(X_t)dW_t, ~~ X_0 = x_0,
\end{equation}
where $b,\...
- 203
8
votes
1
answer
438
views
Potts model simulation
I was wondering what were the state-of-the-art methods to simulate low temperature configurations of Potts-like models that exhibit a discontinuous phase transition. For models with a continuous phase ...
- 2,133
8
votes
1
answer
534
views
The cars problem, again
Consider the following simple problem: We are given $2n$ parking spots, labelled from 0 to $2n-1$. There are $n$ cars on the first $n$ spots, and the remaining $n$ spots are free. At every step, every ...
8
votes
1
answer
691
views
Probabilistic proof for derivative of invariant distribution of a Markov chain
Let $P$ be an irreducible Markov matrix, and $\pi$ its stationary distribution. Let $D$ be a perturbation matrix which is zero except for two entries in row $r$:
$$D_{rg}=+1 \qquad D_{r\ell}=-1.$$
Let ...
- 1,068
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 ...
- 19.7k
7
votes
2
answers
922
views
what is the number of paths returning to 0 on the hexagonal lattice
I am looking for an estimation of the number of paths of length $n$ going from 0 to 0 on the hexagonal (or honeycomb) lattice.
I can find plenty on references on self avoiding paths, but I am looking ...
- 1,352
7
votes
1
answer
535
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
...
- 10.3k
7
votes
2
answers
259
views
Slowest initial state for convergence of finite birth-and-death Markov chains
Consider the continuous-time birth-and-death Markov chain on $\{1,\cdots,n\}$ with all rates equal to $1$. Is it true that the convergence to equilibrium, in total variation distance, is slowest when ...
- 4,653
7
votes
1
answer
621
views
Does every (generalized?) Markov chain admit transition probabilities?
To pose the question let us start by recalling the following notions:
Transition Probabilities. A transition probability matrix between two measurable spaces $(S,\mathcal{S})$ and $(V,\mathcal{V})$ ...
- 486
7
votes
1
answer
296
views
Existence of Limiting Distribution for Moving Regions in Stat. Phys. Models
As the title (hopefully) suggests, I've been trying to prove (or disprove) the existence of a limiting distribution for a certain projection in a statistical physics model. I'll give the details of ...
- 101
7
votes
2
answers
698
views
Convergence rate of the convolution of almost uniform measures on $\mathbb{Z}_p$
Statement Given a finite abelian group $G$ and two independent random variables $X,Y$ taking values in $G$ and satisfying $d_{TV}(X,U_G)\leqslant \delta$ and $d_{TV}(Y,U_G)\leqslant \delta$ (where $...
- 696
7
votes
1
answer
422
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,...
- 171
7
votes
1
answer
337
views
First Collision Time for k Random Walkers on a Torus
I consider $k$ random walkers on $\mathbb{Z}^{d}/n \mathbb{Z}^{d}$, the $d$-dimensional torus of side length $n$. More precisely, I will define a Markov chain $Z_{t} = (X_{t}[1], \ldots, X_{t}[k])$ ...
- 71