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
2answers
2k views

Markov chain with infinitely many states

I understand that a Markov chain involves a system which can be in one of a finite number of discrete states, with a probability of going from each state to another, and for emitting a signal. ...
0
votes
2answers
732 views

Markov Chain Reach One State Before Another

I'm stumped on a problem. Here's my transition matrix: $$P = \begin{bmatrix} \frac{3}{4}&\frac{1}{4}&0&0&0&0&0 \\\\ ...
1
vote
1answer
117 views

Proving a non-stopping time

Let $X_n$ be a Markov chain on the state space $\mathcal S$ and for $ y \in \mathcal S$ let $T_y = \min\{ n \ge 1 : X_n =y\}$ be the first return time to $y$. Let $W_y = T_y - 1$ be the time just ...
0
votes
1answer
123 views

Reversibility of Markov Process and Exponential Distribution of Transition Rates

I am reading the paper Towards Utility-optimal Random Access Without Message Passing by J. Liu, Y. Yi, A. Proutiere, M. Chiang, H. V. Poor. A sentence in Section 3.2 can be paraphrased as follows: ...
1
vote
2answers
102 views

Specific question to a Markov chain proof in Durrett

I apologize if this is to specific but i've already talked to two of my professors without much success and I really need to understand this subject. The following theorem is stated in Durrett page ...
2
votes
1answer
89 views

How does this Markov process involving balls and bins behave?

I have some set $S_1,\ldots,S_k$ ($k \geq 3$) of bins, each initially with $N_0(S_i)$ balls ($N_t(S_i)$ denotes the number of balls in $S_i$ at time $t$). A bin can contain a negative number of balls. ...
1
vote
0answers
120 views

Random Walk on $N\times N$ grid

I would appreciate any help (answers, pointers to the literature etc.) on the following problem. Consider a (discrete time) random walk on an N-by-N grid which has two absorbing nodes, namely $(1,1)$ ...
1
vote
1answer
221 views

Constructing a discrete Markov chain

Klenke gives a construction for a discrete Markov chain (Section 17.2 "Discrete Markov Chains: Examples", pp. 353-354). I don't understand several points in this construction, as indicated below. The ...
4
votes
4answers
619 views

Tricky Probability question

Each morning a student takes one of the three books he owns from his shelf. The probability that he chooses book $i$ is $a_i$, where $0 < a_i < 1$ for $i=1,2,3$ and the choices on successive ...
1
vote
1answer
93 views

Why is the Markov property implied by the existence of a transition matrix?

If $\left(X_n\right)_{n\in\mathbb{N}_0}$ is an $E$-valued stochastic process with distributions $\left(P_x\space:\space x\in E\right)$ satisfying $$\mathrm{P}_x\left(X_0=x\right)=1$$ and stochastic ...
0
votes
2answers
2k views

How to find expected time to reach a state in a CTMC?

Given a simple CTMC with three states 0,1,2. There are three transitions $0 \rightarrow 1$ (with rate $2u$), $1 \rightarrow 2$ (with rate $u$), $1 \rightarrow 0$ (rate $v$).So $2$ is an absorbing ...
0
votes
0answers
82 views

Martingale with reflecting barrier

I am not very familiar with the theory of martingales or random walks, perhaps someone could point me in the right direction or give me some help with the following problem. Consider a random ...
0
votes
1answer
351 views

Why is a random walk a time-homogeneous Markov process?

Why is a random walk on $\mathbb{R}^d$ (see below) a time-homogeneous Markov process? Specifically, why does it satisfy requirement #2 of definition 17.3 that the map ...
2
votes
1answer
232 views

Random walk on finite graph

I know that the stationary distribution of a random walk on the graph is given by, (degree of the node)/($2\times$ total number of links in graph). My question is, how do we get this solution?
4
votes
3answers
743 views

Invariant Probability Vector

I'm reading through my textbook, Introduction to Stochastic Processes (Lawler), before the semester begins in hopes of getting ahead, and I've run into something I just plain cannot figure out: How to ...
1
vote
1answer
229 views

Transforming an inhomogeneous Markov chain to a homogeneous one

I fail to understand Cinlar's transformation of an inhomogeneous Markov chain to a homogeneous one. It appears to me that $\hat{P}$ is not fully specified. Generally speaking, given a $\sigma$-algebra ...
1
vote
1answer
135 views

Expected number of jumps in a regular pure-birth process with Malthusian parameter.

