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

2
votes
0answers
29 views

The independence of random variables

Here is my question: Consider a homogeneous ergodic Markov chain on a finite state space $X=\{1,\ldots,r\} $. Define the random variables $\tau_n \,,n\ge1$ as the consecutive times when the Markov ...
0
votes
0answers
472 views

Random walk on infinite binary tree (recurrence, transience)

Consider a random walk on the infinite binary tree with root $x$ which has the following transition probabilities. $$ p_{x,0}=p_{x,1}=\frac{1}{2},~~~p_{y,y0}=p,~~~p_{y,y1}=q,~~\text{and ...
1
vote
2answers
98 views

On the definition of Markov chains

A Markov chain with discrete time dependence and stationary transition probabilities is defined as follows. Let $S$ be a countable set, $p_{ij}$ be a nonnegative number for each $i,j\in S$ and assume ...
1
vote
1answer
52 views

convergence of nullrecurrent markov chain

Hi guys! At the moment I'm working on this proof. It's in a german book so hopefully you understand everything. I understand everything in the picture without the use of the markov property at ...
1
vote
2answers
70 views

Is this a stopping time or not?

Let $(\xi_n)_{n\in\mathbb{N}_0}$ be a sequence of independent identically distributed random variables that take values in $\left\{-1,1\right\}$ with equal probabilities. Define ...
0
votes
1answer
39 views

Is it possible to compute these probabilities concerning a 6-digit password using theory of Markov chains? [duplicate]

Consider the situation of decoding a 6-digit password that consists of the symbols A to Z and 0 to 9, where all possible combinations are tried randomly and uniformly. Consider the ...
1
vote
1answer
182 views

How to transform a process into a Markov Chain?

This problem is in the book Introduction to Probability. The question goes this way. Consider the process {$ X_n, n = 0,1,...$ } with values 0,1 or 2. If P{$X_{n+1} = j | X_n = i, X_{n-1} = ...
0
votes
1answer
85 views

Computer failure with Markov chains and n-step transition matrix

Hi I am struggling with a Markov Chain question: A computer network has two servers, only one of which is in operation at any given time. A server may break down on any given day with probability p. ...
4
votes
0answers
227 views

6-digit password - a special decoding method

Consider the situation of decoding a 6-digit password that consists of the symbols A to Z and 0 to 9, where all possible combinations are tried randomly and uniformly. Consider the ...
2
votes
1answer
111 views

Counterexample for $\| (\Phi^\top \Xi \Phi)^\dagger \Phi^\top \Xi P \Phi \|_2 \leq 1$

All matrices are real. Let $P$ be any stochastic matrix (i.e. square, non-negative, rows summing to one). Let $\Xi$ be a diagonal matrix containing on its diagonal any left eigenvector of $P$ ...
1
vote
0answers
39 views

Find condition on $X$ so that $P(\exists n\in\mathbb{N}: N_n=0)=1$

Let $X, X_{n,k}$ for $k,n\in\mathbb{N}$ denote independent random variables with values in $\mathbb{N}_0$. $X$ is identically distributed as all $X_{n,k}$. Define $N_0:=1$ and for ...
0
votes
0answers
92 views

Transition probabilities do not sum to $1$

I have a set of weekly probabilities, and in order to convert to monthly probabilities, I have firstly convert the weekly probabilities into rates, $$r = -\frac{\ln (1-p)}{ t} ,\quad t=1\text{ ...
4
votes
1answer
331 views

Derivative of conditional expectation

Let $\left( {{X_t}:t \in \left[ 0 \right.\left. {, + \infty } \right\rangle } \right)$ be a continuous time Markov chain on a probability space $\left( {\Omega ,\mathcal{F},\mathbb{P}} \right)$ with a ...
1
vote
1answer
570 views

Non-stationary Markov Chain Explanation

I am interested in creating a model in R, where I can implement a non-stationary Markov process. I would like to create a matrix of probabilities of going from one state to the next during a one year ...
0
votes
1answer
36 views

Finding a condition for which it is $P(\exists n\in\mathbb{N}: N_n=0)=0$

Let $X, X_{n,k}$ for $k,n\in\mathbb{N}$ denote independent random variables with values in $\mathbb{N}_0$. Define $N_0:=1$ and for $n\in\mathbb{N}$ set $$ N_n:=\begin{cases}0, & \text{ ...
2
votes
1answer
49 views

Find conditions on the distribution on $X$, but what is meant by $X$?

Let $X, X_{n,k}$ for $k,n\in\mathbb{N}$ denote independent random variables with values in $\mathbb{N}_0$. Define $N_0:=1$ and for $n\in\mathbb{N}$ set $$ N_n:=\begin{cases}0, & \text{ ...
1
vote
0answers
59 views

Check if $(N_n)$ is a Markov chain

Let $X, X_{n,k}$ for $k,n\in\mathbb{N}$ denote independent random variables with values in $\mathbb{N}_0$. Define $N_0:=1$ and for $n\in\mathbb{N}$ set $$ N_n:=\begin{cases}0, & \text{ ...
0
votes
2answers
56 views

Why is P irreducible and aperiodic?

Let $P=(p_{ij})_{i,j\in E}$ denote the transition matrix of a Markov chain with finite state space $E$. Why does the following implication hold: $$ \exists n\in\mathbb{N}: ...
0
votes
2answers
51 views

Does from $P^n$ irreducible for all $n\in\mathbb{N}$ follow that $P$ is aperiodic?

let $P$ be a transition matrix of a Markov chain with state space E, that is finite. Does from $P^n$ irreducible for all $n\in\mathbb{N}$ follow that $P$ is irreducible and aperiodic? ...
1
vote
1answer
63 views

What does it mean if $P^n$ is irreducible for every $n\in\mathbb{N}$?

If $P$ is the transition matrix belonging to a markov chain, then what does it mean that $P^n$ is irreducible for every $n\in\mathbb{N}$? For $n=1$ it means that all states communicate with each ...
1
vote
0answers
136 views

Kolmogorov backward equations for Birth-Death

I'm trying to solve the Kolmogorov backward equations for a Birth-Death Markov chain with three states. I have 2 equations: $$P_{00}'(t) = \lambda_0 (P_{10}(t)-P_{00}(t))$$ $$P_{10}'(t) = ...
0
votes
1answer
18 views

Transformation to achieve unit transition rate in a continuous time Markov chain

I have a continuous time Markov chain (CTMC) defined by a transition matrix $P$ and where all transition times go as a exponential random variables with transition rate $\gamma$. I would like to ...
1
vote
0answers
143 views

Chapman-Kolmogorov equations of time inhomogenous Markov chains

Let us assume that we are given a time inhomogenous Markov chain in continuous time (ICTMC) $(X(t))_{t \geq0}$ with a finite state space $\{1,\ldots,n\}$. Set $P(t)_{i,j} := \mathbb{P}(X(t) = j \mid ...
0
votes
1answer
38 views

Show: $i$ is aperiodic $\implies~\exists n_0: p_{ii}^{(n)}>0~\forall~n\geqslant n_0$

Let $(X_n)$ be a Markov chain with state space E. Show: If a state $i$ is aperiodic then there exists a $n_0\in\mathbb{N}$ so that $p_{ii}^{(n)}>0~\forall~n\geqslant n_0$. I know ...
1
vote
1answer
148 views

Equivalent statements about transition matrix of a Markov chain

Let $P=(p_{ij})_{i,j\in E}$ be a transition matrix and $E$ of finite cardinality. Show that the following three conditions are equivalent: (i) $p$ is irreducible and aperiodic. (ii) $P^n$ is ...
1
vote
1answer
161 views

Periodicity of a communicating class

Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with discrete state space $E$ and transition matrix $P$. Let $C\subseteq E$ be a communicating class. Prove or disprove the following ...
0
votes
1answer
44 views

Is this statement about periodic communicating classes an equivalence statement?

In our reading about Markov chains we had the following theorem (including proof): Let $(X_n)_{n\in\mathbb{N}_0}$ denote a Markov chain with state space $E$. A periodic communicating class ...
0
votes
0answers
130 views

Finding the number of non empty urns after 9 steps

I'm trying to understand this example given in the book and am having trouble. The example states. Suppose that balls are successively distributed among 8 urns, with each ball being equally likely to ...
2
votes
2answers
68 views

Verifying the Markov property

We throw a dice infinitely often. Define $U_n$ to be the maximal number shown up to time $n$. How can I verify that $$ ...
0
votes
1answer
23 views

Determining the Likelihoods of Different Game States

Suppose a game is played in which Player 1 must gain two points to win and Player 2 must gain five points to win. Both players start with zero points. In any round, Player 1 has a $1/3$ chance of ...
3
votes
1answer
48 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
3answers
343 views

Characterize stochastic matrices such that max singular value is less or equal one.

By a stochastic matrix, I mean any non-negative square real matrix with rows summing to one. It is well-known that singular values of stochastic matrices can be more than one. Is there a ...
10
votes
2answers
1k views

Expected number of turns for a rook to move to top right-most corner?

Suppose a rook starts on the lower left-most square of a standard $8 \times 8$ chess board. The board contains no other pieces. The rook randomly makes a legal chess move with every turn (directly ...
0
votes
1answer
420 views

A Markov Chain problem concerning a flea moving around a triangle

A Flea moves around the vertices of a triangle in the following manner: Whenever it is at vertex i it moves to its clockwise neighbor vertex with probability $p_i$ and to the counterclockwise neighbor ...
2
votes
1answer
200 views

Layman perspective of mean time spent in transient state of a Markov chain.

Let $X=\{X_n\}$ be a finite state Markov Chain with the state space $\{0,1,2,\ldots,N\}$ such that $0$ is the single absorbing state and all the rest states are transient. The following is the ...
1
vote
4answers
126 views

Find the expected number of steps needed until every point has been visited at least once.

The complete graph on {1,...,N} is the simple graph with these vertices such that any pair of distinct points is adjacent. Let $X_{n}$ denote the simple random walk on this graph and let T be the ...
0
votes
2answers
76 views

Hitting time $h_i(k)\geqslant h_i(j)\cdot h_j(k)$

Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with state space $E$. The hitting time of a set $A\subseteq E$ is a RV $$ ...
1
vote
2answers
198 views

Back to square 1…

A friend of mine was telling me about one of the problems, which he described thus: As you can see, the answer to the toy problem presented here is reportedly 13. However, I don't understand how ...
1
vote
0answers
44 views

Closed communicating class and stochastic matrix

Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with state space $E$ and transition matrix $(p_{ij})_{i,j\in E}$. Let $C\subseteq E$ be a closed communicating class. Show that $$ ...
0
votes
1answer
15 views

Why does $(p_{04}^{(n)})_{n\in\mathbb{N}}$ not converge?

Consider a Markov chain with the states 0,1,2,3,4,5,6 and transition matrix $$ P=\begin{pmatrix}\frac{1}{5} & \frac{3}{5}& 0 & 0 & \frac{1}{5} & 0 & 0\\0 & 0 &1 & 0 ...
1
vote
0answers
39 views

Comparing frequencies in stationary distribution

Do there exist theorems for comparing frequencies in the stationary distribution of a (say) aperiodic, positive recurrent Markov chain? i.e. given the transition probability matrix $\mathbf{P}$ with ...
0
votes
1answer
37 views

Transition matrix to graph

Is there a program which can given a transition matrix $P$ draw a graph from a it? The transition matrix is also known as stochastic matrix and probability matrix see ...
1
vote
1answer
42 views

Show that $\mathbb{P}((X_{n+1},…,X_N)\in F|X_n\in A, (X_{n-1},…,X_0)\in G)=\mathbb{P}((X_{n+1,}…,X_N)\in F|X_n\in A)$

In our reading we had the following Theorem concerning Markov chains: Take $0<n<N$ and $(X_n)_{n\in\mathbb{N}}$ a Markov chain. Then for all $a_n\in E$ (where $E$ is the state space) ...
1
vote
1answer
134 views

Which of the following processes are Markov chains?

A dice is thrown an infinite number of times. Which of the following procsses are Markov chains or not? Justify your answer. For those processes that are Markov chains give the transition ...
1
vote
2answers
228 views

What is the expected number of flips that are needed?

Suppose we flip a fair coin repeatedly until we have flipped four consecutive heads. What is the expected number of flips that are needed? The hint is given is as follows: Consider a Markov chain ...
0
votes
1answer
18 views

How to properly determine observations related to a Hidden Markov Model alike problem?

I got a an exercise problem which should be seen as a HMM scenario and argument some statements. However I'm quite confused about how to properly solve and argument my solutions. Problem tells: ...
1
vote
1answer
135 views

Calculating the hitting probability using the strong markov property

** This problem is from Markov Chains by Norris, exercise 1.5.4.** A random sequence of non-negative integers $(F)n)_{n\ge0}$ is obtained by setting $F_0=0$ and $F_1=1$ and, once $F_0,\ldots,F_n$ are ...
0
votes
1answer
22 views

Irreducibility of markov chains

Let $A=(a(x,y))_{x,y\in X}$ be a finite irreduzibel nonnegative matrix. Let $b,c >0$, and $\alpha=a^{(b+c)}(x,x)>0$. So $a^{(n(b+c))}(x,x)\ge \alpha^n$. And therefore $\lim ...
1
vote
0answers
29 views

Is there a single matrix norm such that for all stochastic $P$, $\| P \| = 1$?

By a stochastic matrix I mean a square real non-negative matrix with rows summing to one. Denote the set of all such matrices $\mathcal{S}$. By matrix norm I mean a norm in the vector space of ...
0
votes
1answer
70 views

How do we compute the mean time spent in transient states of a Markov Chain?

Let $X=\{X_n\}$ be a finite state Markov Chain with the state space $S = \{0,1,2,...,N\}$ such that all the states are transient. The following is the transition matrix. $$ P = \left[\begin{matrix} ...