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

3
votes
1answer
766 views

Probability distribution of markov chain

I have a Markov chain with state space $E = \{1,2,3,4,5\}$ and transition matrix below: $$ \begin{bmatrix} 1/2 & 0 & 1/2 & 0 & 0 \\ 1/3 & 2/3 & 0 ...
3
votes
1answer
1k views

coin flips and markov chain

Consider the case of an infinite (or finite $n$) string of coin tosses, and let $q$ and $1-q$ be the probabilities that the coin comes up tails and heads, respectively. (For simplicity, we can take ...
3
votes
1answer
91 views

What happens to a regular Markov matrix that has more than one steady state/stationary distribution?

It is known that for a regular Markov matrix $M,$ $M^{n}$ has the steady-state vector as all of its columns as $n \to \infty.$ I learned this in class, but what if there is more than one steady-state ...
3
votes
1answer
235 views

Identifying states in Markov chains

I just started learning about Markov processes and got the following homework question. Classify all the states as recurrent or transient for the Markov chain below $$\begin{matrix} ...
3
votes
0answers
29 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
63 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 ...
3
votes
0answers
42 views

Invariant measure of Euler-Maruyama Discretisation of an Ito diffusion

Let $(X_t)_{t \geq 0}$ be a diffusion process with dynamics governed by the stochastic differential equation \begin{equation} dX_t = b(X_t)dt + \sigma(X_t)dW_t, ~~ X_0 = x_0, \end{equation} where ...
3
votes
0answers
43 views

Standard deviation of a quantum walk?

The standard deviation of a classical random walk with $n$ steps is $\sqrt n$ - Standard deviation of a random walk. I have read in many places that the standard deviation of a quantum walk $n$ with a ...
3
votes
0answers
75 views

Markov Chain Alternate Expectation

Consider a Markov chain defined by transition matrix $P$ such that for each transition from state $i\rightarrow j$ the probability is $p_{ij}$. Now say there is an associated value for each transition ...
3
votes
0answers
95 views

SLLN of Markov chains .

Let $X_1$, $X_2$,... be a finite state, irreducible and aperiodic Markov chain with initial state $X_0=i$. It is known that \begin{equation} \mathrm{P}\Big\{\lim_{n\rightarrow\infty} ...
3
votes
1answer
73 views

expected hitting time with two absorbing states

Consider a Markov chain in a finite space and with two absorbing states, each of which is accessible from the other, transient states. Is the expected number of transitions to reach any single ...
3
votes
0answers
90 views

Prove the 2 definitions of the periodicity of Markov Chain are equivalent.

In many textbooks, there are basically 2 ways of defining the periodicity of Markov Chain. One is by partitioning the graph in to subgraph such that transition in one group of state leads to the other ...
3
votes
0answers
109 views

Monotonic convergence of powers of a stochastic matrix

Let $P$ be a stochastic matrix (nonnegative and each row summing to 1). Assuming that $P^n$ converges to $\textbf{1}\pi$ as $n \rightarrow \infty$, where $\pi$ is a row vector (stationary distribution ...
3
votes
0answers
95 views

maximum renewal rate of a Markov chain

Consider a Markov chain $(X_t)$ on a state-space with a countably generated $\sigma$-algebra and assume this Markov chain allows for small sets of order one. This means there exist sets $\mathfrak{S}$ ...
3
votes
0answers
133 views

Generalization of Dobrushin's Ergodic Decomposition for continuous Markov Chains

Let $T$ be the shift transformation. Let $P$ be invariant for $T$ and also define a discrete state space Markov Chain. Let $C_{1},\ldots,C_{n}$ be the connected components of the Markov Chain. It ...
3
votes
0answers
33 views

Name for maximum transition probability

Let $p(x,y)$ denote the transition probability of a markov chain. Similarly, let $p^n(x,y)$ be the n-step transition probability. My question is, is there a formal name for $S(x,y):=\sup_n p^n(x,y)$. ...
3
votes
0answers
60 views

When is this reversible diffusion on the integer lattice non-exploding?

Let $U\in C^{\infty}(\mathbb R^n;\mathbb R)$ and consider a continuos time Markov chain on the scaled integer lattice $\delta\mathbb Z^n$ with jump rates given by $r_{\delta}(x,y) := \begin{cases} ...
3
votes
3answers
189 views

Markov chain stationary probability simulation

Having a defined markov chain with a known transition matrix, rather than to calculate the steady state probabilities, I would like to simulate and estimate them. Firstly, from my understanding there ...
3
votes
0answers
236 views

Probability question about change in vending machines; maybe markov chain?

Suppose there are vending machine that sells its goods for $3$. It's known that a third of the buyers use three coins of $1$, a third of the buyers use $2$ and $1$, and the last third use $5$. The ...
2
votes
2answers
60 views

Transition Matrix eigenvalues constraints

I have a Transition Matrix, i.e. a matrix whose items are bounded between 0 and 1 and either rows or columns sum to one. I would like to know if it is possible that in any such matrices the ...
2
votes
2answers
299 views

The second largest eigenvalue for Perron-Frobenius matrix

The Perron-Frobenius theorem is about the largest eigenvalue and eigenvector of a non-negative (irreducible) matrix. My question: Is there any estimation of the difference between the first and ...
2
votes
1answer
2k views

What does the steady state represent to a Markov Chain?

I'm a little confused as to the interpretation of the steady state in the context of a Markov chain. I know Markov chains are memoryless, in that each state only depends on its immediate predecessor, ...
2
votes
1answer
3k views

How can I compare two matrices?

I have a matrice A. It is model probability matrice for some process (Markov chain). Then, I have estimated matrice B. I have to somehow compare these two matrices to tell whether process that gave ...
2
votes
2answers
118 views

Using Markov - Chain to find average and probability

Suppose a computer generate a random vector of n positions where each position appears on of the numbers from 1 to n. The generation is performed uniformly on the $n!$ possibilities. In the problem we ...
2
votes
2answers
138 views

Professor has 4 umbrellas, Markov chain and Probability

OK this problem is making me tear my hair out. I need someone to walk me through this in baby-steps method like 1 + 1 = 2. I am trying to figure out what I don't understand. I know this is going to be ...
2
votes
2answers
100 views

Independence of the first passage time of a Markov chain being less than or equal to $n$ and $X_n$

I am reading my lecture notes on Markov chains, and in the proof of one proposition the following statement is made: "For $n = 1,2, \dots$ the event $\{n \leq T_k\}$ depends only on $X_0, \dots, ...
2
votes
2answers
51 views

Is there a proof that the observations of a hidden Markov chain is not itself a Markov chain?

Suppose $\{X_n\}$ is the hidden Markov chain, and $\{Y_n\}$ is the series of observations, where $\mathbb{P}\{Y_n = j| X_n = i\}$ is the same for all $n$ (please correct me if I have not stated the ...
2
votes
1answer
523 views

A problem on Expected value using the survival function

Let $X$ be a random variable denoting the number of times needed to roll ( including the last roll) a fair six-sided die until we obtain 4 consecutive six's. I would like help in computing ...
2
votes
1answer
67 views

Random walk on connected graph: show $E_vT_w \ne E_wT_v$

Let $G$ be a connected graph on at least 3 vertices in which the vertex $v$ has only one neighbor, namely $w$. Let $(X_t)_{t \ge 0}$ be a simple random walk on $G$, where $X_t$ is the current vertex ...
2
votes
1answer
28 views

Proving that a HMC state is recurrent or transient?

Looking at the HMC $$\begin{bmatrix} 1-\alpha & \alpha \\ 0 & 1 \end{bmatrix} $$ How do I prove that the state 2 is recurrent and that state 1 is transient? What does it actually mean by ...
2
votes
2answers
119 views

How do you prove that the second largest number $Y_n$ shown among the first $n$ rolls is not a Markov Chain?

How do you prove that the second largest number $Y_n$ shown among the first $n$ rolls is not a Markov Chain? My attempt: Consider the case, $P(Y_{n+1}=3|Y_n=1)=\frac{1}{6}$ if the current ...
2
votes
2answers
118 views

Wald's equation example controversy

I'm trying to get a grip of Wald's equation, applying it to the following example. Suppose, we have a simple sequence of fair coin flips, where heads wins us a dollar, while tails means loss of a ...
2
votes
2answers
71 views

Random walk on one-dimensional lattice - understanding the expression $pe^{i\theta} + qe^{-i\theta}$

I've started reading the book - First Steps in Random Walks and in the very first example in Chapter 1 they talk about a random walk on a one-dimensional lattice. If we consider a particle starting ...
2
votes
2answers
1k 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. ...
2
votes
1answer
174 views

Some basic questions on Markov chains (Durrett)

If you have a state space $S$, usually I think of a Markov chain $X_n$ on it as $X_n$ takes values in $S$ and satisfies the obvious Markov property and so on. In Durrett's book, he says one should ...
2
votes
2answers
276 views

What does it mean for MCMC to converge?

I know that a Markov Chain is a discrete random process where the current state decides the next and in a random walk, the probability that we move from node u to v is 1/N(u). An MCMC sample will ...
2
votes
2answers
279 views

Calculating probabilities (Markov Chain)

Let $\mathcal{X}=(X_n:n\in\mathbb{N}_0)$ denote a Markov chain with state space $E=\{1,\dots,5\}$ and transition matrix ...
2
votes
1answer
80 views

Irreducible MCs

Why is it that theorems for (discrete) Markov chains always require that the MC concerned is irreducible? Can problems with reducible MCs can be simplified to considering the irreducible components? ...
2
votes
3answers
601 views

How to show Martingale property for sum of $S_k-E(S_k)$-summands where $S_k$ is a function of two RV's

EDIT: new formulation of the question (old version below). In a paper I found the statement that a certain sum $M_n =Y_1+\dotsb Y_n$ is a martingale, $Y_i=f (X_k, Z_k) - E ( f(X_k, Z_k) | X_k)$. (The ...
2
votes
1answer
31 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$ ...
2
votes
2answers
23 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 ...
2
votes
1answer
22 views

Applying transition matrix to a probability vector seems to ruin its normalization

I had a little bit about stochastic processes during my "Statistical Physics" course and on my exam I got a problem with a Markov chain. My solution seems to be without computational mistakes (checked ...
2
votes
1answer
28 views

Markov chains by hand

If I have a starting point: $A_T=[0,1]$ at $T=1$ and a one step transition matrix of: $B=\left[ \begin{align} &\frac34 & \frac14& \\& \frac1{20}& \frac {19}{20} &\end{align} ...
2
votes
1answer
56 views

Inverse of a regular stochastic matrix

Is it true that the inverse of a regular stochastic matrix is also regular? Are there any other interesting features that the inverse may have of a regular stochastic matrix? Hope someone could answer ...
2
votes
1answer
56 views

time-homogeneous continuous time Markov chain

I have a question about the continuous time Markov chain. In the Poisson process we have independent and stationary increments. Do we have this in a continuous time Markov chain that is ...
2
votes
1answer
33 views

Is the following Markov Chain a martingale?

Say I have a finite, ergodic Markov chain with states ${0,1,2,3}$ and with the following transition matrix: $$\begin{bmatrix} \frac{7}{10} & \frac{3}{10} & 0 &0\\ \frac{1}{10} & ...
2
votes
1answer
53 views

Probability distribution of Poisson process

Let $X_t$ and $Y_t$ be two independent Poisson process with rate parameter $\lambda_1$ and $\lambda_2$, respectively, measuring the number of customers arriving in stores $1$ and $2$, respectively. ...
2
votes
2answers
48 views

Generate random sample with three-state Markov chain

I have a Markov chain with the transition matrix $$\pmatrix{0 & 0.7 & 0.3 \\ 0.8 & 0 & 0.2 \\ 0.6 & 0.4 & 0}$$ and I would like to generate a random sequence between the three ...
2
votes
1answer
104 views

Markov chain problem with finite states

Consider any Markov chain on a state space with exactly $r$ states. We want to find the largest $N>0$ such that there exists states $i,j$ for every $n < N$ we have $p_{ij}^{(N)} > 0$ and ...
2
votes
1answer
167 views

Markov chains: is “aperiodic + irreducible” equivalent to “regular”?

I have two books on stochastic processes. In one book, it says that the limiting matrix is possible to find if the matrix is regular, that is, if for some $n$ $P^n$ has only positive values. The ...