The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
133 views

The problem of the drunkard in a valley [closed]

We consider a Markov chain on a subset of positive integers S = {0, 1, 2, 3, .......N}, with transition probabilities defined as follows: The chain jumps only one unit to the left or right. p(i, j) ...
5
votes
2answers
215 views

Anticoncentration of the convolution of two characteristic functions

Edit: This is a question related to my other post, stated in a much more concrete way I think. I am interested in anything (ideas, references) related to the following problem: Suppose that $A ...
4
votes
0answers
76 views

Best convergence rate for convolutions on $\mathbb{Z}_p$

Suppose, that we have sequence of i.i.d variables $X_1,\ldots,X_n$ taking values in $\mathbb{Z}_p$ such that $d_{TV}(X_1,U) < \delta$. How fast, in terms of $\delta$ and $n$ does the sum ...
7
votes
2answers
302 views

Convergence rate of the convolution of almost uniform measures on $\mathbb{Z}_p$

Statement Given a finite abelian group $G$ and two independent random variables $X,Y$ taking values in $G$ and satisfying $d_{TV}(X,U_G)\leqslant \delta$ and $d_{TV}(Y,U_G)\leqslant \delta$ (where ...
3
votes
0answers
179 views

Generalized Markov Processes on CW complexes of dimension > 1

Markov processes have a large variety of applications to physics and chemistry (as well as many other fields). Such processes are formulated on graphs, i.e., CW complexes of dimension one. It is ...
0
votes
3answers
581 views

Stationary distribution for bipartite graph

I was wondering if there is any stationary distribution for bipartite graph? Can we apply random walks on bipartite graph? since we know the stationary distribution can be found from Markov chain, but ...
2
votes
0answers
119 views

Kullback-Leibler Divergence of Stationary Distributions of Markov chains

Consider two finite Markov chains on the same state space, both assumed to be irreducible, with transition matrices $P$ and $Q$ and associated stationary distributions $\pi$ and $\tilde \pi$. Is it ...
1
vote
1answer
136 views

Optimum control of a probabilistic automaton

Suppose we have a probabilistic automaton and we assign a weight to each state. An "interaction strategy" would be a fixed map from states to inputs. Any interaction strategy could be used to ...
3
votes
0answers
315 views

Coin Toss Probabilities like Penney's Game

Generate a binary number, using coin toss. Until you receive a predefined sequence. What is the probability that the number is a multiple of some k. For example, the terminating sequence could be ...
4
votes
1answer
196 views

Uniqueness of Gibbs Measure on Ising model

If I understood this correctly, the Gibbs Specification for the Ising model on $ℤ^d$ dos not have a unique Gibbs Measure for β above the critical level. But what about the Ising model on a finite ...
1
vote
1answer
158 views

Regarding Ricci curvature of Markov chains

In Ricci curvature of Markov chains on metric spaces Yann Ollivier, defines a coarse Ricci curvature for a Markov chain with transition kernels $\{m_x\}$ defined on a metric space $(X,d)$ as follows: ...
0
votes
1answer
247 views

Markov Chain: state reduction

Hi I am trying to understand a proof in a paper (written by Isaac Sonin), I don't know if anyone could give me a clarification on the following: Firstly we have a Markov chain $\{Y_k\}$ with finite ...
2
votes
0answers
143 views

Markov operators and existence of ergodic measures

My question refers to the yesterday's question (see here) of John Learner and goes as follows: Can we deduce the existence of an ergodic measure if we know that an invariant measure exists, but the ...
2
votes
0answers
63 views

iterated mutinomial and hitting time

Let $N,k \geq 1$ be two integers and consider the following Markov chain on $[0,k\times N]^k$. It starts at $X^0=(N, N, \ldots, N)$ and $X^{n+1}$ is the realisation of a multinomial distribution with ...
0
votes
0answers
104 views

Inequality relating stationary probabilities and transition probabilities

Let $P$ be the transition probability matrix of a aperiodic irreducible DTMC and let $\pi$ be its stationary distribution. I would like to know if there is any literature on types of Markov chains ...
8
votes
0answers
103 views

Functions between Markov chains that preserve local harmonicity

Given two Markov chains with respective state-spaces $S$ and $T$, say that a function $\phi$ from $S$ to $T$ is holomorphic iff for all states $t \in T$, every real-valued function $f$ on $T$ that is ...
3
votes
1answer
137 views

Markov Chains based on sampled transition probabilities [closed]

If I have a process that transitions between states with some set, unknown probability, I can sample to find the transition probability. This probability is a sample average, with a well understood ...
1
vote
1answer
144 views

Is anything known about Large Deviation Principle for non additive functionals on Markov chains?

Let $\Sigma$ be a finite set of cardinality $|\Sigma |$ and $$\Pi = \{ \pi(i,j)\}_{i,j = 1}^{|\Sigma|}$$ a stochastic matrix (ie a matrix whose elements are non negative and such that each row sum ...
0
votes
1answer
134 views

A basic question on necessary and sufficient condition for positive recurrence

If state $j$ is recurrent and the following holds can it be called as positive recurrent ? $$\lim_{n -> \infty}\frac{1}{n}\sum_{k=1}^{n}p_{jj}^{(k)} > 0$$ I know that this a necessary ...
4
votes
0answers
123 views

Relaxation = absorption?

Let $A$ be a stochastic matrix, that is, the entries are non-negative and each row adds to $1$. Assume that it is primitive, that is, $A^n$ has only positive entries for sufficiently large $n$. We ...
2
votes
1answer
231 views

The first eigenvalue of a branching process matrix

Let $M$ be the real square matrix of a typed branching process, such that $M_{ij}$ is the expected value of offspring of type $j$ emanating from type $i$. We know that if the first eigenvalue if $M$ ...
1
vote
0answers
174 views

Stationary distribution of a countable state Markov chain

We assume the Markov chain to be countable state space, time-homogeneous. Does it necessarily have a stationary distribution? I found a paper on arXiv.org (http://arxiv.org/abs/math/0610707) that ...
1
vote
1answer
88 views

Empirical distribution of a collection of iid Markov chains

Suppose we have $N$ independent 2-point Markov chains each having a rate matrix $Q = [-1,1;1,-1]$ and stationary distribution $\pi = [0.5,0.5]$. At time $t=0$, we initiate the chains so that the ...
0
votes
0answers
93 views

when are two Markov chains same distributions

Let there be two Markov processes on the same state space (which is countably infinite), but different transition matrices, denoted by $P_{1}$ and $P_{2}$. Assume positive recurrence, irreducibility ...
5
votes
1answer
657 views

Efficient computation of Markov chain transition probability matrix

Consider a continuous Markov chain $X = (X_t)$ on a finite state space and let $Q$ be the (given) transition rate matrix. This matrix is very sparse, with non-zero values on 3 diagonals only (so from ...
1
vote
1answer
512 views

Hitting time probability in a Random Walk with possibility to die.

A Random Walker can move of one unit to the right with probability $p$, to the left with probability $q$ and it can jump again to the starting point with probability $r$ and die. Naturally $p+q+r=1$. ...
1
vote
1answer
234 views

Equivalent Markov Random Fields

Hi, Is it possible to have topologically different Markov Random Fields (few different edges) and yet yielding the same inference results ? Thanks!
1
vote
2answers
236 views

The limiting behavior of geometric random walk

I would like to know what the asymptotic limiting behavior is for the following random walk on $\mathbb Z^d$. By Donsker's invariance principle, I suspect that its behavior is diffusive, i.e., the ...
0
votes
0answers
279 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
1answer
488 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 ...
1
vote
1answer
215 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
1answer
135 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
1answer
206 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
1answer
239 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
0answers
273 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
3k 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
183 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
285 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
1k 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 ...
9
votes
0answers
155 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
117 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
273 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
211 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
152 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
582 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
177 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
547 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
357 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
286 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
596 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 ...