The markov-chains tag has no wiki summary.

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

**2**

votes

**2**answers

480 views

### Spectral gap of a product of Markov processes

For $m \in [N] \equiv \{1,\dots, N\}$, let $Q^{(m)}$ be the generator of a (well-behaved) continuous-time Markov process on a finite state space $[n_m]$. Write $J \equiv (j_1,\dots,j_N) \in \prod_m ...

**2**

votes

**3**answers

533 views

### Markov random field with continuous index set

Hi
There's Markov random field (MRF) which, by my Wikipedia-based knowledge, is an extension of Markov chain. I'd like to think of it as going from 1D to higher dimensional spaces. Inherent in its ...

**1**

vote

**0**answers

192 views

### Is the variance of an eigenfunction of a finite state space aperiodic irreducible markov chain starting at a single state always non-decreasing?

I am reposting a previous question due to incorrect initial formulation.
Given an ergodic (aperiodic and irreducible) finite state space Markov chain $P$. Let $f$ be an eigenfunction, i.e., $P_t f = ...

**2**

votes

**1**answer

263 views

### is the variance of a test function of a markov chain always increasing?

Edits: Changed function to eigenfunction. I should have stated the problem with more explicit conditions. Anyways I realized the original formulation is not true, even when one starts at a single ...

**1**

vote

**1**answer

448 views

### Markov chain: Obtaining transition matrix from recurrence probabilities

Consider a markov chain with finite space { 0,1,..n} with transition probability matrix whose entries are $P_{ij}$. Let
$f_{ij}^n$ = probability that starting from state $i $ it goes to state $j$ ...

**3**

votes

**1**answer

128 views

### mutual hitting measure between two sets

Given disjoint nonempty subsets $X_1, X_2$ of the state space of a finite irreducible Markov chain, there are unique measures $\mu_1$ on $X_1$ and $\mu_2$ on $X_2$ such that (a) starting from a ...

**1**

vote

**2**answers

601 views

### Borel-Cantelli Lemma on MCs (absorbing states)

hi, I'm sorry if the question is silly, but I couldn't get my head around it for a while now.
In Markov Chains (MC) proving that a state is either recurrent or transient is through Borel-Cantelli ...

**2**

votes

**0**answers

346 views

### How to bound the second largest eigenvalue of a transition matrix of a non-irreducible Markov chain?

I have found several bounds (e.g., Cheeger, Poincare) for the case that the Markov chain is irreducible and reversible, however my Markov chain has one absorbing state. Any bound would be helpful, but ...

**0**

votes

**1**answer

613 views

### Convergence of sets

Let $E$ be a compact subset of $\mathbb{R}^n$. Let the density function $\phi(x,y)$ be Lipschitz continuous and such that
$$
\int\limits_E \phi(x,y)dy=1
$$
for all $x\in E$. Let us consider the ...

**3**

votes

**0**answers

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

**2**

votes

**2**answers

574 views

### Exist closed forms of the distribution of return time in markov chains?

Hi, I am interested in the distribution of return times in simple random walks on finite graphs.
Let $G$ be a connected finite graph with, with two independent random walks. If both random walks ...

**2**

votes

**2**answers

637 views

### Counterexample Markov process

Let $X$ be a homogeneous Markov process in a continuous time with value in the set $E$. Suppose that for some $T>0,x\in E, A\subset E$ we have
$$
P_x[X_t\in A] = 0
$$
for all $t\in [0,T]$ but
$$
...

**2**

votes

**1**answer

423 views

### Reachability for Markov process

Let $X$ be a Markov process (in continuous or discrete time) and define an event
$$
R(T,A) = (\exists t\leq T: X_t \in A).
$$
I have seen in one paper that
$$
\Pr[R(\infty,A)] = \sup\limits_{\tau} ...

**3**

votes

**3**answers

1k views

### Statistics of a simple Markov chain

Imagine a two-state Markov chain which hops between the states $\pm 1$ with probability $p<1/2$, so that the autocorrelation function after $k$ steps is
$\rho_k = (2p-1)^k$
If I take an ...

