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
68 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
45 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
93 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
53 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
42 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
127 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
220 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
74 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
357 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
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 ...
2
votes
1answer
180 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
182 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
313 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
302 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
81 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
727 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
2answers
44 views

Limiting probability that the sum of the values of a die is a multiple of 13

A fair die is thrown repeatedly. Let $X_n$ denote the sum of the $n$ first throws. I have to find $\lim_{n\rightarrow \infty}P(X_n \text{ is multiple of 13})$. Now follows what I tried, which I don't ...
2
votes
2answers
22 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
2answers
46 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
2answers
28 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
32 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
30 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
140 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
88 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
46 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
62 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
49 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
264 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 ...
2
votes
1answer
89 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
179 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
450 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
108 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
115 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
184 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
2answers
352 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
200 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
137 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
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. ...
2
votes
1answer
102 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
507 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 ...
2
votes
2answers
190 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? ...
2
votes
1answer
464 views

Expected time of mouse's survival (stochastic matrix)

In the following wikipedia page explaining stochastic matrices, there is an example with 5 boxes and a cat and a mouse where they jump to a left or right box at every turn and it explains how to ...
2
votes
2answers
648 views

Proof of Markov property for Ehrenfest urn

[the question got downvoted on MO with the recommendation to ask here] In many books Ehrenfest Urn is used as an example of a homogeneous Markov chain, where entries in transition probabilities ...
2
votes
2answers
441 views

Markov Chain: Pensioner Problem

A pensioner receives 2000 dollars at the beginning of each month. The amount of money he needs to spend during a month is independent of the amount he has and is equal to i (i.e. i thousand dollars) ...
2
votes
1answer
78 views

Invariance on the product space

Let us consider two spaces $\mathbb{X},\mathbb{Y}$. For simplicity we put $\mathbb{X} = \mathbb{Y} = \mathbb{R}$. On the product space $\mathbb{S} = \mathbb{X}\times \mathbb{Y}$ we consider a Markov ...
2
votes
1answer
40 views
+50

Applying MCMC Metropolis algorithm

I'm interested in all possible paths (on the grid $\mathbb{N}^2 $) that goes from $ (0,0) $ to $ (n, n) $. At each step there are two possibilities: go right or go up. The path is a sequence $ ...
2
votes
1answer
40 views

Prove matrix is positive semi-definite

$P$ is a stochastic matrix (square, non-negative, rows sum to 1). $\Xi$ is a diagonal matrix with a left principal eigenvector of $P$ on the diagonal and zeros elsewhere (stationary distribution if ...
2
votes
1answer
23 views

Why can a Markov chain having two states and no self-loop have a stationary distribution?

Why does a Markov chain having two states and no self-loop can have a stationary distribution? Lets consider a markov chain with two nodes = $\{A, B\}$ and the transition matrix: $P = ...
2
votes
1answer
67 views

A Markov Chain Flea Problem

A Flea moves around the vertices of a triangle in the following manner: Whenever it is at vertex i it moves to its clockwise neighbor vertex with probability $p_i$ and to the counterclockwise neighbor ...
2
votes
1answer
75 views

Counterexample for $\| (\Phi^\top \Xi \Phi)^\dagger \Phi^\top \Xi P \Phi \|_2 \leq 1$

All matrices are real. Let $P$ be any stochastic matrix (i.e. square, non-negative, rows summing to one). Let $\Xi$ be a diagonal matrix containing on its diagonal any left eigenvector of $P$ ...