All Questions
Tagged with pr.probability markov-chains
362 questions
14
votes
3
answers
9k
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 ...
- 173
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 ...
- 101
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$.
...
- 39
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
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 ...
- 3
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 ...
- 2,133
2
votes
1
answer
421
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 ...
- 340
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 (...
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 $\...
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
17
votes
2
answers
953
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 ...
- 171
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 ...
- 313
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. ...
- 33
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, ...
- 4,466
4
votes
2
answers
835
views
Reference on continuous-time finite state filtering
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....
- 267
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}$
...
9
votes
2
answers
3k
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 ...
- 599
1
vote
2
answers
307
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,069
3
votes
1
answer
1k
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:
...
- 181
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 ...
- 5,191
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$ ...
- 1,069
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 ...
- 1,069
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....
- 911
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 ...
- 4,952
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)}...
- 15.4k
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 ...
- 241
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 [...
- 15.4k
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 ...
- 355
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
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 ...
- 4,466
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 ...
- 345
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
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
$$
...
- 1,655
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
3
votes
3
answers
2k
views
Statistics of a simple Markov chain
Imagine a two-state Markov chain which hops between the states $\pm 1$ with probability $p<1/2$, so that the autocorrelation function after $k$ steps is
$\rho_k = (2p-1)^k$
If I take an ...
- 823
2
votes
1
answer
186
views
scalar diffusions are reversible
It is well known that under mild assumptions a scalar diffusion $dX_t = a(X_t) dt + \sigma(X_t) dW_t$ with invariant probability distribution $\pi$ is reversible. This is indeed not true for ...
- 2,133
10
votes
1
answer
1k
views
Bounds on $\|P^{k+1} - P^k\|$ for $n$ by $n$ stochastic matrix $P$ with trace $n-1$ and integer $k\gg n$
The problem:
We have a $n$-state Markov chain with arbitrary initial distribution and transition matrix $P$ that is arbitrary except that we know that $P$ has trace $n-1$. Of course $P$ is also a ...
- 303
4
votes
1
answer
782
views
A simple problem in markov chains
I'm trying to understand a 1954 paper of Kubo intitled "Note on the stochastic theory of resonance absorption". The specific problem can be stated mathematically as follows: let $X(t)$ be a random ...
8
votes
4
answers
8k
views
Is there MDPs (Markov Decision Process) which have a non deterministic optimal policy?
I'm working on Markov Decision Process and I have not found yet an example of MDP that has a stochastic (non deterministic) optimal policy. Is there MDPs that have a stochastic optimal policy or is it ...
- 254
5
votes
2
answers
1k
views
Expectation of first positive value in random walk
Let $p$ be a parameter in $]0,1[$. Let $(X_k)_{k\geq 0}$ be an independent, identically distributed sequence of random variables, such that each $X_k$ takes values only in
$\lbrace -1, \frac{1-p}{p} \...
- 621
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 ...
- 2,133
1
vote
2
answers
661
views
Markov chain convergence problem.
Consider a markov chain matrix P of size n x n (n states).
P is known to be:
1- there are at least two absorbent states. one of them is denoted by null. (thus, we have that P_null,null = 1)
2- For ...
- 27
-2
votes
3
answers
2k
views
Convergence of a markov matrix
Consider a markov chain matrix P of size n x n (n states).
P is known to be:
1- Not irreducible (i.e. there exist at least a pair of states i, j such that we cannot go from i to j)
2- Not all ...
- 27
1
vote
1
answer
648
views
Lower bound on the convergence rate of a specific Markov chain
I have a Markov chain $\mathbf{A} = (A_0, A_1, \ldots)$ with state space $\{0, \ldots, n\}$ which converges towards a stationary distribution $\pi$. There are a lot of well-known results on upper-...
- 113
1
vote
0
answers
299
views
Markov Chain Patterns
Hi
I would like to detect repetitive patterns and deviations from these repetitions. I have historical data and can calculate probabilities for the transitions between my many states. I have ...
- 11