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

5
votes
1answer
795 views

When the sum of independent Markov chains is a Markov chain?

I try to find as much as possible cases, when the chain $Z(t) = |X_1(t)-X_2(t)|$ is Markov, where $X_1(t)$ and $X_2(t)$ are independent, discrete-time and space, preferably non-homogeneous Markov ...
5
votes
1answer
181 views

recurrence criterion for random-walk like Markov chain

Suppose we have a random-walk like Markov chain, i.e. state space is the set of all integers from $-\infty$ to $\infty$, the transition probability $P_{ij}$ is nonzero only when $j=i+1$ or $j=i-1$. ...
5
votes
1answer
133 views

Log-likelihood function

I'm not sure if this could be asked here, or in math overflow... In the following paper Cho, Jin Seo, and Halbert White. "Testing for regime switching." Econometrica 75.6 (2007): 1671-1720. doi: ...
5
votes
1answer
1k views

Strong Markov property - Durrett

I recently had great success with my first question here so I will boldly go on to a second. Here goes: I'm studying Markov Chains in Rick Durrett - Probability: Theory and example and I'm stuck with ...
5
votes
3answers
502 views

From a deterministic discrete process to a Markov chain: conditions?

When will a probabilistic process obtained by an "abstraction" from a deterministic discrete process satisfy the Markov property? Example #1) Suppose we have some recurrence, e.g., $a_t=a^2_{t-1}$, $...
5
votes
1answer
111 views

Is a Markov process uniquely determined?