Consider a pure-birth process $X(t)$ with rates $\lambda_i$ that satisfies $$\sum_{i=0}^\infty \frac{1}{\lambda_i} = \infty.$$ By Reuter's criterion this is sufficient for $X(t)$ to be regular, ie ...
1
vote
1answer
87 views

Is this a valid proof for recurrence time?

The following is a well known result of Markov chain: Given a Markov chain $(X_t)_{t \ge 0}$, if $T_{ii}$ denote the time of the first return to state $i$ when starting at state $i$, then we ...
2
votes
1answer
104 views

Expected number of jumps in regular jump HMC

Consider a homogeneous Markov Chain $X$ on a countable state space, ie a jump process. It is said to be regular (does not explode) if there are only a finite number of jumps in every finite interval. ...
1
vote
1answer
77 views

spectral gap of the graph / Markov chain

Let $G=(V,E)$ be a graph. The gradient of a function $f:V\longrightarrow R$ is defined on the edges of the graph, given by the discrete derivative $$ \nabla f(e)=f(y)-f(x), \quad e=(x,y) \in E $$ ...
1
vote
1answer
127 views

Gradient of a function on the vertices of a graph

Let $G=(V,E)$ be a graph. The gradient of a function $f:V\longrightarrow R$ is defined on the edges of the graph, given by the discrete derivative $$ \nabla f(e)=f(y)-f(x), \quad e=(x,y) \in E $$ ...
0
votes
2answers
546 views

Why is every irreducible matrix with period 1 primitive?

In a certain text on Perron-Frobenius theory, it is postulated that every irreducible nonnegative matrix with period $1$ is primitive and this proposition is said to be obvious. However, when I tried ...
1
vote
2answers
245 views

Average run lengths for large numbers of trials: Intuition and proof

This article states that the formula for the average run lengths for large numbers of trials is:$$\frac{1}{1-Pr(event\ in\ one\ trial)}.$$ My questions What is the intuition behind this formula? Do ...
4
votes
1answer
284 views

question involving Markov chain

