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

3
votes
1answer
22 views

Markov Chains - Strong Markov Property

I'm struck with an exercise. I tried, but the results don't seem to fit to those proposed. Exercise: Two players play the following game. The one who begins draws two cards from a deck of 40 cards ...
0
votes
1answer
20 views

Why do all steady state probabilities have the same denominator?

I have noted that the steady state probabilities of an irreducible Markov chain can be written as fractions that have the same denominator. Is there any result about this property? What does this ...
1
vote
1answer
304 views

Gradient-descent and Hidden Markov Models

I would like to use gradient-descent to fit the parameters of a simple 2-state HMM. This paper Levinson, S. E., Rabiner, L. R. and Sondhi, M. M. (1983), An Introduction to the Application of the ...
0
votes
0answers
16 views

Markov chain state reached earlier than other state

Consider a Markov chain with $S={1, 2, 3, 4}$ and transition Matrix: $P=\begin{bmatrix} 0 & 1/2 & 1/2 & 0 \\ 0 & 0 & 1/2 & 1/2 \\ 1/2 & 0 & 0 & 1/2 \\ 1/2 & ...
2
votes
1answer
458 views

Random walk, Cat and mouse

Here is the problem. In graph G, on different vertices there is cat and mouse. Cat and mouse do independent random walk, but time is synchronous, in one unit of time both cat and mouse do one step. ...
4
votes
0answers
34 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 ...
-1
votes
0answers
15 views

Renewal argument [on hold]

wBus is arriving at station and arrival interval Xi~iid Erlang(2,a) customers come to station as poison process, PP(b) when bus come to the station, all customers are taking the bus. Pn(t) is ...
0
votes
1answer
26 views

Transition matrix in Markov's chain

I'm trying to find the probability transition matrix in this Markov's chain problem. Three black and three white balls are distributed between two polls, in a way that each poll contains three balls. ...
2
votes
1answer
65 views

Expression for the quotient between two stationary states in a Markov process

I've been thinking about this problem and I would appreciate some help. Consider a finite number of states ($n$) Markov process with transition matrix $Q_{n\times n}$ with the usual properties and ...
2
votes
0answers
29 views

MLE for CTMC parameters

Let the data set be $$D = \{(s_0, t_0), (s_1, t_1), ..., (s_{N-1}, t_{N-1})\}$$ where $N=|D|$. Each $s_i$ is a state from the state space $S$ and during the time $[t_i,t_{i+1}]$ the chain is in state ...
-4
votes
2answers
35 views

Probability problem! please help [closed]

A soccer team wins 60% of its games when it scores the first goal, and 10% of its games when the opponent scores the first goal. If the team scores the first goal about 30% of the time, what is the ...
-3
votes
1answer
19 views

Probability help with meals and markov chains [closed]

Sam eats lunch at the campus center every Monday of the week. If he eats Pizza (P) this week, with probability 1/2 he eats Pizza again and with probability 1/2 eats Buritto (B) in the following week. ...
0
votes
0answers
14 views

model a system with finite users as a Markov Chain

