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

0
votes
0answers
68 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
54 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
38 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
0answers
27 views

Inequality about the $L_2$ norm of stochastic matrices.

Let $P$ be a $n \times n$ stochastic matrix i.e. square, non-negative, rows sum to one. Let $\Phi$ be any given real matrix of size $n \times k$. We can assume $\Phi$ has independent columns and $k ...
-1
votes
0answers
32 views

Are $T_4$ and $T_5$ stopping times?

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 ...
1
vote
2answers
41 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 ...
-1
votes
0answers
19 views

Given initial state and steady state, how do I find the transition matrix?

The initial vector is $x_0 = \{.5, .5\}$ and the steady state is $x_\infty = \{1/9, 8/9\}$. How do I get the transition matrix, such that $$\lim_{p\to\infty} x_0 A^p = x_\infty $$ where $A$ is a ...
0
votes
0answers
43 views

Show that every finite closed class is positive recurrent

Let $C$ be a finite closed class. Prove or disprove that $C$ is positive recurrent. Note 1: In our lecture we proved that every finite closed class is recurrent. Note 2: (Positive) recurrence is ...
0
votes
0answers
8 views

Recurrence time of persistent state in a markov chain

Let a Markov chain contains a states and let $E_j$ be persistent. There exists a number $q < 1$ such that for $n \ge a$ the probability of the recurrence time of $E_j$ exceeding $n$ is smaller ...
0
votes
1answer
21 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
20 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
26 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
113 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
75 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$ ...
0
votes
0answers
8 views

Decomposition of a communicating class with countably infinite state space

Do you know an easy example of a Markov chain with countably infinite state space $E$, that has a communicating class $C$, that can be decomposed into a disjoint union of sets ...
1
vote
0answers
37 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
22 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{ ...
0
votes
0answers
27 views

How to build a 3-dimensional Markov chain and its transition matrix? Good examples, books, terminology?

I have three signals, of equal length, for which I want to building the transition matrix and the Markov chain. I will use the picture below to explain my questions. I am beginner with this, so please ...
2
votes
0answers
127 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 ...
0
votes
0answers
16 views

Can I reconstruct Penney's game win probabilities from dominant strategy odds?

The probabilities of each strategy (row in the table below) in Penney's game (assuming the basic version played with a penny — no relation — and strategies consisting of a pattern the outcome of three ...
0
votes
1answer
23 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
34 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
46 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
41 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
0answers
19 views

$P^n$ irreducible for all n $\implies \exists n\in\mathbb{N}: p_{ij}^{(n)}>0~\forall~i,j$

Let $P=(p_{ij})_{i,j\in E}$ denote a transition matrix belonging to a Markov chain with finite state space $E$. How can I prove the following implication? $P^n$ irreducible for all ...
0
votes
1answer
33 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
0answers
9 views

Identity how many classes in the transient prob matrix

I have searched for the existing questions in the section, but don't find any related result. So given the transient probability matrix of a certain Markov Chain, if I am required to identify how ...
0
votes
1answer
23 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
0answers
35 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
28 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
0answers
17 views

Find all communicating classes and their properties

Indicate all the communicating classes together with their partial ordering for the stochastic matrices $$ P_1=\frac{1}{4}\begin{pmatrix}2 & 2 & 0 & 0 & 0 & 0 & ...
0
votes
1answer
12 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
33 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
0answers
8 views

Calculate the mixing time of a continuous time markov chain

I have Markov Rate Matrix Q for a continuous time Markov chain, that is irreducible. I would like to calculate the mixing time of the matrix - how can I do so? Note that the methods in Markov Chains ...
0
votes
1answer
28 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 ...
0
votes
0answers
24 views

Theorem and proof about random walks

$\tau_{+d}=inf \{n: S_n =0, S_{n+1}>0, ... ,S_{n+d}>0 \}$ $\tau_{-d}=inf \{n: S_n =0, S_{n+1}<0, ... ,S_{n+d}<0 \}$ $q_n=P\{S_1>0,...,S_n>0\}=P\{S_1<0,...,S_n<0\}, n\in N$ I ...
1
vote
1answer
96 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 ...
0
votes
0answers
15 views

Joint probability of Markov evens

If we have a Markov chain with $X \rightarrow Y \rightarrow Z$, then by definition the joint probability is $$p(x,y,z) = p(x)p(y|x)p(z|y)$$ My question is: How does this imply that events $X$, $Y$, ...
1
vote
1answer
131 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
25 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 ...
1
vote
0answers
16 views

Testing Time Homogeneity of a Markov Chain

The following shows a statistical test used to check the time homogeneity of a MC but I just cannot seem to understand how exactly it is done. Can someone help me out to understand this method in a ...
0
votes
0answers
26 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
46 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
16 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 ...
0
votes
0answers
11 views

Eigen Value -1 of a stochastic matrix

I have to prove that if there is an eigen value of -1, of a stochastic irreducible transition matrix $P$, then the corresponding markov chain has a period which is a multiple of 2. I am approaching ...
3
votes
1answer
36 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 ...
1
vote
2answers
55 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 ...
9
votes
2answers
795 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
88 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
41 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 ...