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
43 views

Steps in a proof from Spectral Graph Theory by Fan Chung

On page 15 of Spectral Graph Theory by Fan Chung, http://www.math.ucsd.edu/~fan/research/cb/ch1.pdf, before eq (1.14) is the step, $\displaystyle || \sum_{i\neq 0} (1-\lambda_i)^s a_i \phi_i ...
0
votes
0answers
11 views

minimum condition under which time avg. and ensemble avg. are equal for a markov chain

What is the minimum condition under which time avg. and ensemble avg. are equal for a markov chain. Is it ergodicity ?
1
vote
1answer
33 views

In an irreducible, aperiodic, null-recurrent Markov chain holds $\sum_n p_{ij}^{(n)} = \infty$

My lecture notes state the following theorem: Theorem 2. Let $(X_n)$ be an irreducible, aperiodic, null-recurrent Markov chain. Then $$\forall i,j \in S : p_{ij}^{(n)}\to 0 \text{ and } \sum_n ...
1
vote
1answer
137 views

A Markov Chain Problem.(Change the color of ball)

There are $n$ different color balls in a box. Take two balls in turns, and change color of the second ball to the first. (This is one operation). Let $k$ be the (random) number of operations needed to ...
1
vote
1answer
37 views

Markov property for discrete Markov chains. A question about “adjacent random variables”

Consider a discrete Markov chain (with values in $\mathbb R$) $\{X_n:\, n\in\mathbb N\}$: namely the state space $S$ is a countable subset of $\mathbb R$ and the random variables are $X_0, X_1, ...
0
votes
1answer
118 views

M/G/1 queue has embedded Markov chain

I tried to prove that the M/G/1 queue has an embedded discrete-time Markov chain. But I'm not sure if I have done it right and properly. Specially I'm not 100% sure if i calculated right the ...
0
votes
1answer
45 views

How to apply the strong Markov property in this case?

I'm trying to understand the following proof: Theorem: Let $(X_n)$ be an irreducible $(\alpha, \mathbf p)$-Markov chain with a finite state space $S$. Then $(X_n)$ is positive recurrent. ...
1
vote
1answer
46 views

How to find the conditional expectation of the following random variable?

Let $\{N_n; n=1,2,3,\dots,\}$ be an irreducible and aperiodic Markov chain with transition probability matrix $\mathcal{P}=\begin{pmatrix} p_{0,0} & p_{0,1}&p_{0,2}&\cdots \\p_{1,0} & ...
1
vote
0answers
53 views

Cereal boxes - Mean time spent in transient states

Problem: A cereal company gives 2 images in each cereal box it has. There are a total of 5 images. Once a buyer have 5 images she wins a prize. No box contains 2 images that are the same. What is the ...
1
vote
1answer
37 views

Branching process: Why does the population die or explode?

Consider a population such that each member, independently from other members, at a certain instant of time is replaced by its offspring. Lets denote with $X_n$ $({n\ge 1})$ the amount of the ...
1
vote
1answer
33 views

Max of independent and identical random variables is Markov

I'm supposed to show that given a sequence $\{Y_n\}$ of i.i.d the stochastic process $$X_n=\max(Y_0, Y_1...,Y_n)$$ is a Markov of chain. I think I could do it by induction but I would rather see how ...
1
vote
1answer
52 views

Markov Property as given in Norris' book on Markov chains vs standard formulation

In the book, Markov Chains, the following theorem is mentioned: Let $(X_n),n≥0$ be Markov$(λ,P)$. Then, conditional on $X_m=i,(X_{m+n})_{n≥0}$ is Markov$(\delta_i,P)$ and is independent of the random ...
1
vote
0answers
62 views

Follow-up on solution to Markov process equation

I asked a question here about solving a system related to an absorbing Markov chain. I now have a variation where there are $m$ types (of student, job seeker, etc) each of which applies to ...
2
votes
1answer
24 views

Limit distribution is invariant

Consider a homogeneous Markov chain $\{X_n\}_{n\in\mathbb N}$ with a countable (but not necessarily finite) state space $S$. Suppose that there exists a limit distribution $\pi$, namely: ...
1
vote
1answer
25 views

About homogeneous Markov chains

Consider a homogeneous Markov chain $\{X_n\}_{n\in\mathbb N}$ with discrete state space $S$. Now consider the map $$T_{ij}=\text{min}\{n\in\mathbb N\,:\, X_n=j\mid X_0=i\}$$ where $T_{ij}$ is defined ...
0
votes
0answers
22 views

Markov Models and Applications

I am looking for resources in Markov models and its applications. I'm looking for tutorials, videos, books etc which provide the following Explain Markov chains in layperson terms and provide ...
1
vote
1answer
49 views

