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
votes
0answers
15 views

Calculate the discrete density of the variables of a Markov chain

$X$ and $Y$ are independent random variables of Bernoulli with parameter $\frac{2}{3}$. $Z=X+Y$ $\{X_n\}_{n \in \mathbb{N}}$ with values in {0,1,2} having $Z$ such as initial law and the transition ...
0
votes
2answers
37 views

Markov chains steady-state distribution

Ok so we are given a Markov chain $X_n$, $P=P(ij)$ as the transition matrix and the $(\pi_1,\pi_2,\pi_3,...,\pi_n)$ as steady-state distribution of the chain. We are asked to prove that for every $i$: ...
0
votes
2answers
39 views

Defining the states when we roll one single die repeatedly

We roll a single die and the game stops as soon as the sum of two successive rolls is either 5 or 7. We want to find the probability that the game stops at a sum of 5. It seems like Markov ...
0
votes
0answers
6 views

Recurrent Markov chain with $p_{i,i+2} = p$ , $p_{i,i} = r$ , $p_{i,i−1} = 1−p−r$

Let $Xn$ a Markov chain on $\mathbb{Z}$ with the following transition matrix: $p_{i,i+2} = p$ , $p_{i,i} = r$ , $p_{i,i−1} = 1−p−r$ Find p and q such that the cain is recurrent. I'm tring to ...
0
votes
0answers
9 views

How to calculate mean of busy-cylce

Let $\{X(t)\}$ be birth-death process on a finite state {0,1,2} with non negative birth rates $(\lambda_0,\lambda_1)$and death rates $(\mu_1,\mu_2)$. Suppose $\mathbb{P}(X(0)=0)=1$ and $s_0=\inf ...
0
votes
0answers
8 views

How to find expectation of birth-death process

Let $\{X(t)\}$ be birth-death process on two-state space {0,1}. Let birth rate $\lambda=2$ and death rate $\mu=12$. How to calculate $\lim_{t\to\infty} \mathbb{E}[X(t)]$?
0
votes
1answer
9 views

Biased voter model survival

