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

79
votes
9answers
21k views

How often does it happen that the oldest person alive dies?

Today, we are brought the sad news that Europe's oldest woman died. A little over a week ago the oldest person in the U.S. unfortunately died. Yesterday, the Netherlands' oldest man died peacefully. ...
22
votes
2answers
799 views

Drunkard's walk on the $n^{th}$ roots of unity.

Fix an integer $n\geq 2$. Suppose we start at the origin in the complex plane, and on each step we choose an $n^{th}$ root of unity at random, and go $1$ unit distance in that direction. Let ...
14
votes
5answers
2k views

Good introductory book for Markov processes

Which is a good introductory book for Markov chains and Markov processes? Thank you.
13
votes
1answer
399 views

Eigenvalues for $3\times 3$ stochastic matrices

This is a plot of the non-real eigenvalues of 10000 randomly generated $3\times3$ stochastic matrices. It's pretty clear that they lie in the convex hull of the three cube roots of unity. The ...
12
votes
3answers
622 views

A rigorous proof of an obvious fact about a Markov chain

So I'm having trouble writing down a rigorous proof of something that seems very clear. Consider the following Markov chain on a ring: with probability $1/2$, it stays where it is, with probability ...
8
votes
2answers
2k views

Nice references on Markov chains/processes?

I am currently learning about Markov chains and Markov processes, as part of my study on stochastic processes. I feel there are so many properties about Markov chain, but the book that I have makes ...
7
votes
4answers
3k views

Example of a stochastic process which does not have the Markov property

According to this definition, A stochastic process has the Markov property if the conditional probability distribution of future states of the process depends only upon the present state. [...] ...
7
votes
2answers
278 views

“Small sets” in Markov chains

I came across a definition for a "small set" (of the state space) $A \subset \Omega$: there exists a $\delta > 0$ and a measure $\mu$ such that $p^{(k)}(x, \cdot) \geq \delta \mu (\cdot)$ for every ...
7
votes
1answer
255 views

What happens to a random walk when we increase the probabilities of going right?

Consider a random walk on the integers where the probability of transitioning from $n$ to $n+1$ is $p_n$ (and of course, the probability of transitioning from $n$ to $n-1$ is $1-p_n$); we assume all ...
6
votes
2answers
155 views

What does it mean to observe a Markov Chain after a certain kind of transition?

I'm working on a problem concerning censoring of transitions in a Markov Chain. For example, take a Markov Chain that models a counter, it goes up or down but does not stay in position. A possible ...
6
votes
1answer
957 views

Stationary distribution of random walk

Let $\mathcal{X}$ be a simple random walk with barrier at zero, state space $E = \mathbb{N}_0$ and transition matrix below with $0<q<1$. \begin{bmatrix} 1-q & q & & ...
6
votes
1answer
146 views

Markov chain stochastic process

Can anyone help me with this question, maybe by giving a hint. Consider a Markov chain with state space $\{0,1,2....\}$. A sequence of positive numbers $p_1,p_2,...$ is given with $\sum p_i=1$. ...
5
votes
2answers
3k views

Equilibrium distributions of Markov Chains

I often get confused about when a Markov chain has an equilibrium distribution; when this equilibrium distribution is unique; which starting states converge to the equilibrium distribution; and ...
5
votes
2answers
527 views

Gambler's ruin (calculating probabilities--hitting time)

Im meant to produce the transition matrix which I've already done (in the picture) and list the communication classes. But Im not sure how to find the probability regarding the hitting times (see ...
5
votes
3answers
3k views

What is the difference between all types of Markov Chains?

I have been looking for some good material covering Markov Chains but everything seems so difficult to me... After reading about the subject, I figured out that there is basically three kinds of ...
5
votes
1answer
94 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
111 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
326 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
366 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
213 views

Markov chain $(X_n)$ has $X_n \rightarrow \infty$ a.s

I have the following homework problem: Let $(X_n)_{n \geq 0}$ be a Markov chain on the state space $\lbrace0,1,...\rbrace$. Writing $p_i := p_{i,i+1}$ and $q_i := p_{i,i-1}$, the transition ...
5
votes
1answer
200 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
75 views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N ...
5
votes
0answers
77 views

Confusion in the proof of properties for $\psi$-irreducibility

