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

1
vote
2answers
56 views

Entropy of a Markov chain (right result?)

Consider the Markov chain with state space $E=\left\{0,1,2,3,4,5,6\right\}$ and transition matrix $$ \begin{pmatrix}1/5 & 3/5 & 0 & 0 & 1/5 & 0 & 0\\0 & 0 & ...
0
votes
0answers
17 views

Ergodicity property for continuous-time Harris positive Markov process

The following theorem is Theorem 13.3.3 of Meyn and Tweedie's Markov Chains and Stochastic Stability on page 328 Theorem 13.3.3. If $\Phi$ is positive Harris and aperiodic, then for every initial ...
1
vote
0answers
36 views

Time homogeneous Markov chain with random times

A continuous time homogeneous Markov chain $X_t$ over a finite state space $\{ 1, \dots, n \}$ satisfies the property $$P(X(s+t) = j \mid X(t) = i) = P(X(s) = j \mid X(0) = i).$$ If $S$ and $T$ are ...
-1
votes
2answers
32 views

Markov chain and conditional entropy [closed]

Markov chain (DTMC) is described by transition matrix: $$\textbf{P} = \begin{pmatrix}0 & 1\\ \frac{1}{2} & \frac{1}{2} \end{pmatrix}.$$ Initial distribution $X_1 = \left(\frac{1}{4}, ...
0
votes
1answer
61 views

Markov chain: join states in Transition Matrix

I need to merge two states in the Transition Matrix: For example: I have the matrix below ...
2
votes
1answer
41 views

Expectation of hitting time of a markov chain

Let $\{X_n\}$ be a homogenous Markov chain, taking values in N. $T_i:=\inf\{k\ge0:X_k=i\}$ is the first time when the chain arrives at i. I know that if X is irreducible positive recurrent, then ...
1
vote
0answers
36 views

Markov chain: join states in Transition Matrix [duplicate]

I need to merge two states in the Transition Matrix: For example: I have the matrix below ...
1
vote
0answers
18 views

Exponentially fast decay of alpha-mixing rates for irreducible, aperiodic finite, Markov chains

Let $(X_n)_{n \in \mathbb N}$ be a stationary, aperiodic, irreducible, finite state space Markov chain. Define the $\alpha$-mixing coefficient as: $$\alpha(n) = \sup \{\vert \Pr(A \cap B) - ...
4
votes
1answer
290 views

Derivative of conditional expectation

Let $\left( {{X_t}:t \in \left[ 0 \right.\left. {, + \infty } \right\rangle } \right)$ be a continuous time Markov chain on a probability space $\left( {\Omega ,\mathcal{F},\mathbb{P}} \right)$ with a ...
8
votes
5answers
5k 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. [...] ...
4
votes
1answer
54 views

Simple random walk: What is the probability that the hitting time is exactly 2n?

I refer to the random walk $(S_n)_{n \geq 1}$ where $S_n = X_1 + \cdots + X_n$ and $X_i$ are i.i.d random variables taking values $\pm 1$ with equal probability. I want to know how to show that ...
2
votes
1answer
23 views

Markov chain - is my diagram/matrix correct?

A boy goes to school on a bike or on foot. If one day he goes on foot, then on the second day he takes a bike with probability $0.8$. If he goes on a bike one day, then he falls off the bike with ...
0
votes
2answers
67 views

Filtration of Markov Chains in general state space

I am reading the book Markov Chains and Stochastic Stability from Meyn and Tweedie. They define Markov chains on a measurable state space $(E,\Sigma)$ (Chapter 3.4) and they define it on the space ...
1
vote
0answers
51 views

Ski Lift - Expectation Value

The following is an exercise from my textbook. Let $Y$ be a random variable with values in $\mathbb{N}_0$ and $Y_1, Y_2, \dots$ be independent copies of $Y$. Further let $X$ be a markov chain with ...
89
votes
6answers
23k 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. ...
0
votes
0answers
27 views

Probability to stay above n

I have an infinite discrete Markov chain $M=(\mathbb{N},P)$ where $$P(n,m)=\sum_{i=0}^{min(m,n)} {n\choose i}(1-\lambda)^i\lambda^{n-i}\mu^{m-i}(1-\mu)$$ My question: If I'm in state $m$ what is the ...
1
vote
3answers
51 views

Markov chain: I don't understand how read this matrix

Consider a gambling game in which on any turn you win \$1 with the probability $p=0.4$ and you loose \$1 with the probability $p=0.4$. We have that $p(i,j)=p\{X_{n+1}=j\mid X_n=i\}$ and thus, for ...
0
votes
1answer
37 views

Markov chain: Sunny or raining?

Suppose that the probability that it rain today is $p=0.3$ if neither of the last two days was rainy, but $0.6$ if at least one of the last two days was rainy. Let the wether at the $n^{th}$ day, ...
2
votes
0answers
29 views

Consequence of random walk with positive speed on a graph

Consider a random walk $X(n)$ on a vertex-transitive graph where the random walk has positive speed, i.e., $$ \lim\limits_{n \rightarrow \infty} \frac{d(X(n), X(0))}{n}= \alpha>0$$ almost surely. ...
0
votes
1answer
47 views

Escape probabilities in a random walk.

So, a lot of theory in symmetric random walks seems to concentrate on 'hitting/stopping times' and things like that. So I started wondering... How would I go about calculating the probability of ...
1
vote
0answers
41 views

Hidden Markov Model Transition Probability

I am doing my assignment and I am asked to derive transition probability of a HMM. There are Three states. H, E and T. They initially gave me the information as follow. E is followed by an H 40% ...
1
vote
0answers
19 views

Mixing time of three particle systems

Is there anything known about mixing time of Markov chains for three particle systems? It is proved here that the mixing time of an exclusion process is $\operatorname{O}(n)$. We can think if a ...
2
votes
1answer
58 views

Using a markov chain to calculate the expected value of conditional/constrained choices (TopCoder PancakeStack)

I've been working on a programming challenge (link) where an expected value is calculated. Recently I learned about Markov chains and successfully applied them to solving a set of problems, but the ...
1
vote
1answer
14 views

Interperetation of tau in marokov chains

I'd like to ask you a question about the meaning of certain equation in my exercise. This concerns Markov Chains I have: $\tau =inf\{n>=1:X_n\in\{3,5\}\}$ and I have to calculate $P(\tau=1)$ ...
1
vote
1answer
76 views

Long term probability in Markov Chains

I was practicing some questions on transition probability matrices and I came up with this question. You have 3 coins: A (Heads probability 0.2),B (Heads probability 0.4), C (Heads probability ...
1
vote
2answers
36 views

Transition probability matrix

In the article here it had this question. A walker moves on two positions a and b. She begins at a at time 0, and is at a next time as well. Subsequently, if she is at the same position for two ...
1
vote
0answers
32 views

Compute the stationary distribution of a Markov Chain on an infinite state space

I have a Markov Chain on $\mathbb N_0^2$ with a given initial state $(x_0,y_0)$. The allowed transitions for example are of the following form: $(x,y) \mapsto (x-1,y+2)$ with probability $\propto x$ ...
0
votes
1answer
15 views

Probabilities in markov chain

I have problem with calculating the probability of Markov Chain with 3 states S = {0,1,2}. I need to calculate $P(X_1=1,X_2=1|X_0=2)$. In the answers to my workbook I am given solution: ...
0
votes
0answers
48 views

markov process and markov chains

I have learned that Markov processes are stochastic processes possessing certain mathematical properties (memoryless, etc). My question is, if you say that a process is Markov, is it automatic (as a ...
0
votes
0answers
19 views

Obtaining the transition probability matrix

Seven black balls are distributed among two persons $A$ and $B$ having urns $X_A $ and $X_B$ with three balls in $X_A$ and four in $X_B$. One white ball is in either $X_A $ or $X_B$. A game consists ...
0
votes
1answer
20 views

Aperiodicity in irreducible markov chains

I am stuck at aperiodic property of irreducible markov chain. Let us consider an irreducible markov chain. It's stated herein that for an irreducible markov chain, a single aperiodic state implies ...
2
votes
1answer
47 views

Markov Chain Detailed Balance property

I am having a hard time to understand the concept of the detailed balance; mostly because of the intermingled notation most of the resources use; which involves constant usage of random and state ...
0
votes
0answers
31 views

Question concerning invariant distribution

Let us consider the Markov chain $(X_n)_{n \in \mathbb{N}}$ with state space $I = \{0,1\}^m$ and transition probabilities $$ p_{xy} = \begin{cases} m^{-1} &\mbox{if } \vert x - y \vert = 1 \\ 0 ...
2
votes
0answers
33 views

Branching Process in simple random walk

Suppose we have a simple random walk on $\mathbb{Z}$ which stars at $1$, i.e. we have iid increment $X_n$ valued in $+1,-1$ with probability $\frac{1}{2}$ each and the sum $S_n=\sum_{i=1}^{n}X_n+S_0$ ...
0
votes
2answers
38 views

Determing a transition probability matrix

I need some support with this homework exercise: An urn contains at most $N$ balls. Let $X_n$ be the number of balls in the urn after the $n$-th execution of the following procedure: If the urn is not ...
0
votes
0answers
24 views

Is it true that $\tilde{P} = D^{\dagger} P D$ has non-negative entries?

Consider a $n \times n$ stochastic matrix $P$ (i.e. non-negative rows sum to one). We are interested in the matrix $\tilde{P} = D^{\dagger} P D$, where $D$ is a $n \times k$ matrix which is ...
0
votes
0answers
42 views

How to recompute the markov transition matrix given a reduction to the number of states? Clustering from a transistion matrix

I am been puzzled with this one for sometime. Given a transition matrix (as below) for a markov chain of N states; how do we calculate the transition matrix for N-1 states, where we combined stat n1 ...
-1
votes
1answer
39 views

Markov chain period

Let a Markov chain with State space $E=\{1,2,3,4\}$ and probability transition matrix: $$P=\begin{bmatrix} 0 & 1 & 0 & 0 \\ 1/4 & 0 & 1/4 & 1/2\\0 & 1& 0 & 0 \\ ...
1
vote
0answers
29 views

Finding the generating function of $H_{0}$ probability of hitting 0 in Markov Chain

Let $Y1 , Y2,...$ be independent identically distributed random variables with $\mathbb{P}(Y1 =1)=\mathbb{P}(Y1 =-1)=1/2$ and set $Xo=1,Xn =Xo+Y1+...+Yn$ for $n\geq1$. Define; $$H_o= inf\{n\geq0:Xn = ...
1
vote
1answer
43 views

What is the probability of arrive either A or B at starting point K?

There are two points which are $A$ and $B$. The distance between $A$ and $B$ is $50$ meter. One person goes to $A$ with probability $\frac{1}{6}$, he goes to $B$ with probability $\frac{3}{6}$. And he ...
5
votes
4answers
5k 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 ...
1
vote
0answers
25 views

Easy Question from Application: Estimate for transition probabilities of random walk - finding a coupling

SHORT VERSION: Find appropriate Coupling Suppose we have a random walk on the natural numbers, where we go to the left with probability $p_L \geq \frac{1}{6}$, to the right with probability $p_R\leq ...
1
vote
0answers
23 views

what's the potential application of low rank approximation of stochastic matrices

Suppose we have a stochastic matrix $P$ for a Markov chain, and we can compute a low rank approximation of $P$, say $P_k$, or we can find the nonnegative matrix factorization of $P$, i.e., $P=AW$ ...
3
votes
1answer
34 views

Generating Constrained Random Distributions

I am trying to help another StackExchange user. We are attempting to fill a 6x6 matrix with 12 A's, 12 B's, and 12 C's subject to the constraint that each row contains 2 A, 2B and 2 C and each column ...
0
votes
1answer
72 views

Can You Help Me With This Continuous Markov Chain Question?

Consider 2 machines, both of which have an exponential lifetime with mean $\frac{1}{\lambda}$. There is a single repairman that can service machines at an exponential rate $\mu$. Set up the ...
2
votes
0answers
53 views

A(nother) variation of the coupon collector's problem

I have come across variation of the coupon collector's problem that goes like this. The coupons are of $n$ different types and in infinite number (or sampled with replacement after each draw, where ...
2
votes
0answers
45 views

Markov chain monte carlo

The target is to simulate a discrete random variable $Z$ with mass function satisfying $\mathbb{P}(Z=i)\propto \pi_i$, for $i\in S$ and $S$ countable. Let $X$ be an irreducible Markov chain with ...
1
vote
0answers
34 views

A 'mix' of simple and lazy simple random walk

Consider a $\mathbb{Z}$ valued markov chain $X_n$ which evolves as follows. $$P(X_{n+1}=y | X_n) =\begin{cases} \frac{1}{2}, y=X_n+1, X_n-1, |X_n|>K \\ \frac{1}{4}, y = X_n-1 , y= X_n+1, ...
3
votes
1answer
109 views

Frog on infinitely many lily pads (Markov chain)

A frog on pad $i$ hops to one of the pads $(1,2,...,i,i+1)$ with equal probability. I know that if the frog starts on pad $k$ the expected number of times the frog jumps, before returning for the ...
2
votes
0answers
50 views

Convergence of a Markov Chain to the normal distribution

If $i$ is a state of an irreducible, postive recurrent Markov chain $X$, and $V_n$ is the number of visits to $i$ between times $1$ and $n$, and further $\mu=\mathbb{E}_i(T_i)$ and ...