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

92
votes
6answers
24k 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. ...
26
votes
5answers
2k views

When the product of dice rolls yields a square

Succinct Question: Suppose you roll a fair six-sided die $n$ times. What is the probability that the product of the rolls is a square? Context: I used this as one question in a course for ...
26
votes
2answers
1k 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 ...
20
votes
5answers
5k views

Good introductory book for Markov processes

Which is a good introductory book for Markov chains and Markov processes? Thank you.
16
votes
1answer
698 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 ...
16
votes
2answers
5k 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 ...
15
votes
2answers
738 views

Knight returning to corner on chessboard — average number of steps

Context: My friend gave me a problem at breakfast some time ago. It is supposed to have an easy, trick-involving solution. I can't figure it out. Problem: Let there be a knight (horse) at a ...
14
votes
1answer
343 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 ...
14
votes
1answer
414 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 ...
13
votes
1answer
5k 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 ...
12
votes
3answers
699 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
1answer
139 views

Can there be a Diaconis-Shahshahani Upper Bound Lemma for Compact Groups?

Let $G$ be a finite group and $\nu\in M_p(G)\subset \mathbb{C} G$ a probability measure on $G$ and let $\pi$ be the uniform distribution on $G$. Denote by $d_\rho$ the dimension of a non-trivial ...
10
votes
2answers
1k 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 ...
10
votes
2answers
7k 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 ...
10
votes
1answer
205 views

Stochastic kernel as linear operator

Let $K$ be a stochastic kernel for a set $S$ equipped with a countably generated $\sigma$-Algebra $B(S)$, i.e. $K:S\times B(S)\rightarrow [0,1]$ such that $K(\cdot,A)$ is a measurable function for ...
9
votes
6answers
7k 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. [...] ...
9
votes
2answers
582 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 ...
8
votes
2answers
174 views

$L^2$ Bounds for Markov Chains.

Consider a non-negative, square stochastic $n \times n$ matrix $P$ (rows sum to one, $P$ is ergodic). We are interested in characterizing the set of $n \times n$ invertible matrices $A$ such that we ...
7
votes
2answers
205 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 ...
7
votes
2answers
4k 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
1answer
102 views

If $A$ is the generator of $(P_t)$, then $A+f$ is the generator of $(P_t^f)$

Let $X=(X_t)_{t\geq0}$ be a Markov process on a state space $\Gamma$ (a Hausdorff topological vector space), let $A$ be the infinitesimal generator of $X$ and let $\mathcal C(\Gamma)$ the space of ...
7
votes
1answer
121 views

What are some modern books on Markov Chains with plenty of good exercises?

I would like to know what books people currently like in Markov Chains (with syllabus comprising discrete MC, stationary distributions, etc.), that contain many good exercises. Some such book on ...
7
votes
1answer
197 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 ...
7
votes
1answer
241 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$. ...
7
votes
1answer
213 views

Analytic Center of Convex Polytope

I have a convex polytope defined by $Ax \leq b$. I want to know how to find the "analytic center" of my convex polytope, because my goal is to sample from the polytope using Monte-Carlo Markov ...
7
votes
0answers
64 views

Can Continuous Time Markov Chains be used as a reasonable voting system?

I just compared a couple of example elections, as given on Wikipedia to show how Condorcet-methods differ from non-Condorcet ones, to what happens if you just interpret the underlying preference ...
7
votes
0answers
523 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 ...
7
votes
1answer
667 views

Intuition on Harris recurrence

I am trying to get some intuition on Harris recurrence in Markov chains. Define state space $\mathcal S$ comprising a single communication class, $f_{ii}^{(n)}=P(X_n=i, X_{n-1}\ne i,\ldots X_1\ne ...
6
votes
4answers
314 views

Probability of going into an absorbing state

If I have a random walk Markov chain whose transition probability matrix is given by $$ \mathbf{P} = \matrix{~ & 0 & 1 & 2 & 3 \\ 0 & 1 & 0 & 0 & 0 \\ ...
6
votes
4answers
9k 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 ...
6
votes
3answers
7k 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
2answers
605 views

Interpretation for the determinant of a stochastic matrix?

Is there a probabilistic interpretation for the determinant of a stochastic matrix (i.e. an $n \times n$ matrix whose columns sum to unity)?
6
votes
1answer
267 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 ...
6
votes
1answer
900 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$. ...
6
votes
1answer
2k 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
401 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
333 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, ...
6
votes
1answer
347 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
1answer
81 views

Martingale converges to the boundary

I asked an almost same question before and it is solved by considering adjacent $Z_n$ can not be far away and obtain a contradiction. However, if the setting is altered a bit, I wonder whether it is ...
6
votes
1answer
106 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 ...
6
votes
0answers
328 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
207 views

A recursive formula to approximate $e$. Prove or disprove.

Let the sequence $\{x_n, n=1,2,...\}$ be defined as follows: Let $x_2=x_1=1$ and for $n>2$ let $$x_{n+1}=x_n-\frac{1}{n}x_{n-1}.$$ This sequence, generated by the recursion above, tends to zero ...
5
votes
3answers
6k views

1D random walk-probability to go back to origin

Suppose There is a random walk starting in origin while probability to move right is 1/3 and probability to move left 2/3.What is the probability to return to the origin. Thank you
5
votes
3answers
272 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
2answers
1k 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
2answers
771 views

Markov chain with uncountable state space

I'm self-studying probability theory and struggling with understanding Markov chains on uncountable state spaces, notably I would like to solve the following exercise from this book. ...
5
votes
1answer
1k 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 ...
5
votes
1answer
7k 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 ...
5
votes
1answer
727 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$. ...