The markov-chains tag has no usage guidance.

**0**

votes

**0**answers

537 views

### Markov transition probabilities and negative binomial distribution.

A realization of a Markov process generates a sequence of interval lengths between transition from one state to another. A natural way of modeling the distribution of the lengths is as a negative ...

**1**

vote

**1**answer

890 views

### How to prove ergodic property from aperiodicity and positive recurrence

How to prove that in case of an irreducible, aperiodic and positive recurrent Markov Chain time average along sample paths is equal to the ensemble average ? i.e.
$$\lim_{n\to \infty }\frac{1}{n}\...

**1**

vote

**1**answer

467 views

### Stationary distribution for directed graph

I want to implement the algorithm of graph partitioning of sparse directed graph. In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random ...

**0**

votes

**1**answer

141 views

### Hidden Markov: representing joint probability for set of observations as a product of two subset probabilities.

Good day to everyone!
My question concerns Hidden Markov Models and is pretty basic. In one of the books ("Introduction to Machine Learning" by Ethem Alpaydin, 2nd Edition, p.373), I get the ...

**4**

votes

**1**answer

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

**0**

votes

**1**answer

278 views

### Estimates for the mixing time of a Markov Chain with biased initiation

Imagine I have some Markov process consisting of a biased random walk on the integers, over some interval $[0, L]$, with $+1$ and $-1$ step probabilities of $p$ and $q$, respectively, s.t. $(p + q) = ...

**1**

vote

**0**answers

449 views

### a problem on DTMC

For a Markov chain $\lbrace X_n, n\ge0\rbrace$ with transition probabilities $P_{i,j}$, consider the conditional probability that $X_n = m$ given that the chain started at time $0$ in state $i$ and ...

**12**

votes

**3**answers

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

**4**

votes

**1**answer

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

**0**

votes

**1**answer

300 views

### Simple markov chain problem

I know this is an easy problem, but I can't figure it out.
A particle takes discrete steps $σ_1,σ_2,σ_3,…,σ_n$ which take on values +1 or −1. However, $P(σ_i=+1)=p$ and $P(σ_i=−1)$ will be $1-p$.
...

**2**

votes

**1**answer

3k views

### Expected Hitting Time for Simple Random Walk from origin to point (x,y) in 2D-Integer-Grid

Consider a simple random walk on the lattice $\mathbb Z^2$ starting at the origin $(0,0)$ where in each step, one of the four adjacent vertices in chosen uniformly at random, i.e. with probability $1/...

**13**

votes

**1**answer

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

**0**

votes

**1**answer

133 views

### transition probability convergence for Harris chains - Durrett.

Dear mathoverflow.
This is a question to a proof in a graduate text. I have asked two professors at my university without help, so I hope it suffices in difficulty for this forum otherwise I ...

**8**

votes

**1**answer

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

**1**

vote

**1**answer

256 views

### Extending Wald's equation to two classes of i.d. random variables?

I try to adopt Wald's equation to a slightly more complex problem. In fact, after a full day, I found some solution now, but it has a confusing argument in the middle. Perhaps somebody can help me at ...

**2**

votes

**0**answers

188 views

### A repeated Balls in Bins Markovian Process

I have a graph $G=(V,E)$ with $|V|=n$ nodes. Define a markov chain matrix P on G (e.g. Metropolis-Hastings). I have $k$ random walkers which are deployed at time $t=0$ on the vertices of $G$ at random ...

**10**

votes

**2**answers

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

**1**

vote

**1**answer

204 views

### Distributions induced by (weighted) random walks on the integer lattice

Consider an integer lattice $\mathbb{Z}^2$ where grid points are separated by a distance $h$. Loosely speaking, a random walk of length $k$ is a sequence of lattice points $(x_1,\cdots,x_k)$ ...

**3**

votes

**1**answer

862 views

### Convergence of Markov chains in terms of relative entropy

Consider a finite state, irreducible Markov chain with a rate matrix $Q$ and a stationary distribution $\pi$. Suppose the chain starts with the initial distribution $p$ at time $0$, then at time $t$ ...

**2**

votes

**1**answer

375 views

### MCMC with progressive demollification of delta distributions

Edit: I simplified the example to a canonical case for clarity.
Given an integral $\int_{\Omega}{g(\mathbf{x})}$ with a well-posed integrand $g(\mathbf{x})$ defined on some multidimensional space $\...

**4**

votes

**1**answer

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

**14**

votes

**1**answer

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

**5**

votes

**1**answer

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

**1**

vote

**1**answer

98 views

### Continuous-time Markov chain to sample Bayesian posterior distribution

Given a Bayesian network and evidence for the values of a subset of the variables, a standard question is to compute the posterior distribution on the remaining variables. The Gibbs sampling technique ...

**4**

votes

**0**answers

648 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

**1**answer

233 views

### Stochastic processes having Markov kernels

