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

0
votes
1answer
29 views

Show $\sum^n_{j=0} P_{ij} = \sum^n_{j=0} P(X_1 =j | X_0 = i) = 1 $

Let $P$ be the one step transition matrix of a Markov chain with states {$0,1,...,n$}. Show $\sum^n_{j=0} P_{ij} = \sum^n_{j=0} P(X_1 =j | X_0 = i) = 1 $ I understand that this is the row sum, but ...
0
votes
0answers
18 views

Changing the index of the sums when changing the sums - why this way?

Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with state space $E$. For $i,j\in E$ set $$ h_i(j):=\mathbb{P}_i(H(j)<\infty):=\mathbb{P}(H(j)<\infty|X_o=i), $$ where $H(j)\colon ...
2
votes
1answer
33 views

Adding distances/weights to absorbing markov chain

in presence of an absorbing state, I want to calculate mean/expected 'distance' from any state to that absorbing state. What I mean by distance is that I want to give different lengths from one ...
0
votes
0answers
22 views

expected value - last $k$ flips of coin are same

we flip a normal coin $n$ times. We mark $k=0.5log(n)$ and we mark the $i$'th value in $Xi$. $Y$ will be the number of times where the last $k$ flips were the same. What is $E[Y]$? I think this has ...
0
votes
0answers
28 views

Markov Chain - last $0.5log(n)$ Tosses of Coin

We toss a coin $n$ times and we mark $k=0.5log(n)$. $Y$ is the number of times where the last $k$ tosses were the same. What is $E(Y)$? I'm pretty sure I need to use Markov Chain but I'm not sure ...
4
votes
2answers
75 views

Expected value of money left from a coin flipping game

Say we were to play a game. We started off with \$100 and kept flipping a fair coin. If it turned out heads, we won \$1, else our money got inverted. For example, if on the first flip we got heads, ...
0
votes
0answers
66 views

Gibbs sampling from a 2D Gaussian

Hi I have the to do the next problem and I am kind of lost, if someone could give a litte hint of where to start I would really appreciate it. Thanks in advance! Suppose $x$~$ N(\mu;\sigma)$ where ...
2
votes
2answers
39 views

How can i interpret this absorbing markov chain to solve a probability question?

