The markov-chains tag has no wiki summary.

**1**

vote

**1**answer

349 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

138 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

232 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

255 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

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

**10**

votes

**2**answers

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

**4**

votes

**1**answer

188 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

296 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

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

**11**

votes

**0**answers

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

**0**

votes

**1**answer

120 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

293 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

232 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

176 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

727 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

195 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

688 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

369 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

308 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

624 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

347 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

92 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

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

**2**

votes

**1**answer

210 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

630 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

240 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

391 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

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

**0**

votes

**2**answers

457 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

779 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

229 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

259 views

### Connectivity of a graph with fixed number of vertices and edges

Hi,
first of all I want to mention, that I'm pretty new to graph-theory. Currently I'm about to write a path search algorithm and I want to take advantage of previous knowledge.
So this is the ...

**1**

vote

**1**answer

599 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

179 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

688 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

424 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

321 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

207 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

756 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

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

**0**

votes

**1**answer

142 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

323 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

301 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

117 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

468 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

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

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

478 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

522 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

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