The markov-chains tag has no usage guidance.

**1**

vote

**0**answers

203 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

268 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

468 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

130 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 $\mu_1$...

**1**

vote

**2**answers

641 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

366 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

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

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

646 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

674 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

447 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

161 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

581 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

733 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

875 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

102 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} \sum_{i=1}...

**8**

votes

**1**answer

390 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

477 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

817 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

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

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

**3**

votes

**1**answer

431 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

725 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

727 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

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

**66**

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

324 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

250 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

504 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

450 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

306 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

270 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 $\sigma$-...

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

673 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

316 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

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