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

81
votes
9answers
22k 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. ...
23
votes
2answers
897 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 ...
16
votes
5answers
3k views

Good introductory book for Markov processes

Which is a good introductory book for Markov chains and Markov processes? Thank you.
14
votes
1answer
514 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
1answer
203 views

Can we qualitatively predict the strategy of the German and US teams in today's World Cup soccer match?

In today's World Cup soccer match between Germany and the US, both teams only need a draw to advance to the next round. There's been speculation about possible collusion, especially given the friendly ...
12
votes
3answers
657 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 ...
11
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 ...
9
votes
2answers
802 views

Expected number of turns for a rook to move to top right-most corner?

Suppose a rook starts on the lower left-most square of a standard $8 \times 8$ chess board. The board contains no other pieces. The rook randomly makes a legal chess move with every turn (directly ...
9
votes
1answer
294 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 ...
7
votes
5answers
4k 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
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 ...
7
votes
2answers
368 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 ...
6
votes
2answers
166 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
3answers
4k 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 ...
6
votes
1answer
1k 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
2answers
347 views

In a tournament $n$ players take part in a series of duels

I've recently been thinking about this problem and I think I solved it correctly. However, I was using a rather peculiar method with lots of algebra. I'll post my solution as an answer below. Is there ...
6
votes
1answer
111 views

Compute a probability in Random Walk by Martingales

Let $X_n$ be the state at time $n$ of a Markov chain with these transition probabilities : $$p_{i,i+1}=p_i\qquad,\qquad p_{i,i-1}=q_i=1-p_i$$ $(a)$ Show that $Z_n=g(X_n)\,;\,n\geq0$, is a ...
6
votes
1answer
164 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$. ...
6
votes
1answer
248 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 ...
6
votes
0answers
251 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). ...
5
votes
3answers
162 views

Expected value of number of draws

We have $5$ number in a bag: $(1,3,5,7,9)$. We draw one from the bag and then put it back. We do this until the sum of the numbers can be divided by $3$. Whats the expected value of the number of ...
5
votes
1answer
2k views

Markov process vs. markov chain vs. random process vs. stochastic process vs. collection of random variables

I'm trying to understand each of the above terms, and I'm having a lot of trouble deciphering the difference between them (note, my mathematics training isn't very strong - so please go easy on the ...
5
votes
2answers
661 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
1answer
115 views

How is the Chapman-Kolmogorov Equation not a fancy name for matrix multiplication?

The Chapman-Kolmogorov Equation: $$p^{m+n}(i,j)=\sum_kp^m(i,k)p^n(k,j)$$ Matrix Multiplication (with $[A]_{i,j}=a_{i,j}$ where $A$ is a linear map "" for B) $$[AB]_{i,j}=\sum_ka_{i,k}b_{k,j}$$ In ...
5
votes
1answer
122 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
116 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
2answers
3k 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 ...
5
votes
1answer
469 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
101 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
121 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, ...
5
votes
1answer
524 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
265 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
2answers
207 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
206 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
86 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 ...
4
votes
2answers
353 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
610 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
665 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
151 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
63 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
487 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
2answers
121 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
504 views

A.s. finite hitting time with an infinite mean

Let $X$ be a discrete-time Markov process on some measurable space $(\mathscr X,\mathscr B)$. Let $B\in\mathscr B$ and $$ \tau_B:=\inf\{n\geq 0:X_n\in B\} $$ is the first hitting time of $B$. ...
4
votes
1answer
36 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
1answer
81 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
474 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
136 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
191 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
1k 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
284 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 ...