Let $P$ be a stochastic kernel on a measurable space $(\mathsf X,\mathfrak B(\mathsf X))$. The kernel $P$ is called $\varphi$-irreducible if for a positive measure $\varphi$ and for all measurable ...
5
votes
0answers
207 views

Potential theory: discrete-time Markov processes

Recently I've found lecture notes on "Analysis on Graphs" where the potential theory methods were used to study discrete-time, time-reversible Markov chains (i.e. the state space is countable). ...
4
votes
4answers
528 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
3answers
377 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
3answers
147 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
405 views

Markov chains- recurrence and transience

This is an exercise in Durrett's probability book. $p$ is the transition probability for a markov chain on a countable space. $f$ is said to be superharmonic if $f(x)\geq\sum_y p(x,y)f(y)$, or ...
4
votes
1answer
3k views

Kendall notation's “General distribution”, what does that mean?

The first and second parameters for the Kendall's notation may have a G value, which stands for General distribution, see here. But what does that mean? What is a ...
4
votes
2answers
116 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
76 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
361 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
120 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
176 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

Is ergodic markov chain both irreducible and aperiodic or just irreducible?

As I find some definition says: Ergodic = irreducible. And then Irreducible + aperiodic + positive gives Regular Markov chain. A Markov chain is called an ergodic chain if it is possible to go ...
4
votes
2answers
896 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
269 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
2answers
114 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 ...
4
votes
1answer
330 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
3answers
273 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}$, ...
4
votes
1answer
47 views

Joint Probability from Marginal Probabilities

$X, Y_1, Y_2$ are random variables with (possibly) different finite alphabets. For given conditional probability mass functions $\mathbb{P}(Y_1|X)$ and $\mathbb{P}(Y_2|X)$, is it always possible to ...
4
votes
2answers
106 views

The problem of the drunkard in a valley.

We consider a Markov chain on a subset of positive integers $S =$ {$0, 1, 2, 3, .......N$}, with transition probabilities defined as follows: The chain jumps only one unit to the left or right. ...
4
votes
2answers
2k views

Why Markov matrices always have 1 as an eigenvalue

Also called stochastic matrix. Let $A=[a_{ij}]$ - matrix over $\mathbb{R}$ $0\le a_{ij} \le 1 \forall i,j$ $\sum_{j}a_{ij}=1 \forall i$ i.e the sum along each column of $A$ is 1. I ...
4
votes
1answer
278 views

question involving Markov chain

Let $S_{2m}$ be the group of all permutations $\pi$ of $\{1, 2, \ldots, 2m\}$. The following transition kernel $S$ generates the random transposition walk $$ Ch(\pi, \pi')= \begin{cases} \frac{1}{2m} ...
4
votes
1answer
196 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 offdiagonal entries). As explained for ...
4
votes
1answer
105 views

random walk along edges of tetrahedron — which face gets hit last?

Suppose we have a tetrahedron $abcd$, and start at edge $ab$. Now walk to any "adjacent" edge (i.e. in this case any edge other than $cd$), each with equal probability $1/4$. This gives a stationary ...
4
votes
0answers
60 views

Spectral gap of mixture of Markov chains

Context Let $P$ be the transition matrix of an irreducible, aperiodic, discrete-time Markov chain. The spectral gap is given by $$\xi = 1 - \lambda_\max$$ where $\lambda_\max = \max\{\lambda_2, ...
4
votes
0answers
121 views

Conditional probability and integrating out part of a random walk

Suppose that I have a random walk process defined by $\alpha_{t+1}$ ~ N$(\alpha_t, \omega^2)$. Given $\alpha_t$ and $\alpha_{t+2}$, I understand why the conditional formula for ...
4
votes
1answer
184 views

Lower bound for multivariate recurrence

I have a recurrence that looks like $$p(i,j,k) = \frac{j}{n}p(i-1,j-1,k-1) + \frac{i-j}{n}p(i-1,j,k-1)$$ $$p(i,0,k) = 1$$ $$p(i,j,0) = 0$$ $$p(0,j,k) = 0$$ The base cases are to be considered in ...
4
votes
0answers
161 views

estimation of transition probabilities from aggregate data

Please, O mathematicians, help me understand the approach to the problem of estimating transition probabilities given only aggregate data in Kalbfleisch & Lawless' 1984 paper "Least-Squares ...