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
25 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
21 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 ...
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 & ...
-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 ...
-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. ...
-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 ...
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 ...
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 ...
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
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
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
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. ...
-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
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
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 ...
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 ...
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 ...
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
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 ...
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
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
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 ...
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 ...
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
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
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 ...
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 ...
-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
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 & : ...
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 ...
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 ...
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
49 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
22 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
1answer
61 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 ...
0
votes
0answers
26 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 ...
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
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 ...
0
votes
1answer
35 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, ...
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 ...
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
38 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
40 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
18 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
0answers
27 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. ...
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)$ ...
2
votes
1answer
53 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 ...