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

1
vote
1answer
129 views

Intuitive argument in case of a problem on Gambler's ruin

We have a gambler who at each step wins and loses $1$ dollar with probability $p$ and $1-p$ respectively. The game ends when he loses everything or wins $m$ dollar. Now starting with $i$ dollar the ...
1
vote
1answer
114 views

Discrete-time Markov chain properties

A Markov chain in discrete time is irreducible, has state space $\{0,1,\dots\}$ and starts at $1$. It is both a branching process and a martingale. Determine the probability of hitting $0$.
4
votes
0answers
146 views

Conditional probability and integrating out part of a random walk

Suppose that I have a random walk process defined by $\alpha_{t+1}$ ~ N$(\alpha_t, \omega^2)$. Given $\alpha_t$ and $\alpha_{t+2}$, I understand why the conditional formula for ...
0
votes
1answer
1k views

Markov Chain - Snakes and Ladders

A simple game of snakes and ladders is played on a board of nine squares. At each turn a player tosses a fair coin and advances one or two places according to whether the coin lands heads or tails. If ...
2
votes
0answers
65 views

Intuition behind criterion for an irreducible Markov chain to be transient

I have been looking over my notes for Markov chains, and I have come across the following: Theorem: An irreducible Markov chain is transient iff for some state $i$ there exists a nonzero vector $y$ ...
0
votes
0answers
33 views

Markov proof that a state is either transitive or ergotic - can it be so simple?

This is the chart associated with a Markov matrix The equivalence(communication) classes are: {1,2,3,4} - transitive {5,6,7} - transitive {8} - ergotic My teacher said that "all equivalence ...
1
vote
0answers
55 views

Meaning of $\pi$ in case of irreducible positive recurrent DTMC which is not aperiodic

In case of a irreducible positive recurrent DTMC which is not aperiodic, we know that there exist a positive unique probability mass function $\pi$ satisfying $\pi=\pi p$. The meaning of this can be : ...
0
votes
1answer
49 views

A basic doubt on the sojourn time of a CTMC

