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
1answer
507 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
689 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
71 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
100 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
49 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
205 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
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$ ...
2
votes
1answer
61 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
132 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
305 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
895 views

Forming the transition matrix for Markov chain, given a word description of transition probabilities

I have just started learning about Markov chain and have a trouble determining appropriate transition matrix: Suppose that whether or not it rains today depends on previous weather conditions ...
2
votes
2answers
84 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
514 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
1answer
157 views

Markov chain transition matrix

if $P$ and $Q$ are $n \times n$ transition matrices for two Markov chain, then product $R=PQ$ is also a transition matrix. is this true ? why is it ? looks like product of transition matrix means ...
2
votes
2answers
107 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
89 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
208 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
209 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
1answer
525 views

Show that two states in the same communicating class of a Markov chain must have the same period

How would you go about showing that two states in the same communicating class of a Markov chain must have the same period? Any help would be greatly appreciated.
2
votes
2answers
347 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
87 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
831 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
23 views

Markov chain - is my diagram/matrix correct?

A boy goes to school on a bike or on foot. If one day he goes on foot, then on the second day he takes a bike with probability $0.8$. If he goes on a bike one day, then he falls off the bike with ...
2
votes
1answer
62 views

Random walks : Hitting and recurrence Times relation

I have trouble understanding that how $$E\left[T_0|X_{0} = 0\right] = 1 + E[H_0|X_0=1] $$ where $T_0 = \inf\{n \geq 1:X_n = 0 \}$ and $H_A =\inf\{ n\geq 0: X_n \in A \}$. In other words $T_0$ is the ...
2
votes
2answers
118 views

Markov Chain: Moving on a circle

A particle moves on 12 points situated on a circle. At each step it is equally likely to move one step in the clockwise or in the counterclockwise direction. Find the mean number of steps for ...
2
votes
1answer
97 views

Finite state Markov chain

Under what conditions a Markov chain can be considered as finite (and not infinite)? Thank you!
2
votes
2answers
56 views

Verifying the Markov property

We throw a dice infinitely often. Define $U_n$ to be the maximal number shown up to time $n$. How can I verify that $$ ...
2
votes
1answer
165 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 ...
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 ...
2
votes
1answer
74 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
32 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
315 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
134 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
61 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
73 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
52 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
113 views

Probability problem with markov property

Problem: In a test paper, the questions are arranged so that 3/4's of the time a True is followed by a True and 2/3's of the time a False is followed by a False. You are confronted with a 100 ...
2
votes
1answer
318 views

Proof that Markov Chains converges to the stationary distribution

Let $P$ is a transition matrix of a Markov Chain, which is irreducible, aperiodic and lets assume $\pi$ is its stationary distribution: $\pi = \pi P$. Does anyone knows the proof for the following ...
2
votes
1answer
730 views

Expected time for winning in biased Gambler's Ruin

Consider the random walk $X_0, X_1, X_2, \ldots$ on state space $S=\{0,1,\ldots,n\}$ with absorbing states $A=\{0,n\}$, and with $P(i,i+1)=p$ and $P(i,i-1)=q$ for all $i \in S \setminus A$, where ...
2
votes
2answers
134 views

Continuous-time finite-state Markov chain as a subordinated Brownian motion

I think I read somewhere that every semimartingale is representable as a time changed Brownian motion (sorry, I don't have a reference). This suggests that in particular a continuous-time finite-state ...
2
votes
3answers
128 views

why is this Markov Chain aperiodic

I have this Matrix: $$P=\begin{pmatrix} 0 & 1 \\ 0.3 & 0.7 \end{pmatrix}$$ this markov chain is said to be aperiodic, I dont understand how it comes to it. Period $\delta$ is the gcd of ...
2
votes
1answer
234 views

Construction of positive recurrent Markov chain

Let $\{X_i\}_{i\geq 1}$ be i.i.d. with values in $\mathbb N_0$. Define a Markov chain via the following transition matrix: $$p(0,n) = \mathbb P(X_1 = n-1) \qquad p(m,n) = \mathbb P\left(\sum_{k=1}^m ...
2
votes
1answer
6k views

Steady-state and Equation System

Two questions: Given the transition matrix: $ \begin{vmatrix} \ 0.4 & 0.4 & 0.2 \\ \ 0.5 & 0.3 & 0.2 \\ \ 0.1 & 0.5 & 0.4 \end{vmatrix} $ I would like to know HOW to find ...
2
votes
1answer
93 views

Markov chain property

Suppose $\{Y_{n}, n \ge 0\}$ is a Markov chain consisting of $N$ states. Suppose that $i$ and $j$ are states of this Markov chain and that $i \hookrightarrow j$, i.e state $j$ can be reached from ...
2
votes
2answers
507 views

Finding the exact stationary distribution for a biased random walk on a bounded interval

Imagine we have a biased random walk on an interval $[0, L]$, where the probability of taking a $+1$ step is $p$ and the probability of taking a $-1$ step is $(1-p)$. At the reflecting boundary $0$, ...
2
votes
1answer
252 views

Random walk with 3 possible steps

I have i.i.d. random variables with following distribution: $$ P(\xi_i =1) = p_1, \ P(\xi_i = 0) = p_0, \ P(\xi_i = -1) = p_{-1}; \quad S_n = \sum^n_{i=1}\xi_i.$$ I am interested in probability of ...
2
votes
1answer
156 views

Markov Property

this relates to an unanswered question I posted a few days ago: Let $\{ X_t : t = 1, 2, 3 \dots \}$ follow a 2-state Markov chain with transition matrix P. Does the Markov property mean I can break ...
2
votes
1answer
101 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. ...
2
votes
1answer
109 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. ...
2
votes
1answer
575 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 ...