Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
0answers
8 views

Population distribution vector as time goes to infinity?

I'm looking for help with finding the following: Given a starting population distribution vector p0 = cv1 + dv2, find the population distribution vector as time (t) goes to infinity, p∞. I have the ...
0
votes
1answer
22 views

Markov Memoryless Property confusion with counterexample

Consider the following transitions: $$P(X_2=d|X_1=b)=P(X_1=d|X_0=b)=3/4$$ By Markov property, all what happened before $X_1=b$ doesn't matter: So when I see $P(X_2=d|X_1=b)$ I know that I can ...
0
votes
0answers
30 views

Markov Property Examples

Let $(X_{t \in \mathbb{N_0}})$ be a Markov Chain with states $E$. Let $A,B \subseteq E$ with $x_0,x_1 \in E$. Prove the following: $P (X_2 ∈ B|X_1 = x_1 , X_0 ∈ A) = P (X_2 ∈ B|X_1 = x_1 )$. $ P(X_2 ...
4
votes
1answer
56 views

Why are these two definitions of Markov property equivalent?

Question Suppose that $S$ is a finite or a countable subset of $\mathbb R$ and $(\xi_n)_{n\in\mathbb N}$ is an $S$-valued sequence of random variables. Then are these two definitions of Markov ...
1
vote
0answers
11 views

Harmonic functions on an irreducible recurrent Markov chain are constant

I would like to show that if $(X_n)$ is an irreducible recurrent Markov chain (on a countable space), and $f \geq 0$ is harmonic, then it is constant. I do the following: for any $x$, $f(X_n)$ is a ...
1
vote
1answer
26 views

Difference between non-homogeneous Markov and Semi-Markov?

I have been going around with Markov family lately and now bit confused. As per my understanding, to satisfy Markov property, state holding time distribution needs to be exponential otherwise the ...
0
votes
1answer
23 views

Expected number of visits for a recurrent Markov chain

Let $(X_n)_{n \geq 1}$ be a recurrent irreducible Markov chain on a countable space. Let $a$ be a fixed point and $\tau$ be a stopping time such that almost surely $X_{\tau} = a$. For any $x,y$ let $G(...
0
votes
0answers
11 views

Fundamental matrix of a markov process with binomial transition probabilities

I'm studying a Markov process with $n$ transient states and one absorbing state (indexed $1, \ldots, n+1$), with transition probabilities given by the $n+1\times n+1$ matrix $P$ where the probability ...
0
votes
0answers
19 views

Limiting distribution of Markov chain

The markov chain with states {0,1,2,3,4} has transition matrix $$P=\begin{pmatrix} 0 & p & 0 & 0 & 1-p \\ 1-p & 0 & p & 0 & 0 \\ 0 & 1-p & 0 &p &0 \\ 0 &...
0
votes
0answers
22 views

Finite invariant measures for reversible Markov chain

I look at a reversible Markov chain on a countable set $G$, i.e. if $p_{xy}$ is the transition probability from $x$ to $y$, there is a positive function $\pi$ such that $$ \pi(x) p_{xy} = \pi(y) p_{...
0
votes
0answers
14 views

Application of these “limiting probabilities”

I have been taking a look at some basic properties of discrete markov chains. Let $S$ be a Markov Chain with a finite state space and with transition matrix $P$. It is well know that under some ...
1
vote
2answers
51 views

Probability that a random walk reaches an arbitrary value in a given number of steps

I have a simple random walk over $\mathbb{Z}$: $X_{i+1} = X_i - 1$ (probability $p$) or $X_i + 1$ (probability $1-p$) and $X_0=0$ I want to find the probability of reaching an arbitrary negative ...
1
vote
1answer
12 views

Difference between two definitions for recurrence

Let $\{X_n\}$ be a Markov chain on a state-space $E$. A state $i$ is recurrent if $$P(X_n = i\;\text{for some} \;n\geq 1|X_0=i) = 1\tag{Definition 1}$$ $$\text{for some}\; n\geq 1\; P(X_n=i|X_0=i)=1\...
0
votes
0answers
28 views

First-Visit vs Every-Visit Monte Carlo

I have recently been looking into reinforcement learning. For this, I have been reading the famous book by Sutton, but there is something I do not fully understand yet. For Monte-Carlo learning, we ...
0
votes
0answers
14 views

Looking for examples for the notion of cocycles.

A set $G$ endowed with an associative binary operation is called a semigroup if it possesses an identity element. Thus a semigroup is short of a group in that it may not be closed under inverses. Let ...
0
votes
0answers
14 views

Probability of reaching a trajectory in a Markov chain before another?

Suppose I have a markov chain given by the transistion probability matrix $Q$. Suppose I also have $2$ trajectories, $t_1, t_2$. I want to calculate the probability that I would get trajectory $t_1$ ...
0
votes
0answers
14 views

Prove the sufficient and necessary condition for Markov chains to have a unique stationary distribution?

I learned that the sufficient and necessary condition for a finite state Markov chain to have a unique stationary distribution is there's only one closed communication class. For example from this ...
0
votes
0answers
15 views

DTMC: given recurrent state I and I communicate with j,How to compute P(T$_{I}$ < infinity|X0 = j)?

Given a recurrent state i ,i and j communicate. How to compute Pr{T$_{i}$ < $\infty$|X$_{0}$ = j}? The hint is to use k-step analysis(which is similar to first-step analysis), I know that the ...
1
vote
0answers
39 views

Proving property of Markov chains.

There is a proof of the following Markov-chain I don't understand. I have circled in red the two steps I do not understand. Could you please explain the steps for me? In the proof they also refer to ...
1
vote
0answers
18 views

Notation for state space

I am trying to describe a state space of a process in mathematical notation. The process begins with L individuals, $X(i)$, all of a unique starting type $X_0(i)$. At each time step, a new ...
0
votes
0answers
13 views

The u* rate for M/M/2 queue to have same “average waiting time in queue of a customer” with M/M/1 system with rate u

Ok here is the question, in a supermarket I have one cashier with u and a single M/M/1 queue, Suppose I want to get 2 cashier with same rate u*.What would should be the u* value for me to have same" ...
0
votes
0answers
34 views

Martingale problem with time-homogeneous Markov chain and a Poisson process

Let $(\Omega,\mathcal A,\operatorname P)$ be a probability space $(\mathcal F_t)_{t\ge0}$ be a filtration on $(\Omega,\mathcal A)$ $(E,\mathcal E)$ be a measurable space $(Y_n)_{n\in\mathbb N_0}$ be ...
2
votes
1answer
39 views

Stochastic Process - Markov Chain

It is common practice to have standby redundant units in mechanical and electrical systems so as to attain a high degree of reliability. Suppose two machines are available, one in use and one on a ...
3
votes
2answers
126 views

Show that there does not exist a unique stationary distribution.

So I was doing some self study and came across a proposition in one of my chemical engineering course's prescribed textbooks. I can't quite get the proof out. It's to do with a particle moving through ...
0
votes
0answers
40 views

Random Replacement

for each round I do have 2 sets (non distinguishable) where I need to place 2 balls A,B. In the first step of each round I place A first then B (the order is always A then B and not allowed to change)...
0
votes
0answers
12 views

Probability measure on $A^\mathbb{N}$ for Markov chains

Let $A$ be a finite set, $\Omega = A^N$, with $N \in \mathbb{N}$ or $N = \infty$ and let $\mathcal{B}(\Omega)$ be a $\sigma$-algebra of $\Omega$. Consider $\omega \in \Omega$ such that $\omega = (x_1, ...
1
vote
1answer
14 views

Trace of a doubly-stochastic matrix

Is there anything special about the trace of a doubly-stochastic matrix ? Formally, let $\mathbf{A}$ be doubly-stochastic of size $n$, and write $\mathrm{Tr}(\mathbf{A}) = \sum_{i = 1}^{n} \mathbf{A}...
0
votes
0answers
20 views

Deriving matrix equation for first passage times in Markov Chains

I'm trying to understand a step in my class notes on deriving the matrix equation which allows us to compute expected first passage times for finite state Markov Chains. The notes proceed as follows, ...
0
votes
0answers
11 views

Does longer input for a markov chain cause longer output on average?

When I have a simple markov chain with a fixed number of states and a fixed number of terminal states, does weighting transitions from a training set of longer sequences cause the chain to produce ...
0
votes
0answers
22 views

Branching process with two types and its extinction probability

I am considering a branching process with two types. I shall designate them with 1 and 2. The branching process follows Poisson distribution. So to that end I may write the probability generating ...
2
votes
1answer
90 views

Stationary distribution and limiting distribution of a random walk

Consider the random walk on $S={0, . . . , N}$, defined as follows. We are given $p, q, r >0$ with$ p+q+r= 1$. The walk increases by 1 with probability $p$, decreases by 1 with ...
0
votes
0answers
18 views

Probabilities and Steady State Vector in a Markov Chain

I have a problem where I have to calculate what the probability of a person being denied service in a phone queue. The states go from no-one in the queue to the queue being full. I have found the ...
0
votes
0answers
12 views

Relation between v(s) and q(s,a) in a Markov Decision Process?

I was solving questions related to backup diagrams from Reinforcement Learning: An Introduction by Barto and Sutton. Are these 4 equations mathematically correct ? Are there any shortcomings in terms ...
1
vote
0answers
14 views

Connections between the randomness of the normal distribution and Textrank?

In a TED speech on 8:40 the mathematician said that: This algorithm uses the laws of mathematical randomness to determine automatically the most relevant web pages, in the same way as we used ...
0
votes
0answers
7 views

Aperiodic states interpretation problem

After reading about periodicity of states in Markov chains I have problems understanding intuitively the aperiodic states. Following the Wikipedia definition if the return to one state can be done in ...
1
vote
0answers
42 views

“Two step” Markov chain is actually a Markov chian

Let $X$ be a compact metric space and $\mathcal X$ be its Borel $\sigma$-algebra. Let $\mathscr P(X)$ be the set of all the Borel probability measures on $X$. A Markov chain on $X$ is a measurable map ...
1
vote
1answer
24 views

Using strong law of large numbers to prove transience

I'm trying to work my way through a problem which defines $N_t$ as a Poisson process of rate $\lambda$ and $ X_n = N_n − n,\quad\text{for }\; n = 0, 1, 2, \ldots $ I've explained why $X_n$ is a ...
0
votes
0answers
19 views

Ruin probability is independent of initial time

Currently I am reading Notes on Markov Chains. Context: We consider an amount of $S$ dollars which is to be shared between two players A and B. We let $X_n$ represent the wealth of Player A at time $...
1
vote
1answer
32 views

Applications of the Markov Property

The Markov property for a discrete state time stochastic process is defined as: $$\mathbb{P}(X_n=x_n\mid X_{n-1}=x_{n-1}, \dots, X_0=x_0)=\mathbb{P}(X_n=x \mid X_{n-1}=x_{n-1})$$ A corollary is $$\...
2
votes
1answer
65 views

Probability a knight on a chess board is back where it started after $n$ moves

I'm trying to work my way through a problem concerning a random walk by a knight on a chessboard. I've modeled the board as a graph with 64 vertices and the random walk on the graph as a Markov chain ...
0
votes
0answers
10 views

Expectation for Markov chain edge visits

Let $X_i$, $ i=0,1,2,\dots$ be a Markov chain with states $1,2,\dots, n$ and transition matrix $[p_{ij}]$. How can we calculate the expected number of times the edge $a \to b$ is used after $M$ ...
0
votes
0answers
46 views

Markov Chain:Symmetric Random Walk is Null Recurrent (Proof verification)

Consider the one-dimensional symmetric random walk: States: $0$, $\pm1$ ,$\pm2$, etc.. $P_{i,i+1}=P_{i,i-1}=1/2$. It was shown before that this random walk is recurrent. Let $\pi_i$ denote the long ...
0
votes
1answer
21 views

Intuition behind a simple random walk on integer lines

Consider a random walk on a line of integers. Suppose we start from the state $x$. Then, the probability of jumping from $x$ to $x+1$ is $p(x, x+1)=p$, and the probability of jumping from $x$ to $x-1$ ...
0
votes
0answers
19 views

Rank of a stochastic matrix

Are there any findings about the rank of a square or fat ($m\times n$-dimensional, $m<n$) stochastic matrix? I would appreciate any pointers.
3
votes
0answers
52 views

A probability concerning the maximum and minimum of a simple random walk

Let $X_i$ be i.i.d. such that $\mathbb P(X_i = 1 )=\mathbb P(X_i=-1) =\frac1 2$. Let $a\in \{1,2,....\}$, now define the random walk, $S_0=a$ and $$S_n = a+\sum_{i=1}^n X_i$$ Now define the maximum ...
1
vote
0answers
16 views

Existence of solution to system of linear equations with stochastic coefficients matrix

Given an underdetermined or determined system of linear equations, can anything be said about existence of a solution if the coefficients matrix is a stochastic matrix, i.e., its rows sum up to 1? I ...
0
votes
0answers
33 views

Reference for the theory of Markov chains on a general state space.

I am interested in learning the theory of Markov chains on a state space $X$ when $X$ is allowed to be more than just a finite set, especially when $X$ is a compact metric space or more generally a ...
2
votes
3answers
57 views

Probability of a Markov chain pursuing an infinite single path

Let $X=(X_n)_{n\ge 1}$ be a (time-homogeneous) Markov chain on a countable state space $S$. I wonder if $X$ is irreducible, recurrent and aperiodic, then necessarily $P(X=s)=P(X_1=s_1,X_2=s_2,\ldots)...
0
votes
0answers
14 views

Getting started with ngram distribution

I need help getting started with this problem. So if the vocabulary is V = {a,b}, and the sentence is based on the vocabulary. we get $$\sum_{w_1,w_2...,w_n}P(w_1,w_2,...w_n) = \sum_{w_1,w_2,...,w_n}...
0
votes
1answer
25 views

Is the 2-norm of the consensus part of a primitive row-stochastic matrix less than 1?

Let $A$ be a primitive row-stochastic matrix. By Perron-Frobenius theorem, $A$ has an eigenvalue 1 and corresponding left eigenvector and right eigenvector $\pi$ and $\mathbb{1}$, i.e., $A\mathbb{1}=1,...