Let $S_{2m}$ be the group of all permutations $\pi$ of $\{1, 2, \ldots, 2m\}$. The following transition kernel $S$ generates the random transposition walk $$ Ch(\pi, \pi')= \begin{cases} \frac{1}{2m} ...
1
vote
0answers
51 views

Markov chain supplementary litterature

I'm studying markov chains through Durrett and I'm finding it quite hard to read. Does anyone have a good idea to supplementary book, preferably one on his level of generality and which studies some ...
0
votes
1answer
90 views

Confusion in probability calculation

I was referring to this wiki article related to forward and backward algorithm Actually, I didn't get this part $$ \frac{P(o_1,o_2..o_T,X_t=x_i|\pi)}{P(o_1,o_2..o_T|\pi)} = ...
4
votes
1answer
517 views

Markov chains- recurrence and transience

This is an exercise in Durrett's probability book. $p$ is the transition probability for a markov chain on a countable space. $f$ is said to be superharmonic if $f(x)\geq\sum_y p(x,y)f(y)$, or ...
0
votes
1answer
353 views

How are the pairs of two independent pure-birth processes a Markov process?

A pure-birth Process is a generalization of a homogeneous Poission process. Whereas in the Poisson process the holding times between jumps are iid exponentially distributed random variables with ...
4
votes
2answers
121 views

Markov and independent random variables

This is a part of an exercise in Durrett's probability book. Consider the Markov chain on $\{1,2,\cdots,N\}$ with $p_{ij}=1/(i-1)$ when $j<i, p_{11}=1$ and $p_{ij}=0$ otherwise. Suppose that we ...
1
vote
0answers
46 views

How to sample the walk which visits each vertex of a graph specific number of times?

Is there any MCMC mathod that allow me to uniformly sample from all feasible walks where the following restrictions apply: ...
2
votes
1answer
518 views

Understanding a Markov Chain

I am using a Markov Chain to get the 10 best search results from the union of 3 different search engines. The top 10 results are taken from each engine to form a set of 30 results. The chain starts ...
0
votes
1answer
77 views

The existence of stopping rule from one distribution to another.

Let $(X_n, n \ge 0)$ be a Markov chain. Let $V$ be the state space. Let $\lambda$ and $\tau$ be two probability distribution. Can we say that for any $\lambda$ and $\tau$, there is always a ...
1
vote
1answer
363 views

A Markov chain probability calculation.

I'm taking a course about Markov chain, and here's a snippet from the lecture notes: Let $(X_i, i \ge 0)$ be a time homogeneous Markov chain, let $V$ be the state space, let $\lambda$ be the ...
2
votes
1answer
4k views

Expected number of steps/probability in a Markov Chain?

Can anyone give an example of a Markov Chain and how to calculate the expected number of steps to reach a particular state? Or the probability of reaching a particular state after T transitions? I ...
3
votes
2answers
245 views

Martingale associated to Markov chain

$X$ is a (continuous time) Markov chain with generator matrix $\Lambda$ and finite state space $G$. I know that for $g\colon G \to R$ $$ M_t = g(X_t) - g(X_0) - \int_0^t (\Lambda g)(X_s)\, ds $$ is a ...
0
votes
1answer
240 views

Conditional Expectation.

Are the following two the same: $E[V(X_{t_{k+1}})|g(X_{t_{k+1}}),X_{t_k}]$ and $E[E[V(X_{t_{k+1}})|g(X_{t_{k+1}})]|X_{t_k}]$ Where $X$ is Markov chain $X_{t_k} \in \mathcal{R}^n$ $V: ...
2
votes
1answer
185 views

Eigenvalues of a quasi-stochastic matrix

Quasi-stochastic In order not to make the title too long I used the term Quasi-Stochastic with this meaning: a quasi-stochastic matrix $Q$ is a square matrix $Q = ...
5
votes
2answers
4k views

Is ergodic markov chain both irreducible and aperiodic or just irreducible?

As I find some definition says: Ergodic = irreducible. And then Irreducible + aperiodic + positive gives Regular Markov chain. A Markov chain is called an ergodic chain if it is possible to go ...
1
vote
2answers
1k views

Can Markov Chain state space be continuous?

I looked for a formal definition of Markov chain and was confused that all definitions I found restrict chain's state space to be countable. I don't understand purpose of such a restriction and I have ...
0
votes
2answers
141 views

Issue with calculating the cholesky decomposition

I am trying to calculate the cholesky decomposition of the matrix Q= ...
0
votes
3answers
100 views

Capacity of a discrete channel in the telegraphy case

I'm reading Shannon's article A Mathematical Theory of Communication, and I'm stuck at the telegraphy case example, on page 4. Shannon writes a formula involving $N(t)$, the number of sequences of ...
2
votes
2answers
193 views

Markov chain basic positive recurrency question

If a discrete markov chain is stationary (as far as I know: doesn't modify itself with time), irreducible (doesn't have transient states) and aperiodic (no periodic states), is it positive recurrent? ...
1
vote
0answers
74 views

Positive recurrence of a continuous-time jump process, from its jump chain

I am looking at an irreducible, continuous-time jump process $(X_t)_{t\geq0}$ with the following jump times. Let a Poisson process $(T_i)_{i=1}^\infty$ determine the event times. With probability ...
2
votes
0answers
202 views

Computing the stationary distribution of a markov chain

I have a markov chain with transition matrix below, $$\begin{bmatrix} 1-q & q & & & \\ 1-q & 0 & q & & \\ & 1-q & ...
14
votes
1answer
529 views

Eigenvalues for $3\times 3$ stochastic matrices

This is a plot of the non-real eigenvalues of 10000 randomly generated $3\times3$ stochastic matrices. It's pretty clear that they lie in the convex hull of the three cube roots of unity. The ...
1
vote
2answers
178 views

Finding again the stationary distribution of a markov chain

I am asked to compute the stationary distribution of the markov chain with state space $E=\{0\dots,n\}$ and transition matrix below: \begin{bmatrix} 0 & 1 \\ \frac{1}{n} ...
3
votes
1answer
2k views

Finding the stationary distribution of a markov chain

I am asked to compute the stationary distribution of the markov chain with state space $E=\mathbb{N}_0$, $q_n >0$ for all $n \in \mathbb{N}_0$ and transition matrix below: \begin{bmatrix} q_0 ...
3
votes
1answer
1k views

Calculating stationary distribution of markov chain

I am asked to compute the stationary distribution of the markov chain with state space $E=\{0\dots,n\}$ and transition matrix below: \begin{bmatrix} 0 & 1 \\ \frac{1}{n} ...
1
vote
1answer
365 views

Why does this example of Hardy-Weinberg equilibrium not work?

Background Info Hardy-Weinberg equilibrium is a mathematical model of the frequencies of alleles (i.e., versions of a gene) in a population. The model states that the frequency of the 2 alleles in a ...
3
votes
1answer
4k views

Kendall notation's “General distribution”, what does that mean?

The first and second parameters for the Kendall's notation may have a G value, which stands for General distribution, see here. But what does that mean? What is a ...