Let $(\Omega_1, \mathcal{F}_1, P_1)$ and $(\Omega_2, \mathcal{F}_2, P_2)$ be probability spaces and suppose $(X_t)$ and $(Y_t)$ are real-valued stochastic processes defined on the respective spaces. ...

**3**

votes

**1**answer

687 views

### Difference in probability distributions from two different kernels

Let $(E,\mathscr E)$ be a measurable space and $P,\tilde P$ be two stochastic kernels on that space. I wonder how the induced measures $\mathsf P_x$ and $\tilde{\mathsf P}_x$ differ on the space of ...

**1**

vote

**1**answer

322 views

### One point on $\phi$-irreducibility

Let $P(x,A)$ be a stochastic kernel on a measurable space $(E,\mathcal E)$ and $G = \sum\limits_0^\infty P^n$ be its potential kernel. A $\sigma$-finite measure $\phi$ is called the irreducibility ...

**5**

votes

**1**answer

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

**3**

votes

**1**answer

470 views

### stochastic processes conditional on other stochastic processes

Problem: I'm working in reliability field and have seen papers written on the topic like process of failures when systems are functioning under unobservable (or observable) Markov-like environment, i....

**0**

votes

**2**answers

484 views

### Number of transitions of a markov chain in a time interval

Let us consider the homogeneous continuous time Markov chain $(X_t)_{t\ge 0}$ with two states {0,1} and the intensity matrix
$Q=\begin{pmatrix}-\lambda& \lambda\\\ \mu& -\mu\end{pmatrix}$
...

**9**

votes

**2**answers

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

**1**

vote

**1**answer

234 views

### Continuous family of Markov chains

Suppose I have a family of countable state-space, discrete-time Markov chains, indexed by a parameter $r \in \mathbb{R}$. The state space is the same for all values of $r$; the transition ...

**1**

vote

**1**answer

639 views

### Ergodicity of a Markov chain

Hi,
I'd appreciate some help on a Markov chain result I'm trying to show. I believe the following is sufficient for a continuous time Markov chain $(X_t)$ with a countable state space to be ergodic:
...

**1**

vote

**0**answers

262 views

### Comparing two Markov chains

I thought that this question is more appropriate for math.stackexchange, where I asked it, but seeing how I got no response, here it goes:
I am interested in the question of the positive recurrence ...

**2**

votes

**2**answers

887 views

### probability distribution of hitting nodes on a finite graph random walk

Consider a finite, undirected, scale-free graph $\{G}$, with uniform edge weights. We define a truncated random walk on $\{G}$ as a random walk that continues for exactly $\{k}$ steps. For an ...

**4**

votes

**5**answers

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

**3**

votes

**1**answer

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

**1**

vote

**1**answer

224 views

### Product of a transient and a positive recurrent Markov chain

Let $X$ be a transient Markov chain with countable state space $S(X)$. Let $Y$ be a positive recurrent Markov chain with countable state space $S(Y)$. (Time is discrete.)
Let $A \subseteq S(X)$ be ...

**10**

votes

**1**answer

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

**1**

vote

**3**answers

694 views

### Probability that a certain Markov process has produced a given state

I am looking for advice on the following practical problem. Please keep in mind that this came up in a practical application.
In the context of Markov chains, we have $N$ states, with $N$ very large....

**0**

votes

**1**answer

144 views

### Modification of a Markov process on the real line

Consider a real-valued Markov process $X$ with a transition density $f(x,y)$, i.e.
$$
\mathsf P[X\in A|X_0 = x] = \int\limits_A f(x,y)\,dy.
$$
For this process I want to find
$$
u(x) = \mathsf P[X_n &...

**1**

vote

**2**answers

327 views

### How to determine a specific graph process is Markovian or not ?

Say, here is a min-degree graph process, which starts with G_0 = the complement of K_n. Given G_t, choose a vertex u of minimum degree in G_t u.a.r., then a vertex v not adjacent to u in G_t u.a.r. ...

**1**

vote

**1**answer

304 views

### A bjection between two stochastic processes

Let x(t) be a Markov process. We define the stochastic process y(t) such that :
y(t) = x(f(t))
f : T -> T
T is the parameter set of the process x(t).
If we ...

**1**

vote

**0**answers

119 views

### A M/M/$\infty$ queue of depositors with compound interest

Hello, I'm trying to model a bank's liabilities using a queue. Suppose a bank begins with a cash reserve of $M$. Depositors are a M/M/$\infty$ queue; they arrive with rate $\lambda$ and deposit 1 ...

**12**

votes

**1**answer

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

**1**

vote

**2**answers

477 views

### Rate of decay of variance for a tensor product Markov process (100 pt bounty for good answer by 1800 EST Fri)

Let $Q$ be the generator of a well-behaved (not necessarily reversible) Markov process $X$ on $[n] = \{1,\dots,n\}$ and let $Q^\otimes = \sum_{m=1}^N I^{\otimes(m-1)} \otimes Q \otimes I^{\otimes(N-m)}...

**11**

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

495 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

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