I try to solve a simple question; if I toss a coin and repeat it until a tails come up, what is the mean number of steps? (I want to solve another question but it is just a complicated version of ...
1
vote
0answers
30 views

Survival function of birth-death process

There is a linear birth-death process with $N$ states + an absorbing state $0$, with $$\Pr[X_{t+1}=0|X_{t}=0]=1, \\ \Pr[X_{t+1}=i+1|X_{t}=i]=\Pr[X_{t+1}=i-1|X_{t}=i]=q_i, i\in [1..N-1],$$ and ...
0
votes
1answer
61 views

Can you help me with this Markov Chain question?

The Problem: Prove that if the number of States in a Markov Chain is M, and that state j can be reached from state i, then it can be reached in M steps or less. The work: I assumed by contradiction ...
1
vote
0answers
19 views

No null recurrent state in finite state space from definition.

Let $\{X_n\}$ be a markov chain on finite state space $I$, with stationary transition probabilities. Let us denote $f^n(i,i):=P(X_n=i,X_{n-1}\neq i,\ldots X_1\neq i\mid X_0=i)$. We say $i$ is ...
1
vote
1answer
46 views

Forward Algorithm Hidden Markov Model matrix help [Discrete]!

So this may seem like a bioinformatics question but it is the math part that is giving me trouble. I'm using a Python package called YAHMM to model DNA sequences. I created a model with two states ...
1
vote
0answers
44 views

Markov chain in continuous time (transition probabilities)

Let $(X_t)_{t \geq 0}$ be a markov chain in continuous time with state space $\mathbb{N}_0$. I want to express $\mathbb{P}(X_t = 2| X_0 = 1, X_{3t} = 1)$ and $\mathbb{P}(X_t = 2 | X_0 = 1, X_{3t} = ...
6
votes
3answers
188 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 \\ ...
1
vote
2answers
21 views

How can I prove that $ p_{x,y}^{(n)}=P(X_n=y|X_0=x)$?

Let $(\Omega,\mathcal{A},P)$ a probability space. Let $E$ be a countable set and $\Bbb P:=(p_{x,y})_{x,y\in E}$ a stochastic matrix (i.e. $p_{x,y}\ge0$ and $\sum_{y\in E}p_{x,y}=1$) and $\mu$ a ...
2
votes
1answer
41 views

How do I show that this game played on a Markov chain has a unique Nash equilibrium?

There are $k$ stages in this game, and each stage is worth one unit of utility to a player (of which there are $n$). Each player $i$ finishes stages at a rate $\lambda_i$ (in a continuous time Markov ...
0
votes
1answer
38 views

Expected number of transition events to complete multiple synchronized Markov chains

Assume the expected number of transitions (events) it takes until a Markov chain with $G+1$ states ranging from $s=0$ to $s=G$ is completed is $M$. Suppose we have $K$ independent instances of this ...
1
vote
1answer
53 views

Markov Chain with heterogeneous transitions

I have a Markov chain as follows: $G+1$ finite states, it begins from $s=G$ and completes at $s=0$ A transition ($s\to s-1$) occurs in case if event $A$ happens. No other form of transition is ...
0
votes
0answers
42 views

Specifying transition probabilities for a Markov Chain

If I have a queueing model and I suppose at most a single customer arrives during a single period, but that the service time of a customer is a random variable Z with geometric probability ...
2
votes
1answer
157 views

The expected time until reaching a specified set in a Markov chain

I am reading an article in which they discuss a specific Markov chain in an example, and it turns out I need to sharpen up my Markov knowledge. First the setup. I have a continuous time Markov chain ...
0
votes
1answer
62 views

Urn Problem-Determining the Transition Probability Matrix

I have two urns A and B containing a total of N balls. An experiment is performed where a ball is selected at random (all selections equally likely) at time t(t=1,2,...) from the totality of N balls. ...
-1
votes
1answer
25 views

Limiting Distributions

Let P be the transition matrix $$ P = \begin{bmatrix} 0 & 0.2 & 0.2 & 0.2& 0.2 & 0.2 \\ 0.2 & 0 & 0.2 & 0.2 & 0.2 &0.2 \\ 0.2 & 0.2 & 0 & 0.2 & ...
0
votes
0answers
20 views

Why so complicated to show that $P_j(t(i)<\infty)=1$?

Let $(X_n)_{n\in\mathbb{N}_0}$ be an irreducible and recurrent Markov chain with state space $E$ and transition matrix $P$. For an $i\in E$ let $t(i)$ denote the random variable ...
0
votes
0answers
48 views

Define a maximization problem as an optimal stopping problem

We work over $\mathbb{R}_+^L$. Let $V$ be the set of vectors whose coordinates take values $0$ or $1$. Let $\mathbf{w}(t)$ (in $\mathbb{R}_+^L$) a vector that changes each time slot. To each vector ...
1
vote
1answer
45 views

Finding the transition probably matrix

If I have an urn that contains six tags, three are red and three are green. Two tags are selected from the urn. If one tag is red and the other is green, then the selected tags are discarded and two ...
0
votes
0answers
32 views

Identifying a Markov chain

This is a very basic question in the theory of Markov chains and I'm just not sure how to prove it mathematically. Say we have random variables $X, Y$ that are correlated and we have a possibly ...
2
votes
0answers
32 views

Define Markov chain and rewrite to recursively solve

Customers arrive at a server with rate $\lambda$ and are served at rate $\mu$. The server breaks down with rate $\gamma$, which causes all customers to leave. New customers can only arrive once the ...
2
votes
0answers
61 views

Model as a continuous time Markov Chain

A system consists of two machines, of which one works and the other is standby. Only the working machine can break down (with rate $\lambda$). If it breaks down the other machine takes over (if it ...
3
votes
2answers
50 views

Random walk on a tree

Consider a Cayley tree with coordination number 3 (http://en.wikipedia.org/wiki/Bethe_lattice). Consider two sites, $x$ and $y$, having a distance $k$ one from another. What is the probability that ...
1
vote
0answers
35 views

How to Simplify a Markov chain in order to estimate the average number of transitions to reach to a final state?

Is there any approach to approximate the expected number of transitions to complete a Markov chain without knowing the exact transition probabilities? The reason I ask this is because I want to ...
2
votes
0answers
23 views

Probability of going from a set $S$ to its complement on a Markov chain

I need to show that if $\pi$ is the stationary distribution of a Markov chain $M$, then for every set of vertices $S$, the probability to choose a random node in $S$ according to $\pi$ and then going ...
1
vote
0answers
19 views

Show that $p_{ii}^{(k+l)}\geqslant p_{ij}^{(k)}\cdot p_{ji}^{(\ell)}$

Let $(X_n)_{n\in\mathbb{N}_0}$ be an irreducible Markov chain with state space $E$ and Transition Matrix $P=(p_{ij})_{i,j\in E}$. Set $$ ...
0
votes
0answers
19 views

Is there any way to find probability of marcov chain when the time is same?

I am just wondering if I am given P(Xn=1 given that Xn=0) (Usual One Marcov chain) Can you find this probability using transition matrix?
0
votes
1answer
65 views

Markov Chain, finding the steady state vector

Suppose that if it is sunny today, there is a 60% chance that it will be sunny tomorrow, a 30% chance that it will be partly cloudy and a 10% chance that it will be completely cloudy. If it is partly ...
0
votes
1answer
27 views

Probability of getting disease and Markov chain

I am studying marcov chain. The question is . There are 5 people ( 4 diseased / 1 healthy) Two people are selected randomly and assumed to interact. If one is diseased and the other is healthy, ...
0
votes
0answers
13 views

How to estimate a hidden model for an unstationary Markov process?

I have a problem that is very similar to the one solved by the Baum–Welch algorithm. I have a process that is very similar to a hidden Markov process. The only difference is that I have an observable ...
0
votes
0answers
20 views

Null recurrence to positive recurrence in DTMC

What are some examples of null recurrent DTMC whose jump chain is positive recurrent? Specifically, for this null recurrent DTMC, removing self loops and normalizing the other outgoing edges from each ...
0
votes
0answers
35 views

recurrence/transience on random walk

Let $X_n$ be a markov chain, $p>\frac{1}{2}$ and $E=\{0,1,2,...\}$ its state space. Let $\Pi$ be its transition matrix with $\Pi(0,0)=p$, $\Pi(i+1,i)=p$, $\Pi(i,i+1)=1-p$ , $i\ge0$. ...
1
vote
1answer
33 views

Determining probabilities Markov Chain

If I have a Markov Chain $X_0, X_1, X_2 \dots$ that has a transition probability matrix $ \textbf{P} = \matrix{~ & 0 & 1 & 2 \cr 0 & 0.3 & 0.2 & 0.5 \cr ...
0
votes
1answer
25 views

Card shuffling transition matrix

a short understanding question. Consider a pile of $n$ cards. At every step we choose randomly 2 cards and transpose them. Now $X_n$ should be a Markov chain which describes the order of the pile at ...
1
vote
1answer
72 views

Determining a transition probability matrix

If I have that $X_n$ is a two-state Markov chain whose transition probability matrix is: $P = \left( \begin{smallmatrix} \alpha & 1-\alpha\\ 1-\beta & \beta \\\end{smallmatrix} \right)$ ...
-1
votes
1answer
54 views

Calculate expected value for a lazy Random Walk

Calculate the mean of time needed for a lazy random walk on $[0,n]$ which starts on $0<k<n$ to hit $0$ or $n$ if in each step the walk stays in probability $\frac 1 3$, goes to the right in ...
0
votes
1answer
141 views

Random Surfer as a Markov Chain

Consider a random surfer who begins at a web page (a node of the web graph) and executes a random walk on the Web as follows. At each time step, the surfer proceeds from his current page A to a ...
0
votes
2answers
89 views

In M/M/1 Markov process, why must entering and leaving the zero state be equal?

According to the image below, which I snipped from this article, the rate of leaving State 0 and the rate of arriving into ...
2
votes
0answers
42 views

An irreducible Markov chain is a martingale

Let $\{X_n\}$ be an irreducible Markov chain. Does exist example of such $\{X_n\}$ which is also a martingale given that: a. $\{X_n\}$ is recurrent with finite number of states (but bigger ...
0
votes
0answers
21 views

Reference on Discrete Markov Chains

I am essentially looking for reference books on Discrete Markov Chains. You can see our full syllabus here.
1
vote
1answer
35 views

How long does it take two identical hidden Markov models run on same observations to forget their initial distributions (if ever)?

Let $H_1$ and $H_2$ be two instances of a finite Hidden Markov Model (HMM) $H$. That is, $H_1$ and $H_2$ have identical state spaces $Q$ as well as identical transition $A$ and emission probabilities ...
1
vote
0answers
19 views

Calculate $P(X_{16}=2|X_0=0)$

Given a Markov Chain with three states 0,1,2 with the following State Transition Probabilites: $$M = \left( \begin{array}{ccc} 0.3 & 0.3 & 0.4 \\ 0.2 & 0.7 & 0.1 \\ 0.2 & 0.3 ...
0
votes
0answers
21 views

Show recurrence of a class

I am a little bit confused with the definition of recurrence with respect to Markov chains. For example consider the transition matrix $$ P=\frac{1}{2}\begin{pmatrix}0 & 1 & 1 & 0 & ...
1
vote
2answers
58 views

Expected first return time of Markov Chain

Given the following Markov Chain: $$M = \left( \begin{array}{cccccc} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 \\ \frac{1}{4} & \frac{3}{4} & 0 & 0 & 0 & 0 ...