Skip to main content

Questions tagged [markov-chains]

Stochastic processes (with either discrete or continuous time dependence) on a discrete (finite or countably infinite) state space in which the distribution of the next state depends only on the current state. For Markov processes on continuous state spaces please use (markov-process) instead.

Filter by
Sorted by
Tagged with
1 vote
1 answer
37 views

Generating function of $P_{11}^{2n}$

I am studying Markov chains and I am interested in calculating the generating function ($U(s)$) of $P_{11}^{2n}$, where $$ P = \begin{pmatrix} 0 & 1-\alpha & \alpha & 0 \\ ...
daniel's user avatar
  • 753
1 vote
1 answer
78 views

Let $\alpha_{ij}=\lim_{n\to\infty}\frac{1}{n}\sum_{m=1}^{n}~p_{ij}^m,~~i,j\in S.$ Show that above limit exist. [duplicate]

Consider an irreducible markov chain with finite state space $S$. let $P=[(p_{ij})]$ is given transition probability matrix and $p^n=[(p_{ij}]$ denote the $n-$ step transition matrix for the chain. ...
Ricci Ten's user avatar
  • 520
1 vote
1 answer
26 views

Confirmation of approach for conditional probability question

I'm looking for confirmation regarding my approach for this probability question: Half the people outside wear black socks, one third wear white, and one sixth are wearing red. What's the probability ...
Abhay Agarwal's user avatar
0 votes
0 answers
48 views

Existence of Borel set and probability measure

Let $X : \Omega \to \mathbb{R}^r$ and $Y : \Omega \to \mathbb{R}^s$ random vectors and let $(X,Y)$ have probability density $f(x,y)$ with product measure $\mu \times \nu$ for $\sigma$-finite measures $...
L N J's user avatar
  • 1
0 votes
0 answers
13 views

Sufficient condition for matrix factorization as an undirected graph random walk matrix

Let $A$ be an $n\times n$ row-stochastic matrix. Is there a sufficient condition for $A$ to be factorized as $D^{-1} W$, where $W$ is a symmetric adjacency matrix for a weighted graph and $D=W\mathbf{...
phil's user avatar
  • 162
1 vote
0 answers
40 views

Stationary distributions in Markov chains

This question is with regards to HMMT Guts 2021/28 and 2018/27. Caroline starts with the number $1$, and every second she flips a fair coin; if it lands heads, she adds $1$ to her number, and if it ...
PunySoloist's user avatar
0 votes
0 answers
22 views

$\mathbb P_{x_0}(\tau>t\mid X_1=x_1)=\mathbb P_{x_0}(\tau>t)$

Let $(\Omega,F,\mathbb P_x,(Y_t)_{t\geq 0})_{x\in E}$ be a continuous time Markov chain with countable state space $E$. I found the following identity on page 73 of Liggett's introduction to ...
Filippo's user avatar
  • 3,584
1 vote
0 answers
46 views
+50

Stochastic Simulation - Simulation from the Marginal Distributions

I am reviewing some material on MCMC / simulation and I realised I never quite understood this point. Given a joint distribution $f(x_1, ..., x_n) = f(x_1) f(x_2 | x_1)...f(x_n | x_{n-1}, ..., x_1)$ ...
InvestingScientist's user avatar
1 vote
0 answers
32 views

Optimal transition matrix that minimizes mixing time

For a finite state space, say I have a transition matrix $P$ such that it is irreducible and aperiodic. The stationary distribution is $\pi$. I wonder if there's any literature on how to pick an extra ...
Kryvtsov's user avatar
  • 131
2 votes
1 answer
74 views

Definition of a Markov process

I found 2 Definitions for a Markov process and I am trying to understand how they are connected. Let $X=\left(X_t\right)_{t\geq 0}$ be a $\mathcal{F}_t$ adapted Process. We say $X$ is a Markov ...
kays44's user avatar
  • 71
0 votes
1 answer
28 views

lower bound for the hitting time

I was reading the book by Meyn and Tweedie(2009), and on page 87 there's an inequality i dont know where it comes from. Here's the setup: Let $P(x,A)$ denote a transition kernel of a markov chain $X_n$...
Kryvtsov's user avatar
  • 131
1 vote
1 answer
50 views

Mean hitting time of position-dependent random walk

The question I am interested in a continuous-time random walk on $K$ states, numbered $0$ to $(K - 1)$. For each $k$: I call $p_k$ the transition rate from state $k$ to state $(k + 1)$; I call $n_k$ ...
Matteo Monti's user avatar
0 votes
1 answer
39 views

What are the conditions on a probability distributions such that the expected time to encounter a nonzero event (or events) is finite?

I know that any specific event (or a specific subset of events) with a non-zero probability will occur almost surely (i.e, with probability 1) at some point given an infinite sequence of events. My ...
Sefi Potashnik's user avatar
2 votes
1 answer
59 views

Question about notation in Durrett's book

I have been studying Markov Chains through Rick Durrett's book, more precisely I was focusing on the Markov Property (Theorem 5.2.3 on page 276 of the book available at: https://services.math.duke.edu/...
Monteiro_C's user avatar
0 votes
0 answers
27 views

Number of Shortest Paths Through Any Edge on a Discrete Torus

I am currently stuck with the following problem: Consider the setting of a random walk on a discrete torus with $d$ dimensions and grid Size $L$. That means considering a simple (no loops or multiple ...
Gabelstabler's user avatar
0 votes
1 answer
29 views

How to prove a Branching Process is transient for all $k>0$ and calculate extinction probability

Consider a branching process $\{z_n\}$. $z_0=0$, $z_{n+1}=\sum_{j=1}^{z_n}\xi_{z_nj}$ and the extinction probability is $\rho$. $\xi_{ij}$ are i.i.d. (i). If $\mathbb{P}(\xi_{ij}=1)<1$, prove that ...
Kaven Lin's user avatar
0 votes
1 answer
22 views

$\mu(x)\mathbb P_x(X_n=y,n<\tau)=\mu(y)\mathbb P_y(X_n=x,n<\tau)$

Suppose that we are given a discrete time Markov chain with reversible measure $\mu$. By definition, $$\mu(x)\mathbb P_x(X_1=y)=\mu(y)\mathbb P_y(X_1=x)$$ and by induction we even get$^1$ $$\forall n:\...
Filippo's user avatar
  • 3,584
1 vote
0 answers
84 views

Fundamental theorem of Markov chains for integrable functions

Let $(X_n)_{n\in \mathbb{N}}$ be an irreducible, positive recurrent and aperiodic Markov chain on a countable set $E$, with stationary distribution $\pi$. Let $f\in L^1(\pi)$. Is it true that $P^nf(x):...
No-one's user avatar
  • 667
2 votes
2 answers
129 views

A pawn moves across the fields of the board. Expected value of the number of moves after which the pawn will visit all fields.

A pawn moves across the fields of the board in the figure below, in each move, moving to one of the fields bordering a side or corner (each of the available fields has the same probability, the ...
thefool's user avatar
  • 1,054
0 votes
2 answers
56 views

A pawn moves between the vertices of a square ABCD. Expected number of the move in which the pawn first moves from point B to C. Solution verification

A pawn moves between the vertices of a square $ABCD$, in each move moving to one of the adjacent vertices - the choice of each vertex is equally likely choices at different steps are independent. ...
thefool's user avatar
  • 1,054
1 vote
1 answer
62 views

A pawn moves along the vertices of a tetrahedron $ABCD$. Probability that the pawn will return to $A$ before reaching $B$. Solution verification.

A pawn moves along the vertices of a tetrahedron $ABCD$, in each move moving to one of the adjacent vertices (each possibility has a $\frac{1}{6}$ chance), or staying put (with a probability of $\frac{...
thefool's user avatar
  • 1,054
2 votes
2 answers
99 views

Random walk on the edges of a square where staying at same position is allowed

The classic question of finding the expected number of steps to move from one corner of a square to the opposite. I found an intuitive way to do it by considering that we are at position $(0,0)$ and ...
Axo's user avatar
  • 301
0 votes
0 answers
23 views

How To Prove That The Absolute Convergence Of The One-Step Transition Matrix?

I am trying to prove that the n-step transition matrix in a Markov Chain satisfies the condition that the sum of each row is one (ie, each row is a valid probability distribution). I have done this ...
Azorbz's user avatar
  • 185
0 votes
0 answers
31 views

Help with Proof of Perron-Frobenius theorem in "Mathematics and Physics of Many Body systems"

In the book Mathematics and Physics of Many Body systems by Hal Tasaki, he gives a proof of a version of the Perron-Frobenius theorem (see below). However I don't follow the line in (2) Since $u_i m_{...
JvT's user avatar
  • 56
0 votes
0 answers
37 views

Relations between boundary and inner probabilities for 2D finite state Markov chains

In calculus the Green's theorem relates an integral around a curve to a double integral over the plane region bounded by that curve. Does there exist an analogy of this theorem for 2-dimensional ...
rrv's user avatar
  • 511
0 votes
1 answer
33 views

Markov Chain Detailed Balance $\pi(x)*P(x, y) = \pi(y)*P(y, x)$

Let's say I have a Markov chain and it has a transition matrix denoted as $P$. The $(row, column)$ elements of the $P$ matrix are denoted as $P(i, j)$. Just by looking at the transition matrix $P$, ...
PredsFan13's user avatar
0 votes
0 answers
10 views

In what sense is $q(\eta,\eta_x)$ the rate at which $\eta$ changes to $\eta_x$? (spin systems)

Let $S$ be a finite set and $E=\{0,1\}^S$. For $\eta\in E$ and $x\in S$, let $\eta_x\in E$ be the configuration obtained from $\eta$ by "flipping" the coordinate $x$, leaving the other ...
Filippo's user avatar
  • 3,584
0 votes
1 answer
66 views

What are the stationary distributions of this Markov Chain?

The Transition Matrix of the chain is : $$ \begin{bmatrix} 0 & 1/3 & 2/3 & 0 & 0 & 0 & 0 & 0 \\ 2/3 & 0 & 1/3 & 0 & 0 & 0 & 0 & 0 \\ 1/3 & 0 ...
Steve M.'s user avatar
0 votes
1 answer
34 views

For which values of $a$ is this Markov Chain irreducible and aperiodic?

The transition matrix is: $$ \begin{bmatrix} a & 1-a & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0\\ 1/2 & 0 & 0 & 0 & 1/2 \\ 0 & 0 & 1 & 0 & 0 \\ 0 &...
Steve M.'s user avatar
3 votes
0 answers
35 views

Expectation value in Markov process using backward generator and semigroup

For the past few days, I've been studying continuous time Markov processes. I was making some exercises and ran into trouble with the following: Consider a continuous Markov process. The state space ...
luki luk's user avatar
  • 189
1 vote
1 answer
47 views

Decomposing a general stopping time into stopping components

Let $(X_n)_{n \geq 0}$ be a discrete-time Markov chain taking values in a finite state space $S$, with transition matrix $P$. Let $(\mathcal F_n)_{n\geq 0}$ be the natural filtration and let $\tau \...
Jeffrey Jao's user avatar
1 vote
1 answer
46 views

Are Markov chains $X_{t+r}$, $X_{2t}$ and $(X_t; X_{t+1})$?

I'm trying to solve a problem. Let $X_n$ be a Markov chain with values in the set $H$. Will there be Markov chains $X_{n+r}$, where $r > 0$ is fixed, $X_{2n}$, $(X_n, X_{n+1}) \in H^2$? The first ...
noname's user avatar
  • 133
1 vote
0 answers
34 views

Prove: every strongly connected graph has at most one stationary distribution without manipulating with eigenvector

In mcs.pdf, Problem 21.12 says: A digraph is strongly connected iff there is a directed path between every pair of distinct vertices. In this problem we consider a finite random walk graph that is ...
An5Drama's user avatar
  • 416
0 votes
0 answers
21 views

Modified Markov chain

Let $x_t, y_t$ be to independent Markov chains with non-zero transition probabilities and two states {0, 1}. $t$ is a positive integer. $x_0 = 0, y_0 = 1$ . Process $a_t$ is defined as $a_t = c^{x_t} ...
ArtBac's user avatar
  • 1
4 votes
1 answer
146 views

circular random walk - markovian frog

Suppose there are $n$ lily pads on a unite circle. A frog is sitting on one of them at time $t=0$. Every minute, this frog makes a jump to a neighboring lily pad with a probability $p=1/2$. Find the ...
user147813's user avatar
0 votes
1 answer
25 views

Coupling identical Continuous-Time Markov Chains

In proving an irreducible positive recurrent CTMC $(X_t)_{t \ge 0}$, started in $\nu$, converges to its invariant distribution $\xi$, my lecture notes examine the coupled process of two independent ...
hegash's user avatar
  • 197
2 votes
1 answer
50 views

Finding References for known results about mixing time of a Markov chain arising from Gaussian elimination

I am looking for references for the known results on the following problem. Let $(X_t)$ be a Markov chain on $GL_n(F_2)$, where in each step, an ordered pair $(i,j)$ is chosen uniformly at random, and ...
mathematico's user avatar
0 votes
0 answers
14 views

Output process of Huffman encoding an i.i.d. source

A binary Huffman code for a pmf $(p_1,\dots,p_m)$ is constructed by starting with all $p_i$ as leaves and iteratively constructing a tree by merging the two nodes of lowest probability. Edges are then ...
hegash's user avatar
  • 197
1 vote
1 answer
36 views

Discrete Hidden Markov Model with continuous observation

Say I have a HMM system that can be in any of $n$ discrete possible states - say they are numbered $1$ to $n$ and can even actually be these integers. I know the transition matrix between different ...
Parker Lewis's user avatar
0 votes
0 answers
17 views

Hitting Times by Translation Invariant Processes with Asymptotic Velocity

I am trying to prove the following statement which seems to me intuitive, but I can't work out how to formalise it. Suppose you have a stochastic process $(X(t))_{t\geq 0}$ on $\mathbb{R}^d$ which is ...
user1598's user avatar
  • 395
0 votes
1 answer
44 views

Expected card draws until two consecutive aces $\mathbf{with\, replacement}$

Im trying to find the expected draws until there are two consecutive aces with replacement, using this formula: $E(X) = 13 + \frac{1}{13}+\frac{12}{13}(E(X)+1)\\E(X) = 13\times 14=182$ Is this the ...
kuwaitikiwi's user avatar
1 vote
0 answers
20 views

Number of transitions into and out of state j in continuous-time Markov chain?

In Introdution to Probability Models, it says that $$v_jP_j=\sum_{k\ne j}q_{kj}P_k, \text{ all states j }$$ and $$\sum_jP_j=1$$ have the interpretation that in any interval (0,t), the number of ...
Yan's user avatar
  • 11
0 votes
0 answers
21 views

How to prove that the convergence to a steady state exists if the change in transition probabilities are sufficiently slow?

Let's say we have a transition matrix $Q_{n}$ for each time step $n$ of a discrete Markov process, where it doesn't stay stationary for all time steps. I want to prove that if the change between each ...
magg13__'s user avatar
1 vote
0 answers
29 views

At what values ​of $p$ will the chain be recurrent?

Consider a Markov chain on $\mathbb{Z}$ with $p_{i,i+2} = p$ and $p_{i,i−1} = 1 − p$. At what values ​​of $p$ will the chain be recurrent? I know that a chain is recurrent if for any state $j$ $$\sum\...
ABlack's user avatar
  • 582
0 votes
0 answers
18 views

Are expected numbers of visits to a point for a random walk in $\mathbb Z^d$ explicitly known?

Let $\lbrace Z_n\rbrace$ be the standard random walk in $\mathbb Z^d$ starting at $0$ (i.e. $Z_0=0$ a.s.). Is there an explicit formula to compute the expected amount of visits to a certain point $(x,...
confusedTurtle's user avatar
1 vote
0 answers
46 views

Is it possible to observe the Strong Markov Property in real life?

I have been spending a lot of time trying to understand what exactly is the Strong Markov Property and what kinds of stochastic processes obey the Strong Markov Property and what kinds don't. In ...
konofoso's user avatar
  • 755
0 votes
0 answers
7 views

Convergence of p_ji (k) in irreducible, aperiodic finite Markov chains

Image for the question Hello, I can't prove the blue step? Can someone see how? It is known: All terms are =>0, m_ii=Sum k=1 to inf kf_ii, f_ji=sum k=1 to inf f_ji (k)=<1 . Sum i=1 to N of p_ji(...
asdfs's user avatar
  • 1
2 votes
1 answer
186 views

When do these Algebra Equations have solutions?

I am learning about the Stationary Distributions and Limiting Distributions of Markov Chains (I think these equations are true for both discrete time and continuous time): $$\text{1) Stationary ...
wulasa's user avatar
  • 399
1 vote
1 answer
36 views

Prove that is a Markov chain from definition

I have $P(U_n = 1) = P(U_n = -1) = \frac{1}{2}$. I have to check if $A_n = U_{n+1}U_n$ is a Markov chain. $U_1, \ldots, U_n$ are independent. I wrote that $A_{n-1} = U_{n-1}U_{n}$ so it is dependent ...
jupyter51's user avatar
1 vote
0 answers
35 views

Random walk metropolis within Gibbs

I tried to implement the Random Walk Metropolis within Gibbs algorithm from Marie Therese Wolfram's article on Inverse Optimal Transport, but I feel like there's an error. In the algorithm, they ...
user600785's user avatar

1
2 3 4 5
120