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.

learn more… | top users | synonyms

4
votes
1answer
122 views

Behavior of explosive random process

Inspired somewhat by this problem, I've been investigating the behavior under iteration of the following discrete random process: Given $n\in\mathbb{N}$, choose an integer from $\{0,1,\ldots,n\}$ ...
3
votes
3answers
635 views

Probability of absorption in a discrete Markov chain

Let $\{X_{n}\}$ be a Markov Chain on the state space $S=\{1,...,100\}$ with $X_{0}=30$, and transition probabilities given by $p_{1,1}=p_{100,100}=1$, $p_{99,100}=p_{99,98}=1/2$ and for $2\leq ...
3
votes
1answer
262 views

Expected number of runs

Let $S[16]$ be a binary array i.e, elements of $S$ are 0/1 with elements $S[i]$ are taken uniformly and independently form $\{0,1\}$. Let $k$ be a random element taken uniformly from $\{0,1\}$. I have ...
3
votes
1answer
1k views

Markov process vs. markov chain vs. random process vs. stochastic process vs. collection of random variables

I'm trying to understand each of the above terms, and I'm having a lot of trouble deciphering the difference between them (note, my mathematics training isn't very strong - so please go easy on the ...
3
votes
2answers
396 views

Irreducible and aperiodic Markov chain : $P^t(x,y)>0$

Consider a Markov chain $X$ with transition probability $P$ and finite state space $\Omega$. Which of the following statement is true? If $X$ is irreducible then $\exists t>0 \ni P^t(x,y)>0, ...
3
votes
2answers
160 views

Markov Chains and Linear Transformations

I just have a quick question about Markov Chain and linear algebra. Background. Let $\{M_n: n= 0, 1, 2, \dots \}$ be a Markov Chain. We can represent the transition probabilities $_{n}Q^{(i,j)}$ in a ...
3
votes
2answers
938 views

Null-recurrence of a random walk

In a random walk on $\mathbb{Z}$ starting at $0$, with probability 1/3 we go +2, with probability 2/3 we go -1. Please prove that all states in this Markov Chain are null-recurrent. Thoughts: it is ...
3
votes
2answers
254 views

How can a Markov chain be written as a measure-preserving dynamic system

From http://masi.cscs.lsa.umich.edu/~crshalizi/notabene/ergodic-theory.html irreducible Markov chains with finite state spaces are ergodic processes, since they have a unique invariant ...
3
votes
2answers
377 views

Simple proof that stationary birth-death chains are reversible

A Markov chain with state space $\mathbb{Z}$ is a birth-death chain if the transition probabilities satisfy $p(x,y) = 0$ for $|x-y| > 1$. That is, the only possible transitions are to move one ...
3
votes
4answers
73 views

Determining vector equations

Let $A\in \Bbb R^{n\times n}$ be a matrix such that $\mathrm{rank}(A) = n-1$ and consider the equation $$ Ax = 0. $$ Clearly, its solutions span a $1$-dimensional space, thus an additional ...
3
votes
1answer
977 views

Calculating stationary distribution of markov chain

I am asked to compute the stationary distribution of the markov chain with state space $E=\{0\dots,n\}$ and transition matrix below: \begin{bmatrix} 0 & 1 \\ \frac{1}{n} ...
3
votes
1answer
377 views

A.s. finite hitting time with an infinite mean

Let $X$ be a discrete-time Markov process on some measurable space $(\mathscr X,\mathscr B)$. Let $B\in\mathscr B$ and $$ \tau_B:=\inf\{n\geq 0:X_n\in B\} $$ is the first hitting time of $B$. ...
3
votes
2answers
326 views

How can I compare two Markov processes?

There is a discrete-time irreductible Markov process with $r$ possible states. $k$ observations were performed. At each observation a state of process was determined. $T_0 = \lbrace 0,1,\dots ...
3
votes
2answers
380 views

Markov chain with uncountable state space

I'm self-studying probability theory and struggling with understanding Markov chains on uncountable state spaces, notably I would like to solve the following exercise from this book. ...
3
votes
1answer
32 views

Coupling between two CTMCs

Suppose I have two random processes $X(t)$ and $Y(t)$ starting at time $t=0$ and $X(0)=Y(0)=0$. The processes obey the following transition rates: $$ X(t):\begin{cases} 0\to 1,\text{at rate } A\\ ...
3
votes
1answer
91 views

Markov Chain Initial Distribution

Suppose $\{X_0,X_1,X_2,\dots\}$ is a discrete-time Markov chain taking values in a finite set $\{1,\dots,N\}$ with initial distribution $p_i(0) = P(X_0 = i)$ for $i\in\{1,\dots,N\}$ and transition ...
3
votes
2answers
71 views

What's the probability that A wins finally

Suppose A has \$2 and B has \$3. They play a game, each game gives the winner \$1 from other. A has a probability $\frac{3}{5}$ to win each game. They play this game until one of them is bankrupt. ...
3
votes
1answer
110 views

How to find the limit of a markov chain

Given a markov chain where the next state is related to the previous state by the following matrix: $$\begin{array}{c|ccc} & A & B & C\\ \hline A & p_1 & q_1 & r_1\\ B & ...
3
votes
1answer
191 views

Conditional probability of a general Markov process given by its running process

I have a question as follow: "Let $X$ be a general Markov process, $M$ is a running maximum process of $X$ and $T$ be an exponential distribution, independent of $X$. I learned that there is the ...
3
votes
1answer
56 views

When are stable continuous time Markov chains Feller? Always?

This is a question is similar to this 2 year-old one that never got answered (truthfully it's pretty much the same question except that I'm adding a bit more detail and the assumption that the $Q$ ...
3
votes
1answer
51 views

Question about Markov chain

We know that if $\{X_n\}$ is a Markov chain, then $X_{n+1}$ is independent with the past states $X_0,\ldots,X_{n-1}$ given current state $X_n$, that is ...
3
votes
1answer
59 views

Random walk where increment depend on current position

Consider the following stochastic process, $$b(i+1) = b(i) + \xi_i (b_i),$$ where $\xi_i(b_i) \in \{-1, k \}$ are the independent increments having the following distribution: $$\begin{align} P (\xi ...
3
votes
1answer
134 views

recurrence criterion for random-walk like (simple) inhomogeneous Markov chain

This question is to some degree a follow-up of this question. Suppose we have a random-walk like Markov chain, i.e. state space is the set of all integers from $-\infty$ to $\infty$, the transition ...
3
votes
2answers
133 views

Given that $(X_n)_{n\geq 0}$ is a Markov Chain, prove that $(X_{kn})_{n\geq 0}$ is a Markov Chain

Given that $(X_n)_{n\geq 0}$ is a Markov Chain, prove that $(X_{kn})_{n\geq 0}$ is a Markov Chain. I don't know what this exercise has been so difficult for me, I've been playing around with the ...
3
votes
1answer
75 views

Sojourn time of a CTMC

Soujourn time of a CTMC at time $t$ is defined as : $$T(t)= \inf\{ s > 0 : X(t+s) \neq X(t)\}$$ My question is why "inf", not min ? Here $T(t)$ belongs to the set $\{ s > 0 : X(t+s) \neq ...
3
votes
1answer
109 views

Probability with Markov chains

I need some hint about Markov chains. So here is my homework. Let $\{ X_t : t = 0,1, 2, 3, \ldots, n\}? $ be a Markov chain. What is $P(X_0 =i\mid X_n=j)$? So I need to calculate if it's $j$ ...
3
votes
1answer
101 views

Limit of a probability regarding a random walk

Consider a random walk on the integers starting at 0, where in each step you move either 1 or 2 meters (back or forth alike). As soon as you reach either the $N$ or $N+1$ meter mark, you stop. What is ...
3
votes
2answers
192 views

a theorem on transient and recurrent state in a DTMC

Is the following statement true: In a finite Markov chain, if $i$ is a transient state then there is at least one recurrent state $j$ such that $j$ is reachable from $i$.
3
votes
2answers
176 views

Martingale associated to Markov chain

$X$ is a (continuous time) Markov chain with generator matrix $\Lambda$ and finite state space $G$. I know that for $g\colon G \to R$ $$ M_t = g(X_t) - g(X_0) - \int_0^t (\Lambda g)(X_s)\, ds $$ is a ...
3
votes
1answer
1k views

Finding the stationary distribution of a markov chain

I am asked to compute the stationary distribution of the markov chain with state space $E=\mathbb{N}_0$, $q_n >0$ for all $n \in \mathbb{N}_0$ and transition matrix below: \begin{bmatrix} q_0 ...
3
votes
2answers
361 views

Expectation of a stopping time uniquely determined by a function

Let $(X_t)_{t\ge0}$ be a Markov chain on a finite state space $\Omega$, with transition probability $P$. Let $T$ be a stopping time such that $T=\min \{t\ge 0;X_t \in A \subset \Omega \}$.  If ...
3
votes
1answer
58 views

Sum of two Markov processes another Markov process?

Let $dX_{t} = m_1(l_1-X_{t})dt+\sigma_1 dW_{t}$ and $dY_{t} = m_2(l_2-Y_{t})dt+\sigma_2(\rho dW_{t}+\sqrt{1-\rho^2}dW_{t}^{1})$ where the $m_i$'s, $l_i$'s and $\sigma_i$'s are constants, $\rho \in ...
3
votes
1answer
17 views

The expectation of total number of different states in N time points

[Conditions] (1) An object has K possible states. (2) This object can have only one state at a single time point. (3) The probability of each state at any single time point is 1/K, and each time ...
3
votes
1answer
152 views

A basic question on irreducible periodic markov chain

For an irreducible periodic (period $2$) Markov Chain I know that both of the following two quantities are same and equal to $\pi(i)$: $$ \lim_{n\to \infty} \frac{1}{2}(p_n(j,i) + p_{n+1}(j,i))$$ $$ ...
3
votes
1answer
326 views

Proof about Steady-State distribution of a Markov chain

Consider $A$ as a matrix, that when normalized represents an finite-state time-homogeneous Markov chain $M$ with entries $0\leq p_{i,j}\leq 1$, where each row sums up to $1$. We can also assume that ...
3
votes
1answer
146 views

what's the generalized approach to this infinite state markov chain problem

Say, a bag has 10 balls, in which 9 are red, 1 is black. Each red ball is worth 1 point, each black is worth 4 points. I have 8 picks from the bag to start with (the bag refills itself after each ...
3
votes
1answer
311 views

Countable state Markov chain: detailed balance consequences

Let $S$ be a countable set and $\pi$ a probability distribution on $S$. A discrete-time Markov chain $(X_n)$ with state space $S$ is said to be in detailed balance with respect to $\pi$ (or simply in ...
3
votes
1answer
680 views

Probability distribution of markov chain

I have a Markov chain with state space $E = \{1,2,3,4,5\}$ and transition matrix below: $$ \begin{bmatrix} 1/2 & 0 & 1/2 & 0 & 0 \\ 1/3 & 2/3 & 0 ...
3
votes
1answer
548 views

Strong Markov property - Durrett

I recently had great success with my first question here so I will boldly go on to a second. Here goes: I'm studying Markov Chains in Rick Durrett - Probability: Theory and example and I'm stuck with ...
3
votes
1answer
1k views

coin flips and markov chain

Consider the case of an infinite (or finite $n$) string of coin tosses, and let $q$ and $1-q$ be the probabilities that the coin comes up tails and heads, respectively. (For simplicity, we can take ...
3
votes
1answer
90 views

What happens to a regular Markov matrix that has more than one steady state/stationary distribution?

It is known that for a regular Markov matrix $M,$ $M^{n}$ has the steady-state vector as all of its columns as $n \to \infty.$ I learned this in class, but what if there is more than one steady-state ...
3
votes
1answer
222 views

Identifying states in Markov chains

I just started learning about Markov processes and got the following homework question. Classify all the states as recurrent or transient for the Markov chain below $$\begin{matrix} ...
3
votes
0answers
28 views

Invariant measure of Euler-Maruyama Discretisation of an Ito diffusion

Let $(X_t)_{t \geq 0}$ be a diffusion process with dynamics governed by the stochastic differential equation \begin{equation} dX_t = b(X_t)dt + \sigma(X_t)dW_t, ~~ X_0 = x_0, \end{equation} where ...
3
votes
0answers
37 views

Markov chains and natural filtration

I have the following problem Consider a homogeneous Markov chain $(X_n)$ with countable state set $E$. Suppose that $A$ is a proper subset of $E$ and consider the stopping times $\tau^0=0 $ and ...
3
votes
0answers
33 views

Standard deviation of a quantum walk?

The standard deviation of a classical random walk with $n$ steps is $\sqrt n$ - Standard deviation of a random walk. I have read in many places that the standard deviation of a quantum walk $n$ with a ...
3
votes
0answers
65 views

Markov Chain Alternate Expectation

Consider a Markov chain defined by transition matrix $P$ such that for each transition from state $i\rightarrow j$ the probability is $p_{ij}$. Now say there is an associated value for each transition ...
3
votes
0answers
50 views

A Continuous-Time Markov Process Taking All Possible Values

Let $\mathbb{N}$ be the set of positive integers. For each $n \in \mathbb{N}$, let $X^{(n)}=\{ X^{(n)}(t): t \geq 0 \}$ be a Markov chain with state-space the two point set $\{0,1\}$ and $Q$-matrix ...
3
votes
0answers
84 views

SLLN of Markov chains .

Let $X_1$, $X_2$,... be a finite state, irreducible and aperiodic Markov chain with initial state $X_0=i$. It is known that \begin{equation} \mathrm{P}\Big\{\lim_{n\rightarrow\infty} ...
3
votes
1answer
63 views

expected hitting time with two absorbing states

Consider a Markov chain in a finite space and with two absorbing states, each of which is accessible from the other, transient states. Is the expected number of transitions to reach any single ...
3
votes
0answers
86 views

Prove the 2 definitions of the periodicity of Markov Chain are equivalent.

In many textbooks, there are basically 2 ways of defining the periodicity of Markov Chain. One is by partitioning the graph in to subgraph such that transition in one group of state leads to the other ...