I have a biased voter on $\mathbb{Z}^d,$ where $d>0$ (I am mostly interested in the cases where $d>1$) with the bias parameter $\lambda$. In other words, let us have a process $X=(X_t)_{t \ge ...
0
votes
0answers
9 views

Inequality problem for Markov Process

Is there any upper bound available for the following quantity $$E[\max_{1 \leq k \leq n} X_k]$$ where $\{X_n\}$ is a Markov chain.
2
votes
0answers
47 views

Norris exercise: Showing $P_0[X_n\neq0\forall n\geq1]=6/\pi^2$

Consider exercise 1.3.4 of Norris' Markov Chains. The question is as follows: Let $\{X_n\}_{n\geq 0}$ be a Markov Chain with state space $S=\{0,1,2,\dots\}$. Suppose the transition probabilities ...
1
vote
1answer
22 views

An example of a reversible but reducible Markov chain

The reversibility of a Markov chain is defined in the following way with some basic propositions. Unfortunately all examples of reversible Markov chains shown in my textbook so far are irreducible, ...
2
votes
1answer
24 views

An example of a reducible random walk on groups?

Random walk on group is defined in the following way as a Markov chain. A theorem says the uniform distribution is stationary for all random walk on groups. If the random walk is ...
1
vote
0answers
28 views

The patterns of markov chain [on hold]

I have one question let $X$ be a Markov chain that could take the values $1,2$ or $3$ with the same probability $1/3$. what is the probability that $(1,2,1)$ pattern occurs sooner than $(2,1,3)$?
4
votes
0answers
23 views

Find a Markov chain transition kernel

Let $f_{X}$ be a density we would like to sample from. For some reasons, $f_{X}$ may be analytically intractable or expensive to evaluate. A solution consists in considering a density $(x,y) \in X ...
-1
votes
0answers
14 views

How is the measure of states defined in Markov Chain [on hold]

Given a Markov chain, is the sample space defined as "states"? how is the measure of the states defined? Does the measure depend on time?
0
votes
0answers
31 views

Identity for return times in continuous Markov chain

I need help with this problem about return times in continuous time Markov chains: We are given a continuous time Markov chain $(X_t)$. Define $T_i=\inf{\{t>0; X_t=i, X_{t-} \neq i\}}$, which ...
0
votes
0answers
28 views

First return times and continuous markov chains.

We are given a generator matrix $Q$ (Q-matrix) for a continuous time Markov chain $(X_t)_t. We want to calculate the probabilities of: returning to State 3 before State 1, while starting at State 3: ...
0
votes
1answer
20 views

Does such a Markov chain exist?

Suppose it has finite state space $S$, and $\lim\limits_{n\to \infty}p_{ij}^{(n)}=0$ for all $i,j\in S$. But guess is there isn't, since for a finite transition matrix, it is unlikely to have ...
0
votes
0answers
22 views

stationary distribution of outputs in Markov chain

consider a hidden Markov model with two states, with following transition/observation matrices: $T = \left( \begin{array}{cc} 0.9 & 0.1 \\ 0.1 & 0.9 \end{array} \right), O = \left( ...
1
vote
1answer
37 views

Discrete Time Markov Chain question

Let $\{X_n : n \ge 0 \}$ be a Markov chain with state space $ \{0, 1, 2, 3\} $ and transition matrix $$P=\begin{pmatrix} \frac{1}{4} & 0 & \frac{1}{2} & \frac{1}{4}\\ 0 & \frac{1}{5} ...
0
votes
1answer
21 views

Detailed balance implies time reversibility, how about the converse?

Given a Markov chain (finite state space) $X_1,X_2,...$ with transition matrix $P$ and initial distribution $\pi$, if they satisfy $\pi(x)P(x,y)=\pi(y)P(y,x)$, we say they satisfy detailed balance. ...
0
votes
0answers
58 views

Markov Chain Probability Limit

Show that the Markov chain on the state space $S=\{0,1,...,n \} $ with transition matrix: $$ P(k,l) = \binom{n}{l} \left(\frac{k}{n}\right)^{l} \left(\frac{n-k}{n}\right)^{n-l} $$ is such that, ...
3
votes
1answer
42 views

Rigorous argument of the Markov property used in discrete-time Markov chains

I am reading an example related to discrete-time Markov chains which I do not really understand rigorously. Suppose that $\{ X_n \}_{n \in \mathbb{N} }$ is a time-homogeneous discrete-time Markov ...
1
vote
2answers
32 views

Random Walk Definition

I have just begun studying this script about Random Walks, but I'm having trouble with a definition that is given there right at the beginning (page 10). We're looking at Random Walks on the square ...
0
votes
2answers
50 views

Transition Probability Matrix of Tossing Three coins

Three fair coins are tossed, and we let $X1$ denote the number of heads that appear. Those coins that were heads on the first trial (there were $X1$ of them) we pick up and toss again, and now we let ...
1
vote
0answers
26 views

An example of Markov chain with no closed class?

What is an example of Markov chain with no closed communicating class? Closed class means that once we are in that class, there would be no escape from it. I am thinking that an example would be ...
0
votes
1answer
11 views

How to solve for steady state matrix symbolically?

I'm trying to understand this solution to a question related finding the steady state matrix $s$ for a regular markov chain. Specifically I'm having trouble understanding how my textbook got $$ ...
0
votes
0answers
20 views

For which p is the Markov chain recurrent (almost random walk)

We have a Markov chain on Z with matrix: $p_{ii+1}=p=1-p_{ii-1}$ for $i\leqslant-1$, $p_{ii-1}=p=1-p_{ii+1}$ for $i\geqslant1$, and $p_{00}=p_{01}=p_{-10}=\frac{1}{3}$. For which values of p ...
2
votes
0answers
82 views

Probability mass function of the sum of the function of the sum of iid random variables

How can I get an expression of the probability mass function of: \begin{equation} Y_i=\sum_{k=1}^i f\left(\sum_{n=1}^{k} X_n\right) \end{equation} being $X_n, n=1,2,...$ iid random variables and ...
1
vote
1answer
18 views

Equality of probability of finite hitting time for irreducible states in Markov Chain

Suppose I have a finite state Markov Chain with state space $S=\{1,2,3,4,5,6\}$. Suppose I further have that $\{1,2\}$,$\{3,4\}$ and $\{5,6\}$ are irreducible classes where $\{1,2\}$ and $\{3,4\}$ are ...
0
votes
1answer
31 views

Why do recurrence and transience follow the $0-1$ law?

We say that a state $i\in S$ (where $S$ is the state space of a Markov Chain) is recurrent iff $P_i[X_n=i \space\text{i.o.}]=1$ and transient iff $P_i[X_n=i \space\text{i.o.}]=0$. My question is, ...
0
votes
1answer
32 views

Show that $m_{ii}=\infty$ when $i$ is transient

Show that $m_{ii}=\infty$ when $i$ is transient, where $m_{ii}$ is the mean time to get from $i$ to $i$. if $i$ is transient I know that there is a positive probability of going to some ...
0
votes
0answers
15 views

Markov Chains: is such classification of states and their properties correct?

After having finished a course on Markov Chains, I would like to build a summary of state properties. Could someone correct / confirm the following statements? Consider an irreducible time ...
0
votes
0answers
30 views

Skeleton of a continuous Markov Chain

I have a continuous Markov Chain with transition matrix $\Bbb P$ and with initial state $X_0=1$ and state space $I=\{1,2,3,4,5\}$ $$\Bbb P= \begin{bmatrix} -3 & 1 & 0 & 1 & 1\\ 0 ...
0
votes
1answer
20 views

Marginal distribution for a set of discrete events in continuous time

Assume we have a set of four events $\{(k_1,t_1),...,(k_4,t_4)\}$ where the $k_i$ label the type of event from a finite set of possible events, and the $t_i$ their respective times, with $t_i < ...
2
votes
2answers
33 views

Irreducible Markov chain. Pakes Lemma.

I've got problem with that task: Consider $\{Z_n\}_{n>0}$ is iid with integer values with expected value $\mathbb EZ_1<0$ and $\{X_n\}_{n\ge0}$ is homogeneous Markov chain defined by $$ ...
1
vote
1answer
28 views

Cont Time Markov Chains. Stationary Probability

A barber finishes haircuts at rate $3$, measured in hours, so on average it takes him 20 minutes to cut a person’s hair. Customers arrive at rate 2. There is, however, only a two chair waiting ...
0
votes
0answers
11 views

Markov chain recurrent state imply closed

It seems that the standard proof that if a class is recurrent it is closed goes along the lines: Suppose the opposite, i.e. the class is recurrent but not closed. Then there exists $i \in C$ and $j ...
0
votes
0answers
29 views

Average length of a rainy period

Weather is modelled as a Markov chain(first row corresponds to state $0$ (sunny), second row to state $1$(rainy)): $$ \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} $$ The problem is ...
0
votes
0answers
22 views

For which $\alpha>0$ is the chain recurrent?

The stochastic matrix $(p_{ij})_{i,j}$is defined as follows; $p_{01}=1, p_{i,0}=(i+1)^{-\alpha}, p_{i,i+1}=1-p_{i,0}$ for which $\alpha>0$ is the chain recurrent ? If the chain is ...
0
votes
0answers
16 views

Markov chain simulation of all possible sequences if you know the probability matrix

I'm taking Stanford's ee263 course online and have trouble with one of the homework problems.This is for self-study so it's all cool ! We consider a language or code with an alphabet of n symbols ...
0
votes
0answers
15 views

recurrence time for transient state

I have the following transition matrix for a MC with state space $S = \{ 1,2,3,4,5,6,7,8 \}$ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.4 ...
0
votes
0answers
24 views

Markov Chain (DTMC)

What is the expected number of times we need to roll a die until we get three consecutive 6's? I am trying to construct the transition matrix; however, I am not sure how also how to go from here.
3
votes
1answer
32 views

Uniqueness of the solution to a discrete boundary value problem

Given a Markov chain with state space $\Omega$ and transition matrix $P$, and $A\subset \Omega$, define function$f(x)=\Bbb E _x(\tau_A)$, where $\tau_A$ is the "stopping time into set $A$", meaning ...
0
votes
0answers
22 views

A question about the “stopping time with respect to a set” of a Markov chain

Given a Markov chain with state space $\Omega$ and transition matrix $P$, and $A\subset \Omega$, define function$f(x)=\Bbb E _x(\tau_A)$, where $\tau_A$ is the "stopping time with respect to a set", ...
0
votes
0answers
7 views

Deriving upper bound on number of recolorings of 3-colorable graph that 2-coloring won't give any monochromatic triangle

I clearly don't uderstand something in this exercise (because my answers seems to trivial to me). Let G be a 3-colorable graph. Consider the following algorithm for finding such a 2-coloring. ...
1
vote
2answers
28 views

The relation between the discrete Harmonic function and the Harmonic function in PDE

Given a Markov chain with state space $\Omega$ and its transition matrix $P$, a function $h(x):\Omega\to\Bbb R$ is called a harmonic at state $x$ if $h(x)=\sum_{y\in\Omega}P(x,y)h(y)$, and is called ...
2
votes
0answers
46 views

Convergence of empirical average of Markov chain from transient class

I am trying to get an intuition of how to understand the limit of the empirical average $$\frac1n\sum_{i=1}^nX_i\tag{$\ast$}$$ of some Markov chain $(X_n)_n$ with transition matrix $P$ (let's assume ...
0
votes
0answers
10 views

Efficient exploration of the “least important” nodes in a large graph

We call Markov Chain Crawler (MCC) a graph learner that is given query access to a Markov Chain Teacher (MCT) which itself is given a specific Markov Chain. At the beginning, the MCC is given some ...
1
vote
1answer
23 views

How to discretely stochastically simulate a continuous-time Markov chain?

A continuous-time markov chain describes a continuously varying process, such that future state only depends on the current state. A sampling of a continuous markov chain can be described in terms of ...
0
votes
0answers
11 views

Number of transitions in a 2-state markov chain in time t

Suppose I have a 2-state discrete-time Markov chain. Start in some initial state, and take t time steps forward. I want to know, what is the expected number of state switches (e.g. 1 -> 2 or 2 -> 1) ...