I have to model a system M/M/2 with finite users (4 users) as a Markov Chain (and then find the probality an incoming users would enter the queue being the servers busy but that's not the problem). I ...
0
votes
0answers
5 views

Looking for resources on Harris recurrence

I'm working on a problem (in a not countable space) and it seems that I could get much further with it if I can prove that a certain Markov chain is Harris recurrent (I strongly suspect that it is). I ...
0
votes
1answer
35 views

Convergence of a particular fixed point iteration scheme

Setup I have the following non-linear system of equations: $$ \mathbf{x} P(\mathbf{x}) = 0 $$ where $\mathbf{x} \in \mathbb{R}_{>0}^n$ is a probability distribution, i.e., $\sum_i x_i = 1$, and ...
0
votes
0answers
12 views

How to understand this kind of Markov chain?

There are two unidirectionally coupled processes $X_t$ and $Y_t$. The coupling is $Y_t=g(X_{t-\delta},\dots)$. The Bayesian network of the two process is described in the following figure: Now this ...
0
votes
1answer
576 views

Expected state of a Markov chain

Let's start with a slightly trivial Markov chain defined as follows: the beginning state is called $1$ and the set of states is $\mathbb{N}$. At each step, when the current state is $n$, the ...
1
vote
2answers
39 views

Difficult to comprehend markov chain and its characteristics

If $Y_n$ is a sequence of independent random variables with $P(Y_n=0)=2/3,P(Y_n=1)=1/6,P(Y_n=2)=1/6$ and $X_n$ with $X_0=0$ is defined as $$X_{n+1}= \left\{ \begin{array}{lr} X_n-Y_n & : ...
0
votes
0answers
13 views

How does one estimate the order of a Markov chain empirically (given the data)?

I have a string of symbols $x_1, x_2, ...., x_n$, ($n$ very large), belonging to a finite alphabet. I know that they are a result of a Markov process, but I want to find out the order of the process. ...
0
votes
1answer
18 views

Solving for max () in Viterbi algorithm

In simple terms, what is the proper way to solve for max. I am working with the Viterbi algorithm and am now stuck on how to solve this part of the equation. pc(G,2) = 0.3 + ...
1
vote
0answers
26 views

Gibbs sampling truncation for contrastive divergence

I am following Yoshua Bengio's Learning Deep Architectures for AI and at page 31 there is a phrase that confuses me. Starting by lemma 7.1 in the same page: Lemma 7.1. Consider the Gibbs chain ...
1
vote
0answers
34 views

Maximum likelihood estimate of Gaussian parameters (1st-order Markov Chain)

Let us assume the availability of a time series $x_1, \ldots, x_N$ (where $x_i \in \mathbb{R}$, $0 \leq x_i \leq 1$). If we assume each variable to be independent of all previous observations except ...
-2
votes
0answers
15 views

Deriving busy channel probability through a markov chain model [closed]

Could anyone clarify to me how this probability (the busy channel probability in the second clear channel assessment) was derived in the paper "A Generalized Markov Chain Model for Effective Analysis ...
0
votes
1answer
55 views

Constructing a new Markov chain from another Markov chain

I have a very simple problem, but it seems I have difficulty to prove it rigorously. Suppose random variables $X, Y$ and $Z$ form the following Markov chain: $X\leftrightarrow Y\leftrightarrow Z$. My ...
1
vote
1answer
20 views

Determining the population size of a branching process

Suppose that I have the following branching process. Each parent can have up to two children, the number of which is determined by two independent fair coin flips. I know that this branching process ...
0
votes
1answer
21 views

Homogeneous Markov chains with general state space

I found in the book Markov Chains by Revuz the following definition of a Markov chain. In the following $(X_n)_{n \in \mathbb{N}}$ is a sequence of random variables on a probability space ...
0
votes
1answer
382 views

Renewal Processes for Uniform and exponential Distributions

Suppose the lifetime of a component $T_i$ in hours is uniformly distributed on $[100, 200]$. Components are replaced as soon as one fails and assume that this process has been going on long enough to ...
3
votes
1answer
26 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
11 views

HMM Scaling with Multiple Observations

for some background information on the topic please see the paper that I will largely be referencing for this question: http://www.cs.ubc.ca/~murphyk/Bayes/rabiner.pdf. Now to continue. I am ...
0
votes
2answers
32 views

Computing $\lim \limits_{n\to \infty}Pr(X_n=0)$ for r.v $X_n$ using matrices and Markov Chains.

There are three coins on the table showing "Heads". Every round, Danny comes and turns a coin upside down: the left one with probability of $1\over 2$, the middle with probability of $1\over 3$ and ...
0
votes
0answers
27 views

Finding the period in a Markov Chains related situation.

Let there be two vases with total 4 balls in them. At every step a ball is chosen with a uniform probability to every ball, and is put in the other vase. Let us consider the number of balls in vase ...
2
votes
1answer
23 views

Measuring incoming communication in a Markov Model

Given a standard Markov Chain on discrete time and finite statespace, represented by a matrix $M$, with $\sum_{j=1}^d m_{ij}=1$. I have a certain absorbing state k, where the incoming communication ...
0
votes
1answer
28 views

Markov Chain: Expected number of visit within certain time period

I am a student trying to learn more about probability,especially that of Markov Chain so I apologize if I maybe very inexperience on the topic. I am trying to get the expected number of visit a state ...
10
votes
1answer
349 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 ...
1
vote
1answer
34 views

Is this graph ergodic?

I had a long discussion with a friend of mine about if this simple graph is ergodic. I think it is because every state can be reached in an non-endless number of steps. My friend argues that it is not ...
0
votes
0answers
14 views

How do I parametrise a stochastic matrix?

I have a matrix $\mathbb{t}$ whereby $\sum\limits_j t_{ij} = 1$ and $\sum\limits_i t_{ij} x_i = q_j$ where $x_i$ are the elements of a discrete probability distribution, as are $q_j$, i.e. ...
1
vote
0answers
11 views

Inverse of Lumped Markov Process

Suppose we have an (ergodic, with dumping factor $\alpha$) Markov chain $P$ on a graph $G$, and we lump the transition matrix (it's a sort of reduction of the matrix using a equivalence relation of ...
1
vote
2answers
49 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
11 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
34 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 ...
4
votes
1answer
422 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 ...
-1
votes
2answers
28 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}, ...
1
vote
1answer
775 views

Long run probability of going to a state from another

We consider the following transition matrix for a markov chain with state space {A,B,C,D,E} : $P= \left( \begin{array}{ccccc} \frac{1}{2} & 0 & 0 &0 &\frac{1}{2} \\ 0 & ...
3
votes
1answer
298 views

Probability of being at a certain point after $N$ steps in Random Walk with a single absorbing barrier

A random walker in $1$ dimension starts walking from a point $k>0$ with an absorbing barrier at point $0$. What is the probability that he will reach a point $m>0$ in $N$ steps? How should I ...
0
votes
1answer
52 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
38 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
17 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
286 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 ...
1
vote
2answers
426 views

What is the difference between the forward and backward equations in a CTMC?

Given that the Forward equation in a CTMC (Continuous Time Markov Chain) is: $P'(t)=P_t G$, and the Backward equation is: $P'(t)=G P_t$, which equations should I use of the two depending on the case I ...