The markov-chains tag has no wiki summary.

**62**

votes

**3**answers

3k 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 ...

**14**

votes

**5**answers

2k 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 ...

**14**

votes

**9**answers

2k 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 ...

**14**

votes

**1**answer

596 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 ...

**12**

votes

**4**answers

552 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 ...

**12**

votes

**3**answers

1k 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. ...

**12**

votes

**2**answers

1k 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 ...

**12**

votes

**1**answer

453 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 ...

**12**

votes

**0**answers

625 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 ...

**12**

votes

**0**answers

703 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 ...

**10**

votes

**4**answers

2k 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 ...

**10**

votes

**1**answer

657 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 ...

**10**

votes

**2**answers

3k 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 3x3x3 Rubik's cube, starting in an arbitrary configuration, can strictly be ...

**10**

votes

**2**answers

582 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 ...

**9**

votes

**0**answers

155 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 ...

**8**

votes

**1**answer

504 views

### Bounds on $||P^{k+1} - P^k||$ for $n$ by $n$ stochastic matrix $P$ with trace $n-1$ and integer $k>>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 ...

**8**

votes

**1**answer

272 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 ...

**8**

votes

**2**answers

592 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 ...

**8**

votes

**1**answer

371 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 ...

**8**

votes

**0**answers

103 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 ...

**7**

votes

**1**answer

231 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 ...

**7**

votes

**2**answers

302 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 ...

**7**

votes

**2**answers

287 views

### Examples of Slowly Mixing Chains in Statistics

This should probably be community wiki, but I don't know how to set that myself.
I'm looking for examples or Markov chains that are used in statistics or statistical physics, and which are known to ...

**6**

votes

**2**answers

813 views

### Expectation of first positive value in random walk

Let $p$ be a parameter in $]0,1[$. Let $(X_k)_{k\geq 0}$ be an independent, identically distributed sequence of random variables, such that each $X_k$ takes values only in
$\lbrace -1, \frac{1-p}{p} ...

**6**

votes

**1**answer

149 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 ...

**6**

votes

**1**answer

186 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])$ ...

**6**

votes

**2**answers

519 views

### References for a physicist migrating to stochastic processes

I've studied "Markov Chains" - Norris and "Measure, Integral and Probability" - Capinski, Kopp. Now, I'm looking for a couple of books (or other references) that help me bridging these two topics. ...

**6**

votes

**1**answer

182 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 ...

**5**

votes

**1**answer

295 views

### Elementary Markov Chain Question

Are any general conditions known on a finite transition nxn matrix that ensure that there exists at least one mth root which is also a transition matrix? It is easy to construct a 3x3 , diagonally ...

**5**

votes

**1**answer

366 views

### Probability of a set of random vectors over finite field being a spanning set

Suppose I have a set of random vectors $f(a_1, \ldots, a_\ell) := (v_1, \ldots, v_m) \subset F_p^n$, $m \ge n$, given by a matrix valued polynomial function $f$, where the $a_i$'s are independent, ...

**5**

votes

**2**answers

215 views

### Anticoncentration of the convolution of two characteristic functions

Edit: This is a question related to my other post, stated in a much more concrete way I think.
I am interested in anything (ideas, references) related to the following problem:
Suppose that $A ...

**5**

votes

**2**answers

605 views

### Is there a way to analytically compute the recurrence time of a finite Markov process?

Let $X_t$ be an ergodic (time-homogeneous) Markov process (in discrete or continuous time) on a finite state space $\{1,\dots,n\}$. Let $T(X_0)$ be the stopping time given by the infimum of times such ...

**5**

votes

**1**answer

657 views

### Efficient computation of Markov chain transition probability matrix

Consider a continuous Markov chain $X = (X_t)$ on a finite state space and let $Q$ be the (given) transition rate matrix. This matrix is very sparse, with non-zero values on 3 diagonals only (so from ...

**5**

votes

**0**answers

116 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

**5**answers

419 views

### Some questions concerning a random number process

Consider the following Markov process: Start with an integer $N = N_0$. Now repeatedly choose an $N_i$ uniformly at random in the range $[1...N_{i-1}]$ until $N_i = 1$ at which point one terminates ...

**4**

votes

**1**answer

286 views

### Combinatorial descriptions of the stationary distribution of a Markov chain

When I say "Markov chain" I think of a directed positively weighted (finite) graph, such that the sum of all edges going out of a vertex equals 1. Also I assume that it is aperiodic and irreducible.
...

**4**

votes

**1**answer

645 views

### A simple problem in markov chains

I'm trying to understand a 1954 paper of Kubo intitled "Note on the stochastic theory of resonance absorption". The specific problem can be stated mathematically as follows: let $X(t)$ be a random ...

**4**

votes

**1**answer

196 views

### Uniqueness of Gibbs Measure on Ising model

If I understood this correctly, the Gibbs Specification for the Ising model on $ℤ^d$ dos not have a unique Gibbs Measure for β above the critical level. But what about the Ising model on a finite ...

**4**

votes

**3**answers

480 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 ...

**4**

votes

**1**answer

148 views

### Log-likelihood in regime switching

Not sure if this question is too simple to be asked here...
In the following paper
Cho, Jin Seo, and Halbert White. "Testing for regime switching." Econometrica 75.6 (2007): 1671-1720. doi: ...

**4**

votes

**1**answer

206 views

### Approximating a hitting time for some state using the stationary distribution?

Provided a random walk on a bounded interval, with step probabilities, $p$ and $q$ and a stationary distribution $\pi$, how "bad" of an approximation is to assume that the hitting time for a position ...

**4**

votes

**1**answer

183 views

### Practical way to check for geometric convergence

Target distribution is multimodal, 24 dimensions, continuous state space. For MCMC integration (MH sampler) I use a manually tuned proposal distribution.
When I measure the convergence rate ...

**4**

votes

**1**answer

447 views

### When is a 1-block factor of a non-Markovian process Markov?

Let $Y$ be a discrete stationary stochastic process. Suppose that $Y$ is not $n$-step Markov for any positive integer $n$. Let $Z$ be a 1-block factor of $Y$. For what condition on $Y$ or the ...

**4**

votes

**2**answers

278 views

### Efficiently sampling points from an integer lattice.

Let $\mathcal{L}$ = {x$\in$ $N^n$ : ||x||$_1$ $\leq$ m} denote the set of integer points in the positive orthant of the $\ell_1$ ball of radius $m$, where $m < n$. For each $x \in \mathcal{L}$, let ...

**4**

votes

**0**answers

76 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 ...

**4**

votes

**0**answers

123 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

379 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

**4**answers

340 views

### Does the variance of a continuous time, time homogeneous, Markov process starting from one point necessarily not decrease?

Let $x_t$ be a zero mean, time homogeneous Markovian process (chiefly look at the case where the value is in $1$ dimension) over time $t$ starting from $x_0=0$. Is it necessary that, in continuous ...

**3**

votes

**2**answers

154 views

### Markov Partitions for toral automorphisms

I know that my question is more practical than theoretical. But, I do know where to look for the theoretical sources.
I want to find a program in the case that it exists (does it?), or to program it. ...

**3**

votes

**1**answer

316 views

### Probability-one event for Markov chain

Let $X$ be a Markov chain, with countable state space $I$ and transition probability matrix $P$. $X$ is irreducible, but need not be recurrent. Let $S$ be a fixed subset of $I$.
Define a subset $K$ ...