Why are points from this matrix geometric sequence co-planar?

Let $ M= \left[ {\begin{array}{ccc} a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \\ \end{array} } \right] $, such ...
3
votes
0answers
40 views

A basic doubt on Markov chain/ergodicity

Consider a finite state (no. of state $N$) Markov chain $\{X_n\}$ (all the random variables are bounded) such that there is a state $i*$ such that $$ \sum_{i=1}^{N}p_{ii*}^{(n)} > 0$$ for all ...
3
votes
1answer
145 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 ...
0
votes
0answers
53 views

A question about a Markov Chain

I encountered a question about Markov Chains which looks interesting. Given a homogeneous, irreducible, non cyclic Markov Chain with $K$ possible states and a transition matrix $Q$. We define $T_i$ ...
0
votes
1answer
216 views

Supply the transition matrix for these (possible) Markov chains

Reading Grimmet, Stirzaker: Probability and Random Processes, which unfortunately doesn't have solutions. Trying to make sure I understand Markov chains. A die is rolled repeatedly. Which of these ...
0
votes
0answers
29 views

Probabilities in a Markov Model

I am reading a paper on Markov Models and I am trying to figure out how to compute the probabilities for the $\alpha$-pass. I am given an $N\times N$ matrix $A$, that has the probabilities of ...
0
votes
0answers
35 views

Treatment of Markov process with absolute states

In the standard treatment of a markov process, the state vector is a probability vector, whose elements can be between zero and one. But I have a need to constrain the state vector to zeros or ones. ...
4
votes
1answer
291 views

