All Questions
Tagged with pr.probability markov-chains
362 questions
1
vote
1
answer
295
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!
- 200
4
votes
0
answers
282
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 ...
CommunityBot
- 1
2
votes
0
answers
74
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 $...
- 2,133
0
votes
1
answer
599
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 ...
0
votes
0
answers
151
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 ...
- 1,655
8
votes
0
answers
130
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 ...
- 19.7k
1
vote
1
answer
228
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 ...
- 7,514
19
votes
9
answers
3k
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 ...
CommunityBot
- 1
1
vote
1
answer
293
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 ...
- 710
7
votes
2
answers
404
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 ...
CommunityBot
- 1
2
votes
1
answer
2k
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}\...
CommunityBot
- 1
0
votes
1
answer
529
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) = ...
CommunityBot
- 1
11
votes
4
answers
3k
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 ...
CommunityBot
- 1
4
votes
1
answer
555
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 $...
- 6,711
1
vote
0
answers
1k
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 ...
- 23.2k
0
votes
1
answer
320
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$.
...
CommunityBot
- 1
4
votes
1
answer
213
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 ...
- 1,302
5
votes
1
answer
7k
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/...
- 53
2
votes
1
answer
422
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 ...
CommunityBot
- 1
0
votes
1
answer
165
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 ...
- 1,352
8
votes
1
answer
429
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,411
14
votes
2
answers
2k
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 (...
- 3,069
2
votes
1
answer
447
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 $\...
- 101
4
votes
1
answer
587
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.
...
- 406
5
votes
1
answer
476
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 ...
- 20.2k
4
votes
0
answers
1k
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 ...
- 509
3
votes
1
answer
335
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. ...
- 1,122
6
votes
1
answer
663
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, ...
- 148k
2
votes
1
answer
640
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} \...
- 1,655
0
votes
2
answers
571
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}$
...
1
vote
3
answers
871
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....
CommunityBot
- 1
4
votes
5
answers
492
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 ...
CommunityBot
- 1
2
votes
1
answer
395
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$ ...
CommunityBot
- 1
1
vote
1
answer
332
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 ...
- 5,721
1
vote
0
answers
129
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 ...
- 309
11
votes
1
answer
642
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 ...
- 17k
1
vote
2
answers
515
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)}...
CommunityBot
- 1
3
votes
1
answer
574
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 ...
CommunityBot
- 1
2
votes
2
answers
861
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 [...
- 23.2k
3
votes
3
answers
1k
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,468
2
votes
0
answers
281
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 = ...
- 4,466
8
votes
1
answer
438
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 ...
- 31
3
votes
1
answer
295
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$-...
CommunityBot
- 1
3
votes
1
answer
145
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$...
- 19.7k
2
votes
2
answers
1k
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 ...
- 5,721
0
votes
1
answer
938
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-...
- 1,655
4
votes
1
answer
468
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 ...
CommunityBot
- 1
3
votes
0
answers
341
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,133
2
votes
2
answers
959
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 ...
- 23
2
votes
2
answers
1k
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
$$
...
CommunityBot
- 1