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.
68
votes
8answers
20k 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
672 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 ...
13
votes
5answers
1k views
Good introductory book for Markov processes
Which is a good introductory book for Markov chains and Markov processes?
Thank you.
12
votes
1answer
260 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
585 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 ...
7
votes
2answers
784 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 ...
6
votes
4answers
1k 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. [...] ...
6
votes
2answers
168 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
1answer
99 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
162 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 ...
5
votes
2answers
127 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 ...
5
votes
2answers
360 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
2k 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
542 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 & & ...
5
votes
1answer
99 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
137 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
53 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
145 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
2answers
2k 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
...
4
votes
4answers
397 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 succesive days ...
4
votes
3answers
133 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
141 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
2answers
112 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
99 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
160 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
248 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
78 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
166 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
48 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
199 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
158 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 ...
4
votes
1answer
264 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
91 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
1answer
164 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 ...
4
votes
1answer
180 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
97 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 ...
4
votes
1answer
76 views
Behavior of explosive random process
Inspired somewhat by this problem, I've been investigating the behavior under iteration of the following discrete random process:
Given $n\in\mathbb{N}$, choose an integer from $\{0,1,\ldots,n\}$ ...
3
votes
3answers
383 views
Probability of absorption in a discrete Markov chain
Let $\{X_{n}\}$ be a Markov Chain on the state space $S=\{1,...,100\}$
with $X_{0}=30$, and transition probabilities given by $p_{1,1}=p_{100,100}=1$,
$p_{99,100}=p_{99,98}=1/2$ and for $2\leq ...
3
votes
1answer
248 views
Expected number of runs
Let $S[16]$ be a binary array i.e, elements of $S$ are 0/1 with elements $S[i]$ are taken uniformly and independently form $\{0,1\}$. Let $k$ be a random element taken uniformly from $\{0,1\}$. I have ...
3
votes
2answers
295 views
Irreducible and aperiodic Markov chain : $P^t(x,y)>0$
Consider a Markov chain $X$ with transition probability $P$ and finite state space $\Omega$.
Which of the following statement is true?
If $X$ is irreducible then $\exists t>0 \ni P^t(x,y)>0, ...
3
votes
2answers
137 views
Markov Chains and Linear Transformations
I just have a quick question about Markov Chain and linear algebra.
Background. Let $\{M_n: n= 0, 1, 2, \dots \}$ be a Markov Chain. We can represent the transition probabilities $_{n}Q^{(i,j)}$ in a ...
3
votes
2answers
271 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 ...
3
votes
4answers
68 views
Determining vector equations
Let $A\in \Bbb R^{n\times n}$ be a matrix such that $\mathrm{rank}(A) = n-1$ and consider the equation
$$
Ax = 0.
$$
Clearly, its solutions span a $1$-dimensional space, thus an additional ...
3
votes
1answer
192 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 ...
3
votes
2answers
252 views
How can I compare two Markov processes?
There is a discrete-time irreductible Markov process with $r$ possible states. $k$ observations were performed. At each observation a state of process was determined.
$T_0 = \lbrace 0,1,\dots ...
3
votes
2answers
60 views
What's the probability that A wins finally
Suppose A has \$2 and B has \$3. They play a game, each game gives the winner \$1 from other. A has a probability $\frac{3}{5}$ to win each game. They play this game until one of them is bankrupt. ...
3
votes
2answers
969 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 ...
3
votes
1answer
85 views
How to find the limit of a markov chain
Given a markov chain where the next state is related to the previous state by the following matrix:
$$\begin{array}{c|ccc} & A & B & C\\ \hline
A & p_1 & q_1 & r_1\\
B & ...
3
votes
1answer
254 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$.
...
3
votes
1answer
161 views
Conditional probability of a general Markov process given by its running process
I have a question as follow:
"Let $X$ be a general Markov process, $M$ is a running maximum process of $X$ and $T$ be an exponential distribution, independent of $X$.
I learned that there is the ...