Conditional return time of simple random walk

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$. Call $\tau_k = \min\{t \in \mathbb{N}\, : \, \, S_t =k \}$, the hitting time of $k \in \mathbb{N}$. Call $\tau^* = \min\{t ...
2
votes
1answer
163 views

Markov Chain with Memory

One of the defining characteristics of a Markov Chain is that it is memoryless: the next state depends only on the current state, and not on the set of preceding states. I'm looking for a ...
1
vote
2answers
160 views

Measuring the entropy of a graph representing a transition probability matrix of a first order markov chain

There's a research project i'm currently working on which requires me to analyze various aspects of "worlds" represented by transition probability matrices, where the nodes represent objects in the ...
0
votes
0answers
81 views

Exact probability distribution for hitting time of simple random walk

Consider simple random walk on the line starting from the site $y \in \mathbb{N}$. With probability $p$ the walker moves to the right and with probability $1-p$ to the left. Call $\tau$ the first time ...
0
votes
1answer
284 views

Application of Conjugate Gradient Method to non-symmetric matrices

I am currently working on a problem in which I am using the Conjugate Gradient method to solve for the steady state solution of a continuous time Markov chain. I am applying the algorithm found in ...
2
votes
1answer
98 views

Green's function of a Markov Chain, and maybe of a Feller Process?

How are the Green's functions of a Markov chain related to the notion from PDE theory? For instance, if the Markov chain (i.e. discrete state space) is continuous time, then the Green's function I'm ...
0
votes
1answer
278 views

Continuous time markov chains, is this step by step example correct

I have some questions regarding CTMC... and most importantly whether the step-by-step example I provide below is correct. My main sources about CTMC are: ([1], and [2]). Let's assume 3 possible ...
2
votes
1answer
171 views

Why left multiplication when it comes to Markov chains?

When working with Markov chains and transition matrices $P$ we multiply from the left, meaning that for example $\mu^{(n)} = \mu^{(0)}P^n$ or that the stationary distribution satisfies $\pi = \pi P$. ...
0
votes
1answer
193 views

Can the transition probabilities of an inhomogeneous Markov chain be written as an exponential?

If $Z_t$ is a homogeneous continuous-time Markov chain with finite state space $E=\{1,\ldots,p\}$, transition matrices $(P(t))$ and intensity matrix $Q$, it holds that $$ P(t) = \exp(tQ), $$ see for ...
2
votes
1answer
139 views

Finding the probability of ever visiting a transient state for a zero-seeking device for a Markov Chain?

A zero-seeking device operates as follows: if it is in state $j$ at time $n$, then at time $n+1$, its position is $0$ with probability $\frac{1}{j}$ or $k$ with probability $\frac{2k}{j^2}$, where $k$ ...
1
vote
1answer
91 views

Producing transient and recurrent examples for birth-death chains with mixed birth- and death-probabilities

Suppose we have a birth-death chain with a state space $$ S = \{0,1,2,\ldots\} $$ and transition probailities: $$p(x,y)=\begin{cases}q_x, &\text{if } y = x-1, &\text{i.e. death}\\ ...
1
vote
0answers
30 views

A question about Markov

There is a continuous-time markov chain,and we know the probability transition matrix P.The time between 2 states can be formulated as a exponential distribution whose u is related to the 2 states.Now ...
0
votes
1answer
79 views

Board Game Markov Process - Transient Probabilities

I need to write an essay on the Game of Life board game, and so I studied up on Markov Chains to help me calculate the probabilities and average payoffs for the spaces; however I'm not sure whether ...
0
votes
1answer
65 views

Control principal eigenvector of a row stochastic matrix

I am just trying to consider the classical discrete-time Markov Chain problem. Consider the transition matrix P, which transforms state vector $x(k)$ to $x(k+1)$, satisfying: $x(k+1)$ = $P*x(k)$ It ...
1
vote
1answer
80 views

Q-matrix vs. P-matrix description of a Markov chain

Consider a continuous time Markov chain $(X_t)_{t \geq 0}$ on some state space $S$ with transition matrix (P-matrix) $p_t(x,y)$, the probability density of jumping from $x$ to $y$ in time $t$. The ...
2
votes
2answers
40 views

Probability of returning to a given state after n transitions-Markov chains

Let us denote $f_j^{(n)}$ denote the probability of the first return to state $j $after n transitions. Let $p_{jj}^{(n)}$ be the probability of returning to the state $j$ after $n$ transitions when ...
1
vote
1answer
64 views

Symmetric random walk and the distribution of the visits of some state

I need help with this problem: Let $(S_n)_n$ a symmetric random walk in $\mathbb{Z}$ i.e $S_n=X_1 + \cdots + X_n$ with $(X_n)$ iid $\mathbb{P}(X_n=1)=\mathbb{P}(X_n=-1)=\frac{1}{2}$. Let $m \in ...
-1
votes
1answer
88 views

How to make sense out of this: Ergodic theorem for Markov chains

We had the ergodic theorem for Markov chains, stating that: For a state space $S \subset \mathbb{N}$ and all functions $f \in L^1$ (meaning that $\sum_{s \in S} |f(s)|\pi(s) < \infty$) and an ...
3
votes
1answer
169 views

2D random walk variation

If a point on a 2D lattice is allowed to take a random walk by taking a unit step either up, down, left or right, there is probability $1$ of reaching any point (including the starting point) as the ...
1
vote
1answer
75 views

Need help with a basic exercise about Markov chains

Suppose $\left\{ X_{n}\right\} _{n=1}^{\infty}$ is a Markov Chain taking real values. Are the following Markov Chains? $$Y_{n}=\sum_{i=1}^{n}X_{i} , Z_{n}=\left(X_{n},X_{n-1}\right)$$ Edit1 I ...
0
votes
1answer
24 views

Is there a relationship between the mean matrix and the transition matrix of a multi type branching process?

Let $\mathbf{M}$ be the mean matrix of a multi type branching process $(\mathbf{Z}^{(n)})_{n\geq1}=((Z^{(n)}_1,\ldots,Z^{(n)}_k))_{n\geq1}$. This matrix is defined as follows $$M_{i,j}=\mathbb ...
0
votes
1answer
68 views

Long run behavior of a absorbing markov chain

$$A=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0.2&0&0.6&0.2\\0&0.2&0.2&0.6\end{pmatrix}.$$ In the above matrix how do I calculate the probability that in the ...
0
votes
1answer
22 views

Return Lemma MC

If a Markov chain is $\phi$-irreducible and has stationary distribution $\pi$, then $\phi\ll \pi$, Proof: We use the irreducibility of the chain to write the state space $E = \bigcup_{n,m \in ...
1
vote
1answer
29 views

Markov chains: An issue in classification of states

I recently came across a lemma which goes as follows. Suppose a Markov chain has N states. Let i and j be pair of states. Then j can be reached from i iff there is an integer $ 0 ≤n< N$ such ...
0
votes
2answers
106 views

Expected number of steps to absorbtion - Markov chain

I want to calculate the expected number of steps (transitions) needed for absorbtion. So the transition probability matrix $P$ has exactly one (lets say it is the first one) column with a $1$ and the ...
0
votes
2answers
63 views

Given a Markov-chain, what is the probability of being at a given state?

Given a Markov-chain, what is the probability of being at a given state? I drew the diagram below just as an example, there is nothing special about it but it would be nice if your answer used it as ...
0
votes
1answer
56 views

How do you find the probability of a certain state in Markov Chain?

This question appears without answer in an old exam I found (not a homework question) Suppose messages that enter a system need to be processed by two servers. They arrive at the system at a ...