Let $E$ be a Polish space and $\mathcal E$ be the Borel $\sigma$-algebra on $E$ $I\subseteq[0,\infty)$ be closed under addition and $0\in I$ Please consider the following result: Let $(\...
5
votes
1answer
155 views

Question about Markov chain

We know that if $\{X_n\}$ is a Markov chain, then $X_{n+1}$ is independent with the past states $X_0,\ldots,X_{n-1}$ given current state $X_n$, that is $$P\{X_{n+1}=j|X_0=i_0,\ldots,X_n=i\}=P\{X_{n+1}=...
5
votes
1answer
470 views

Probability of being at a certain point after $N$ steps in Random Walk with a single absorbing barrier

A random walker in $1$ dimension starts walking from a point $k>0$ with an absorbing barrier at point $0$. What is the probability that he will reach a point $m>0$ in $N$ steps? How should I ...
5
votes
2answers
186 views

Prove that a random walk on $\mathbb{Z}_+\cup \{0\}$ is transient

Prove that a random walk on $\mathbb{Z}_+ \cup \{0\}$ is transient with $p_{i,i+1}=\frac{i^2+2i+1}{2i^2+2i+1}$ and $p_{i,i-1}=\frac{i^2}{2i^2+2i+1}$. So since this Markov chain has only a single ...
5
votes
1answer
784 views

Probability distribution for the position of a biased random walker on the positive integers

I initialize a biased one-dimensional random walk on the positive integers at the origin, $x = 0$, which also serves as a reflecting boundary blocking steps onto the negative integers. Let's say that ...
5
votes
1answer
82 views

Modified gambler's ruin problem: quit when going bankruptcy or losing $k$ dollars in all

In each round, the gambler either wins and earns 1 dollar, or loses 1 dollar. The winning probability in each round is $p<1/2$. The gambler initially has $a$ dollars. He quits the game when he has ...
5
votes
1answer
55 views

Branching Process: generation survival or extinction?

Let $p\in [0,1]$, and consider a branching process where the number of offspring of an individual is zero with probability $p$, and is two with probability $1-p$. Initially there is one ...
5
votes
1answer
157 views

Conditions for birth and death process having only finitely many deaths.

Consider a birth and death process on $\mathbb{N}=\left\{0,1,2,\ldots\right\}$, given by the transition probabilities $p(n,n+1)=\lambda_n$ and $p(n,n-1)=\mu_n$ (those are the birth and death rates, ...
5
votes
1answer
1k views

A question about how to get the limiting probability.

Suppose $p=\begin{bmatrix} 0& 1\over 3 &0 &2\over 3 \\ 0.3& 0& 0.7 &0 \\ 0& 2\over 3&0 &1\over3 \\ 0.8& 0& 0.2& 0 \end{bmatrix}$is the ...
5
votes
1answer
301 views

Does every continuous time minimal Markov chain have the Feller property?

Consider a Q-matrix on a countable state space. (A Q-matrix is a matrix whose rows sum up to $0$, with nonpositive finite diagonal entries and nonnegative off-diagonal entries.) As explained for ...
5
votes
1answer
404 views

Nested Expected Values

Assume we have random variables $X_1,\dots,X_N$ i.i.d. $\mathcal{U}\,(0,1)$ distributed and now define $Y_i$ as $$Y_i = f(Y_{i-1},X_i)\qquad \text{and}\qquad Y_0 \text{ arbitrary constant}$$ for some ...
5
votes
0answers
48 views

Poisson: Conditional Probability on Pizza order

I am not sure about my answer. In particular, part b of the following question. Pizza orders arrive according to a Poisson process of rate 20 per hour. Orders are independently for a vegetarian ...
5
votes
0answers
66 views

markov chain: 2 state chain

I have a machine. It has two states, broken or working. If it is working, then it will be broken with probability $q=0.1$. If the machine is working, I will make \$1000 dollar a day. If it is broken, ...
5
votes
0answers
39 views

Find a Markov chain transition kernel

Let $f_{X}$ be a density we would like to sample from. For some reasons, $f_{X}$ may be analytically intractable or expensive to evaluate. A solution consists in considering a density $(x,y) \in X \...
5
votes
0answers
91 views

Simplifying Chain of Conditional Variances given a Markov Chain

$\newcommand{\Var}{\operatorname{Var}}$Suppose $X,Y,W$ form a Markov chain $X \to Y \to W$. Can we simplify the following expression? \begin{align*} E [ \Var ( \Var (X\mid Y) \mid W)] \end{align*} ...
5
votes
0answers
165 views

Harmonic functions and null recurrence

Let $(X_n)_{n \geq 0}$ be a irreducible Markov chain defined on a countable state space $S$. It is known some ways to figure out if this chain is recurrent or not looking for superharmonic functions ...
5
votes
2answers
300 views

Generalization of the Jordan form for infinite matrices

Under what conditions is it the case that for a matrix $M$ whose rows and columns are indexed by a countably infinite set $S$ one has a Hamel basis consisting of generalized eigenvectors (i.e. $v \in \...
5
votes
0answers
115 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 $b,\...
5
votes
0answers
100 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 ...
4
votes
2answers
3k views

Transformation of state-space that preserves Markov property

I am solving a problem in Mathematical Statistics by Jun Shao Let $\{X_n \}$ be a Markov chain. Show that if $g$ is a one-to-one Borel function, then $\{g(X_n )\}$ is also a Markov chain. Give an ...
4
votes
2answers
3k 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 & ...
4
votes
2answers
846 views

Simple proof that stationary birth-death chains are reversible

A Markov chain with state space $\mathbb{Z}$ is a birth-death chain if the transition probabilities satisfy $p(x,y) = 0$ for $|x-y| > 1$. That is, the only possible transitions are to move one ...
4
votes
3answers
2k 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 ...
4
votes
2answers
696 views

How can a Markov chain be written as a measure-preserving dynamic system

From http://masi.cscs.lsa.umich.edu/~crshalizi/notabene/ergodic-theory.html irreducible Markov chains with finite state spaces are ergodic processes, since they have a unique invariant ...
4
votes
4answers
813 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 ...
4
votes
1answer
9k 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 ...
4
votes
3answers
156 views

Probability of finding 2012 before any other occurence of 012 in a random infinite sequence of digits 0,1,2

The following problem is from the semifinals of the Federation Francaise des Jeux Mathematiques: One draws randomly an infinite sequence with digits 0, 1 or 2. Afterwards, one reads it in the ...
4
votes
1answer
500 views

Are primitive row stochastic matrices diagonalizable?

Let $A$ be an $n \times n$ matrix with real, non-negative entries. Assume $A$ is primitive, meaning there exists an integer $k$ such that $A^k>0$ (here the inequality means all entries in $A$ are ...
4
votes
1answer
6k 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 ...
4
votes
1answer
51 views

What is the expected number of steps in a random walk from leaf to leaf in a full binary tree?

Let $h \geq 2$ be a natural number. Consider a complete binary tree of height $h$. Say we take a random walk starting from the "leftmost" leaf. What is the expected number of steps before the "...
4
votes
1answer
104 views

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 $ z=(z_0,...
4
votes
1answer
200 views

A die whose score cannot be as before (Markov chains)

A die is "fixed" so that each time it is rolled the score cannot be the same as the preceding score, all other scores having probability $1/5$. Given that the first score is 6, what is the probability ...
4
votes
2answers
145 views

When are stable continuous time Markov chains Feller? Always?

This is a question is similar to this 2 year-old one that never got answered (truthfully it's pretty much the same question except that I'm adding a bit more detail and the assumption that the $Q$ ...
4
votes
2answers
127 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 ...
4
votes
1answer
49 views

Stopping time in Markov chains

A random variable $T : \Omega \rightarrow ${$1,2,3...$} $\cup$ {$ \infty$} is called a stopping time if the event {$T=n$} depends only on $X_0 , X_1 ,X_2 ,..., X_n$ for $n = 0,1,2,...$ I have trouble ...
4
votes
1answer
120 views

Doubly stochastic matrix proof

A transition matrix $P$ is said to be doubly stochastic if the sum over each column equals one, that is $\sum_i P_{ij}=1\space\forall i$. If such a chain is irreducible and aperiodic and consists ...
4
votes
1answer
281 views

Find the Stationary Distribution of an infinite state Markov chain

A Markov Chain on states 0,1,..... has transition probabilities $P_{ij}=1/(i+2)$ for j=0,1,....,i,i+1. I'm supposed to find the stationary distribution. So do I take the limit as n goes to ...
4
votes
2answers
159 views

Expected value of money left from a coin flipping game

Say we were to play a game. We started off with \$100 and kept flipping a fair coin. If it turned out heads, we won \$1, else our money got inverted. For example, if on the first flip we got heads, ...
4
votes
1answer
98 views

random walk in a certain environment

Consider the following random walk in one dimension, starting from $r(0)=0$. $$ r(i+1) = r(i) + \xi, $$ where $\xi(i, r(i))$ is an increment with distribution $P(\xi=1) = \frac{c^{r(i)}}{i-r(i)+1}$ ...
4
votes
2answers
728 views

Random walk on lollipop graph

Hi i am trying to prove expected Hitting time on the Lollipop graph. It is a graph on $n$ vertices with clique on $n/2$ vertices and path joined to this. Let vertex $i$ be a vertex on the clique, ...
4
votes
1answer
1k views

Return time of a markov chain

I'm having trouble deriving the return time for a Markov chain. The graph has $n$ vertices and is connected by $n - 1$ edges. So we can draw this as a horizontal line of nodes with node $1$ all the ...
4
votes
1answer
174 views

Chance of being able to quit while ahead in a betting game (Markov chain with gambler's ruin)

Suppose a player starts with $N$ chips, and is playing a game with odds $O$, betting 1 chip in each iteration. When the player reaches 0 chips the betting must end. What is the probability that at ...
4
votes
1answer
196 views

Combinatory + Coding Theory

I am reading about an algorithm for finding minimum-weight words in large linear codes. Let $c$ be the codeword of weight $w$ to recover (with size $n$ and in $GF(2)$). Let $N = \left\{1, 2, \ldots, n\...
4
votes
2answers
2k views

First time passage decomposition for continuous time Markov chain

For discrete time finite Markov chain, the first passage time $T_j$ to visit state $j$, is determined from the recurrence equation: $$ p^{(n)}_{ij} = \sum_{k=0}^n f_{ij}^{(k)} p^{(n-k)}_{jj} = ...
4
votes
2answers
324 views

Stopping rules for Markov Chains

The following is a quote from Lifting Markov Chains to Speed up Mixing, by Chen, Lovasz, and Pak: ...Thus we have described a (randomized) stopping rule that, for any starting node, stops in an ...