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
132 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
480 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
104 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
148 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 ...
5
votes
1answer
450 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
185 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
749 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
48 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
152 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
293 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
389 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
41 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
59 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
37 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
84 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
153 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
295 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
107 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 ...
5
votes
0answers
93 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
797 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
1k 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
654 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
800 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
8k 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
155 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
429 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
5k 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
190 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
137 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
45 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
231 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
138 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
96 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 $ ...
4
votes
1answer
95 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
703 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
166 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, ...
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 ...
4
votes
1answer
70 views

Markov chain ergodicity

$(X_n)_n$ is a discrete-time, time-homogenous Markov chain. I have have the following transition matrix and want to show whether the chain is ergodic. $$P = \begin{pmatrix} \frac{1}{2} & 0 & ...
4
votes
1answer
121 views

$P^n$ transition matrix of a Markov chain

The setup: We have an unlimited supply of balls and $k$ boxes. In every step, we randomly (all of them have the same probability) choose a box and put a ball in it. Let $X_n$ be the number of ...
4
votes
1answer
306 views

Conditional return time of simple random walk

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$. Call $\tau_k = \min\{t \in \mathbb{N}\, : \, \, S_t =k \}$, the hitting time of $k \in \mathbb{N}$. Call $\tau^* = \min\{t ...
4
votes
1answer
371 views

A linear growth model with immigration

Ill give some background first before asking questions.(the text below is straight out of the book) Each individual in the population is assumed give birth at an exponential rate of $\lambda$ in ...
4
votes
3answers
769 views

What is the difference between the forward and backward equations in a CTMC?

Given that the Forward equation in a CTMC (Continuous Time Markov Chain) is: $P'(t)=P_t G$, and the Backward equation is: $P'(t)=G P_t$, which equations should I use of the two depending on the case I ...
4
votes
3answers
388 views

Given that $(X_n)_{n\geq 0}$ is a Markov Chain, prove that $(X_{kn})_{n\geq 0}$ is a Markov Chain

Given that $(X_n)_{n\geq 0}$ is a Markov Chain, prove that $(X_{kn})_{n\geq 0}$ is a Markov Chain. I don't know what this exercise has been so difficult for me, I've been playing around with the ...