By using the memoryless property, I find the CDF of sojourn time of a CTMC as follows : $$F_X(t) = 1-e^{-F_X'(0)t}$$ I am slightly confused about the intuitive meaning of the term $F_X'(0)$. How ...
0
votes
1answer
43 views

Can an absorbing CTMC be reversible?

Can a CTMC with an absorbing state be reversible? I guess not, as the product of rates through any loop cannot be equal when the loop involves the absorbing state (Kolmogorov criterion). Is my ...
1
vote
1answer
60 views

Mean number of particle present in the system: birth-death process, $E(X_t|X_0=i)$, $b_i=\frac{b}{i+1}$, $d_i=d$

Let $\{X_t\}$ be a birth–and–death process with birth rate $$ b_i = \frac{b}{i+1}, $$ when $i$ particle are in the system, and a constant death rate $$ d_i=d. $$ Find the expected number of particle ...
0
votes
1answer
186 views

three-state Markov chain

a male and a female go to a 2-table restaurant on the same day. each day the male sits at one or the other of the 2 tables, starting at the table 1, with a Markov chain transition matrix: ...
1
vote
1answer
554 views

Finding Markov chain transition matrix using mathematical induction

Let the transition matrix of a two-state Markov chain be $$P = \begin{bmatrix}p& 1-p\\ 1-p& p\end{bmatrix}$$ Questions: a. Use mathematical induction to find $P^n$. b. When n goes to ...
1
vote
1answer
211 views

Limit theorem of Markov chains applied to higher order Markov chains

I have a second order Markov chain with 4 states {A,T,C,G} (the 4 DNA nucleotides). the transition matrix looks like this: ...
0
votes
1answer
186 views

Markov chain problem in Ross's Introduction to probability models

It is example 4.10 and the problem states that a pensioners receives 2 at the beginning of the each month. The amount of money he needs to spend is independent of the amount he has and is equal to $i$ ...
1
vote
0answers
123 views

Log Moment Generating function of a two-state Markov source

Let's say you have a two-state markovian source whose transition matrix is $P=\begin{pmatrix}1-\sigma & \sigma\\ \tau & 1-\tau\end{pmatrix}$, for the state 0 the data rate is 0 and for the ...
0
votes
1answer
78 views

Question on Markov chains of expected number of states

I am confused with an statement from my probability book that has to do with Markov chains. I hope someone could clarify that, if possible....Consider a Markov chain for which $P_{11}=1$ and ...
1
vote
1answer
253 views

Hidden Markov Model Coin Toss Problem

Given two coins and transition matrix between them given by: $\begin{bmatrix} 1-\alpha&\alpha \\ \beta&1-\beta \end{bmatrix}$ Where the first coin has probability of heads $p$ and tails ...
0
votes
1answer
34 views

Convergence of probabilistic process

Take a random vector $V$ of length $n$ where $V_i \in [m]$. Define a random process as follows. Repeatedly pick two indices $i, j \in [n]$ uniformly at random and let $V_i := V_j$ (that is change the ...
1
vote
0answers
46 views

Estimate on Galton-Watson process distribution

Let $(Zn)_{n\in \mathbb N_0}$ be a Galton-Watson process, i.e. $$ Z_{n+1} = \sum_{k=1}^{Z_n}\xi_{n,k},\qquad (\xi_{n,k})_{n\in \mathbb N_0,k \in \mathbb N} \quad \text{i.i.d } \mathbb N_0 \text{ ...
1
vote
0answers
321 views

Modified M/M/1/2 with 2 possible arrival rates and M/M/1/5 queue

I've been stuck on this question for hours, and could use some help :) "An M/M/1/2 queue has service rate $\mu$ and arrival rate of either $\lambda_1$ or $\lambda_2$. The rate can change only when ...
0
votes
2answers
912 views

Random walk with absorbing barriers

Consider a random walk with absorbing barriers at $0$ and $3$. $\mathbb P(S_{n+1}-S_n=1)=0.6$ and $\mathbb P(S_{n+1}-S_n=-1)=0.4$. What is the probability of eventual absorption at $0$, given that the ...
4
votes
2answers
143 views

Prove that a random walk on $\mathbb{Z}_+\cup \{0\}$ is transient

Prove that a random walk on $\mathbb{Z}_+ \cup \{0\}$ is transient with $p_{i,i+1}=\frac{i^2+2i+1}{2i^2+2i+1}$ and $p_{i,i-1}=\frac{i^2}{2i^2+2i+1}$. So since this Markov chain has only a single ...
0
votes
1answer
87 views

General State Space Markov Chain

I am having some difficulty understanding some early results of Markov Chain theory on a general state space. We have a function (Kernel) $K:E \times E \rightarrow \mathbb{R}$, and a distribution ...
1
vote
1answer
101 views

Time Periodic Homogeneous Markov Chain

I want to find a textbook or survey article reference with a treatment of discrete-time, inhomogeneous, yet time periodic, markov chains on finite state spaces. Elaboration: I have an inhomogeneous ...
1
vote
1answer
79 views

Identity in Markov Processes

I want to know if my reasoning here is correct, it seems simple enough but I just want clarification (I am considering the proof that if a Markov process satisfies the detailed balance condition, then ...
0
votes
1answer
45 views

recurrence for 2nd order Markov Chain

Given that $X_n$ given $X_{n-1},...,X_0$ is Poisson distributed with mean $a+bX_{n-1}+cX_{n-2}$, for $n\geq 2, a>0,b,c\geq 0$. Define $Y_n=\begin{pmatrix}X_n\\X_{n-1} \end{pmatrix}$. Prove that ...
2
votes
1answer
232 views

Question on M/M/2 queue variation

I have the following question: Two workers handle three machines(i.e. we can at most repair two machines at a time). The time until the machine breaks down is exponential distributed with expectation ...
0
votes
0answers
54 views

Question about Infinite Markov chains

Do 2 Markov chains $\left\{X_n\right\}^\inf_{n=0} $ and $\left\{Y_n\right\}^\inf_{n=0} $ with all of these properties exist so that the probability for infinite n values to maintain $X_n=Y_n$ is 0? ...
4
votes
1answer
187 views

Lower bound for multivariate recurrence

I have a recurrence that looks like $$p(i,j,k) = \frac{j}{n}p(i-1,j-1,k-1) + \frac{i-j}{n}p(i-1,j,k-1)$$ $$p(i,0,k) = 1$$ $$p(i,j,0) = 0$$ $$p(0,j,k) = 0$$ The base cases are to be considered in ...
0
votes
0answers
98 views

Markov Chains Worked Example (Stirzaker)

I have a Markov Chain with state space the non-negative integers. The rules of the M.C. are that when it is in state $i \neq 0$, it moves to one of {${0,1,2,\ldots,i+1}$} with probability $1/(i+2)$ ...
3
votes
0answers
129 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 ...
0
votes
1answer
76 views

Probability, Markov chain

A teacher leaves out a box of N stickers for children to take home as treats. Children form a queue and look at the box one by one. When a child finds $k \geqslant 1 $ stickers in the box, he or she ...
1
vote
0answers
23 views

Some questions about a “relaxed” invariant probability problem $|\mu(P-I)|\leq \epsilon$

Let's consider the set $\mathcal{M}=\{\mu:|\mu(P-I)|_1\leq \epsilon\}$ where $\mu$ is a probability vector, $P$ is the transition matrix of a discrete homogeneous Markov chain, $I$ is the identity ...
1
vote
2answers
462 views

Question about Markov chain derived from a Poisson process

Let $(N_t)$ be a Poisson process of rate $\lambda$. Define $$ X_n = N_n − n,\quad\text{for }\; n = 0, 1, 2, \ldots $$ Explain why $(X_n)$ is a Markov chain and give its transition probabilities. Using ...
1
vote
0answers
143 views

Kolmogorov backward and forward equations for a discrete-time Markov chain?

I found Kolmogorov backward equations and forward equations for diffusion processes, and for continuous time Markov chains in Wikipdia. I was wondering what Kolmogorov backward and forward equations ...
1
vote
0answers
51 views

What is the matrix norm in defining the generator of a continuous time Markov chain?

For a continuous time Markov chain with finite state space and Markov transition function $p(t)$, its generator $G$ can be defined entry-wise as $$ G_{i,j}:=\lim_{t\to 0^+} \frac{p_{i,j}(t) - ...
2
votes
1answer
366 views

Two different ways of constructing a continuous time Markov chain from discrete time one

Consider a homogeneous continuous time Markov chain (CTMC) with Markov transition function $p(t)$ and infintesimal generator $G$. Its embeded discrete time Markov chain (DTMC) has its transition ...
0
votes
2answers
31 views

A state $i$ is recurrent, if and only there exists $n \geq 1$ s.t. $p_{ii}^{(n)} =1$?

For a homogeneous discrete time Markov chain with transition matrix $p$, a state $i$ is recurrent, if and only there exists $n \geq 1$ s.t. $p_{ii}^{(n)} =1$? I have it copied from somewhere in my ...
0
votes
0answers
111 views

Markov Chain: Turn a problem into a markov chain

We have 2 machines, which are working in 0.75 precent if it wasn't out o order the day before. When a machine goes out of order, it takes 2 days to fix her up. let Xn be the num of working machines in ...
1
vote
1answer
70 views

A simple case of random walk

$\forall n \in \mathbb{N}$ we can either move from state $S_n$ to state $S_{n+1}$ with probability $p$ or to state $S_{n-1}$ with probability $q=1-p$. Also we move from state $S_0$ to state $S_{1}$ ...
2
votes
1answer
228 views

Construction of positive recurrent Markov chain

Let $\{X_i\}_{i\geq 1}$ be i.i.d. with values in $\mathbb N_0$. Define a Markov chain via the following transition matrix: $$p(0,n) = \mathbb P(X_1 = n-1) \qquad p(m,n) = \mathbb P\left(\sum_{k=1}^m ...
0
votes
1answer
149 views

Calculating probabilities in genetic sequences

I am working with certain recurring sequences in genetics and try to calculate certain probabilities: Let for instance $$\langle g_i\rangle :=\{1,1,1,6,1,1,1,6,...,1,1,1,6\}$$ and $$\langle ...
0
votes
2answers
2k views

Prove Markov Chain by definition

I came across this problem in homework: $X_n$ are i.i.d random variables with $\mathbb{P}[X_n=1]=\mathbb{P}[X_n=-1]=\frac{1}{2}$ and we we also have $S_n=X_1+...+X_n.$ Show that $S_n'=|S_n|$ is a ...
2
votes
1answer
440 views

Random walk, Cat and mouse

Here is the problem. In graph G, on different vertices there is cat and mouse. Cat and mouse do independent random walk, but time is synchronous, in one unit of time both cat and mouse do one step. ...
1
vote
2answers
202 views

How can I calculate the expected number of changes of state of a discrete-time Markov chain?

Assume we have a 2 state Markov chain with the transition matrix: $$ \left[ \begin{array} (p & 1-p\\ 1-q & q \end{array} \right] $$ and we assume that the first state is the starting state. ...
0
votes
1answer
117 views

Metropolis Hastings definition - Proving $\pi(x)$ is the invariant density of our transition matrix

I'm currently working through the proof of the Metropolis-Hastings algorithm, and using two sources: page 328, section 3 page 1704-1705 I have a good understanding of most of the proof until ...
2
votes
1answer
6k views

Steady-state and Equation System

Two questions: Given the transition matrix: $ \begin{vmatrix} \ 0.4 & 0.4 & 0.2 \\ \ 0.5 & 0.3 & 0.2 \\ \ 0.1 & 0.5 & 0.4 \end{vmatrix} $ I would like to know HOW to find ...
4
votes
3answers
261 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 ...
1
vote
2answers
298 views

Probability of visiting state $s_1$ of a Markov chain more than $N$ times in $L$ steps.

Assume we have a two-state Markov chain, with $s_1$ and $s_0$ denoting the two states. The initial state of the Markov chain is either $s_1$ or $s_0$ with probability $p_1$ or $p_0$, respectively. The ...
5
votes
4answers
5k views

Why Markov matrices always have 1 as an eigenvalue

Also called stochastic matrix. Let $A=[a_{ij}]$ - matrix over $\mathbb{R}$ $0\le a_{ij} \le 1 \forall i,j$ $\sum_{j}a_{ij}=1 \forall i$ i.e the sum along each column of $A$ is 1. I ...