The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
333 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
2answers
4k 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
1answer
187 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
1answer
294 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
1answer
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 ...
10
votes
0answers
171 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
1answer
119 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
1answer
285 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
1answer
226 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
0answers
173 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
2answers
685 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
1answer
192 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
1answer
660 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
1answer
365 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
1answer
299 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
1answer
616 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
1answer
335 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
1answer
91 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
0answers
456 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
1answer
205 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
1answer
620 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
1answer
227 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
1answer
387 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
1answer
424 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
2answers
448 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
2answers
732 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
1answer
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
1answer
258 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
1answer
588 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
0answers
174 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
2answers
664 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
5answers
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
1answer
320 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
1answer
203 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
1answer
726 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
3answers
692 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
1answer
140 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
2answers
321 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
1answer
299 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
0answers
116 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
1answer
464 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
2answers
464 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
4answers
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
2answers
470 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
3answers
504 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
0answers
186 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
1answer
257 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
1answer
443 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
1answer
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
2answers
596 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 ...