**2**

votes

**1**answer

159 views

### scalar diffusions are reversible

It is well known that under mild assumptions a scalar diffusion $dX_t = a(X_t) dt + \sigma(X_t) dW_t$ with invariant probability distribution $\pi$ is reversible. This is indeed not true for ...

**8**

votes

**1**answer

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

**4**

votes

**1**answer

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

**2**

votes

**2**answers

1k views

### Is there MDPs (Markow 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 ...

**6**

votes

**2**answers

847 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} ...

**0**

votes

**1**answer

100 views

### how to find a sequence of digits in base b such that each consecutive block of size k appears exactly once?

My question is most precisely stated in the title. As an example, if we consider base 10, and k=4, then I am asking, is it possible to have a sequence of length 10^4 + 3, such that each 4 digit number ...

**1**

vote

**1**answer

2k views

### How to do integration using MCMC?

I want to evaluate $I = \int_V f(\vec{x}) d\vec{x}$. The classical Monte Carlo method is to sample uniformly from within the integration volume $V$, and then compute $I \approx V \frac{1}{N} ...

**8**

votes

**1**answer

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

**1**

vote

**2**answers

464 views

### Markov chain convergence problem.

Consider a markov chain matrix P of size n x n (n states).
P is known to be:
1- there are at least two absorbent states. one of them is denoted by null. (thus, we have that P_null,null = 1)
2- For ...

**-2**

votes

**3**answers

689 views

### Convergence of a markov matrix

Consider a markov chain matrix P of size n x n (n states).
P is known to be:
1- Not irreducible (i.e. there exist at least a pair of states i, j such that we cannot go from i to j)
2- Not all ...

**15**

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

**1**

vote

**1**answer

315 views

### Lower bound on the convergence rate of a specific Markov chain

I have a Markov chain $\mathbf{A} = (A_0, A_1, \ldots)$ with state space $\{0, \ldots, n\}$ which converges towards a stationary distribution $\pi$. There are a lot of well-known results on ...

**3**

votes

**1**answer

387 views

### (Stochastic) matrix for which a stochastic matrix logarithm exists?

I think this is basically the inverse question of Matrices whose exponential is stochastic.
i.e. what are sufficient conditions on the matrix representation of an evolution operator of a (finite) ...

**13**

votes

**0**answers

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

**13**

votes

**0**answers

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

**1**

vote

**0**answers

256 views

### Markov Chain Patterns

Hi
I would like to detect repetitive patterns and deviations from these repetitions. I have historical data and can calculate probabilities for the transitions between my many states. I have ...

**13**

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

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

**3**

votes

**1**answer

319 views

### initial condition of a diffusion approximation

I am trying to prove that a certain sequence of Markov chains $x^N_k$ converges towards a diffusion process. The invariant measure of $x^N$ is $\pi^N$ and the Markov chain $x^N$ is started in ...

**7**

votes

**1**answer

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

**2**

votes

**1**answer

501 views

### “Induced” arrivals in an M/M/1 queue?

I'm a newcomer to the realm of queueing theory, so please bear with me :)
I'd like to model web server traffic with a modified M/M/1 queue.
In the simple case we have two parameters - $\lambda$ for ...

**4**

votes

**1**answer

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

**7**

votes

**2**answers

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

**3**

votes

**1**answer

265 views

### Finitarily Markovian Finite Factors of Bernoulli Schemes

By processes, I mean discrete, stationary stochastic processes, that is $(X,\mathcal{U},\mu,T)$ where $X$ is the set of doubly infinite sequences of some alphabet $A$, $\mathcal{U}$ is the ...

**13**

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

**5**

votes

**2**answers

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

**0**

votes

**1**answer

309 views

### Where can I learn about master equation?

I am reading a paper by Dorogovstev on structure of growing complex networks with preferential linking. I need to learn master equation for this.
I need a reference for the same.

**4**

votes

**2**answers

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

**16**

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