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
0answers
52 views

Why a positive recurrent Markov chain implies positive limiting probability?

Let $X=\{X_0,X_1,\ldots\}$ be an irreducible, positive recurrent, and aperiodic Markov chain with the state space $S=\{0,1,2,\ldots\}$ then how do we show that the probability $$ ...
3
votes
2answers
202 views

Interpretation for the determinant of a stochastic matrix?

Is there a probabilistic interpretation for the determinant of a stochastic matrix (i.e. an $n \times n$ matrix whose columns sum to unity)?
3
votes
0answers
38 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
162 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
75 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
151 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
1answer
120 views

Dice probability of a winning more than $X\%$ of the time over $Y$ Throws

I have a die with three possible outcomes. The three outcomes are win (+1), draw (0) and lose (-1). $P(w) + P(d) + P(l) = 1$. (1) If I throw the die Y times, what is the probability I will win $X$ ...
3
votes
0answers
108 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
92 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
129 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
1answer
184 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
105 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
140 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
65 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
0answers
252 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
63 views

Under what conditions does $(I-N)^{-1}$ exist?

Given an nxn matrix N and $I=I_n$, under what conditions does $(I-N)^{-1}$ exist? On one hand $(I-N)(I + N + N^2 + ...) = (I + N + N^2 + ...) - (N + N^2 + ...) = I?$ On the other hand, $(I-N)(I + N ...
2
votes
1answer
444 views

If $P$ is a regular transition probability matrix then $P^{n^2}$ has no zero element

A transition probability matrix $P\in M_{n\times n}$ is regular if for some $k$ the matrix $P^k$ has all of its elements strictly positive. I read that this can be tested by using the following ...
2
votes
2answers
226 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
3answers
454 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
2answers
2k views

What values makes this Markov chain aperiodic?

Let the following transition matrix represent a $4$ state Markov chain $$\begin{pmatrix} 0 & a & 0 & b \\ \frac{1}{2} & 0 & \frac{1}{3}+c & d \\ 0 & a & 0 & ...
2
votes
1answer
64 views

Is every PMF on the set of non-negative integers the stationary distribution of some birth-death process?

Let $f(.)$ be a probability mass function on the non-negative integers such that $0<f(n)<1$ and $f(0)+f(1)+...=1$. Then does there exist an irreducible birth-death process with stationary ...
2
votes
2answers
149 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
323 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
127 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
54 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
554 views

example of irreductible transient markov chain

Can anyone give me a simple example of an irreductible (all elements communicate) and transient markov chain? I can't think of any such chain, yet it exists (but has to have an infinite number of ...
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. ...
2
votes
2answers
2k 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 ...
2
votes
1answer
451 views

Markov Process: Have you seen this notation and do you know what it means?

Ok, I've already posted this a minute ago, but my text deleted itself while I was editing it :-( So next try: Can you help me to understand the notation my professor uses to describe Markov ...
2
votes
1answer
477 views

Finite State Markov Chain Stationary Distribution

How does one show that any finite-state time homogenous Markov Chain has at least one stationary distribution in the sense of $\pi = \pi Q$ where $Q$ is the transition matrix and $\pi$ is the ...
2
votes
1answer
673 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
70 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
2answers
92 views

Equilibrium distribution of Ehrenfest's urn

(I'll post my own answer to this, but others may be of interest, so post your own if you have one.) (PS: In reply to comments posted below: Stackexchange encourages posting an answer to one's own ...
2
votes
2answers
48 views

finding the generating function $\phi(s) = \mathbb{E}(s^{H_0})$.

i just started the course of markov chains and i'm having a few problems with one of the excercises. Let $Y_1,Y_2, \dots$ be i.i.d random variables with: $\mathbb{P}(Y_1 = 1) = \mathbb{P}(Y_1 = -1) ...
2
votes
1answer
160 views

Probability of a substring occurring in a string

Consider a random string of length $n<\infty$ where each digit can be between 0-9 with equal probability and a substring of length $k<n$ consisting of only zeros. What is the probability of ...
2
votes
1answer
137 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
1answer
58 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
131 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
293 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
80 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
1answer
479 views

Is a Bernoulli process a Markov chain?

For a Bernoulli process, the outcome of a future trial is independent of the outcome of past trials. I.e., the future behaviour of a Bernoulli process is independent of its past, i.e. a Bernoulli ...
2
votes
2answers
106 views

Simple Symmetric Random Walk : $P_{00}^{2n}=\binom{2n}{n}\left(\dfrac{1}{2}\right)^{2n}$

I was studying Simple Symmetric Random Walks and my notes state (without proof) that $$P_{00}^{2n}=\binom{2n}{n}\left(\dfrac{1}{2}\right)^{2n}$$ That is the probability of going from $0$ to $0$ in ...
2
votes
1answer
87 views

Differences of consecutive hitting times

An interesting property of consecutive hitting times from Koralov&Sinai. Consider a homogeneous ergodic Markov chain on the finite state space $X = \left\{1,\ldots,\ r\right\}$. Define the random ...
2
votes
1answer
5k 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 ...
2
votes
1answer
199 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 = ...
2
votes
1answer
201 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
397 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
338 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
84 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? ...