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

3
votes
4answers
74 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
2answers
450 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
1answer
45 views

Question about random walk markov chain

For a random walk, let $a$ denote the probability that the markov chain will ever return to state $0$ given that it is currently in state $1$. Because the markov chain will always increase by $1$ with ...
3
votes
1answer
57 views

Recurrence/Transience of random walk with +2/-1 steps

Consider the Markov chain with state space $S=(0,1,2,...)$ and transition probabilities: $p(x,x+2)=p$ , $p(x,x-1)=1-p$, $\forall$ $x>0$. $p(0,2)=p$ , $p(0,0)=1-p$. For which values of $p$ is this ...
3
votes
1answer
130 views

For finite Markov Chain, time average distribution is always a stationary distribution?

Given some finite state space $\Omega\equiv\{\omega_1,\ldots,\omega_n\}$ be given, and let any Markov chain $\{X_t\}$ with $n\times n$ transition matrix $A$ on $\Omega$ be given. I would like to know ...
3
votes
1answer
278 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
75 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
116 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
210 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
2answers
67 views

Limiting probability that the sum of the values of a die is a multiple of 13

A fair die is thrown repeatedly. Let $X_n$ denote the sum of the $n$ first throws. I have to find $\lim_{n\rightarrow \infty}P(X_n \text{ is multiple of 13})$. Now follows what I tried, which I don't ...
3
votes
1answer
78 views

Applying MCMC Metropolis algorithm

I'm interested in all possible paths (on the grid $\mathbb{N}^2 $) that goes from $ (0,0) $ to $ (n, n) $. At each step there are two possibilities: go right or go up. The path is a sequence $ ...
3
votes
1answer
46 views

Is it true that $\|\text{diag($\pi$)} P\|_2 \leq 1$ for $P$ stochastic and $\pi P = \pi$.

$\| \cdot \|_2 $ is the matrix norm induced by $L_2$. $P$ is any given real square $n \times n$ non-negative matrix with rows summing to one, i.e. $P1 = 1$, where $1$ is the vector of ones. There is ...
3
votes
1answer
407 views

Elementary proof of geometric / negative binomial distribution in birth-death processes

The birth-death process concerns a population of $n_0$ individuals, each of which reproduce and die at a constant rate as time $t$ increases from $t=0$. Each individual splits into two individuals ...
3
votes
1answer
105 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
129 views

Markov chain problem with finite states

Consider any Markov chain on a state space with exactly $r$ states. We want to find the largest $N>0$ such that there exists states $i,j$ for every $n < N$ we have $p_{ij}^{(N)} > 0$ and ...
3
votes
1answer
85 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
604 views

Markov chains: is “aperiodic + irreducible” equivalent to “regular”?

I have two books on stochastic processes. In one book, it says that the limiting matrix is possible to find if the matrix is regular, that is, if for some $n$ $P^n$ has only positive values. The ...
3
votes
1answer
174 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
1answer
127 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
136 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
109 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
243 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
266 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
2k 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
734 views

Proof of Markov property for Ehrenfest urn

[the question got downvoted on MO with the recommendation to ask here] In many books Ehrenfest Urn is used as an example of a homogeneous Markov chain, where entries in transition probabilities ...
3
votes
2answers
384 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
26 views

Generating Constrained Random Distributions

I am trying to help another StackExchange user. We are attempting to fill a 6x6 matrix with 12 A's, 12 B's, and 12 C's subject to the constraint that each row contains 2 A, 2B and 2 C and each column ...
3
votes
1answer
64 views

Joint density function Poisson Process

We did an example in class that I'm not sure how we came up with the answer. The problem is: If I let X(t) be a Poisson process of rate $\lambda$. I'm supposed to validate the identity ...
3
votes
1answer
57 views

Stochastic matrices with orthogonal eigenvectors

I stumbled across an odd fact while thinking about Markov chains, and I have an odd proof for it. Claim: Let $P$ be the transition matrix of a finite irreducible aperiodic Markov chain, and assume ...
3
votes
1answer
55 views

Exercise from Norris' book on Markov chains

Let $(X_n)$ be a Markov chain on $\mathbb{N}$ with transition probabilities satisfying: $$p_{0,1}=1,\quad p_{i,i-1}+p_{i,i+1}=1,\quad p_{i,i+1}=\left(\frac{i+1}{i}\right)^{\alpha}p_{i,i-1}$$ The ...
3
votes
1answer
78 views

Gambler's ruin: Distribution of the maximum fortune along the game conditioned to lose

I having troubles with this problem: Let $(X_n)$ a gambler's ruin Markov chain on $\{0,\dots,N\}$ i.e. a Markov chain with state set $E=\{0,\dots,N\}$ and probability transitions $$p(k,k+1)= ...
3
votes
1answer
78 views

Mean exit time / first passage time for a general symmetric Markov chain

Suppose I have a Markov chain as depicted in the following figure: where $N$ is even. State 0 and $N$ are the two sinks of the chain. The transition probabilities have the following property: ...
3
votes
1answer
108 views

What does a customer see when it begins to be served in $M/M/1$ queue?

In queueing theory, the PASTA (Poisson Arrivals See Time Averages) principle [wiki] justifies $a_n = P_n$ where $$a_n = \text{proportion of customers that find } n \text{ customers in the system when ...
3
votes
1answer
166 views

A linear growth model with immigration

Ill give some background first before asking questions.(the text below is straight out of the book) Each individual in the population is assumed give birth at an exponential rate of $\lambda$ in ...
3
votes
1answer
539 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
26 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
283 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
632 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
157 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
567 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
996 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
96 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
292 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
1answer
79 views

Frog on infinitely many lily pads (Markov chain)

A frog on pad $i$ hops to one of the pads $(1,2,...,i,i+1)$ with equal probability. I know that if the frog starts on pad $k$ the expected number of times the frog jumps, before returning for the ...
3
votes
2answers
42 views

Markov chains diagram - what are the numbers above arrows?

Most if not all articles describe the numbers above arrows as probabilities of a transition in that direction, such as this one, or this one. But here, for example, something really weird is ...
3
votes
0answers
28 views

Martingale converges to the boundary

I asked an almost same question before and it is solved by considering adjacent $Z_n$ can not be far away and obtain a contradiction. However, if the setting is altered a bit, I wonder whether it is ...
3
votes
1answer
20 views

non-stationary Markov chain n-step

When I search for the long term behaviour of a stationary markov chain I just multiply the transition matrix with itself for the number of steps: P(n) = P(0)^n. But how do you go about doing it ...
3
votes
0answers
25 views

$ X_n = 2 Y_n + Y_{n+1} $ (non)Markov Chain

Let $Y_1,Y_2,\dots$ be iid random variables with $P(Y_n=0)=1-p,\; P(Y_n=1)=p$ where $p\in(0,1)$. Define $$ X_n = 2 Y_n + Y_{n+1} $$ The question is, whether $\{X_n\}$ is a Markov chain or not. ...
3
votes
1answer
71 views

Markov Property Confusion

I feel like I'm being very dense/employing some sort of circular reasoning, but I'm having trouble understanding the Markov Property. According to Durrett (ISBN-10:1461436141), $X_n$ is a Markov chain ...
3
votes
0answers
36 views

Periodicity of Markov chains under cartesian product

Suppose that you have a finite state Markov chain, with $n$ states and characterized by $p_{i,j}$ the probability of reaching state $j$ from state $i$. Consider the new Markov chain with $n^2$ states ...