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
0answers
17 views

Fano's Inequality Proof

For an information theory class, I am studying the proof for Fano's inequality, i.e.: $H(P_e) + P_elog(|X|) \geq H(X|\hat{X}) \geq H(X|Y)$ Where $H(X)$ is the entropy ...
1
vote
1answer
26 views

Proving technique used to show an equivalence to the definition of a Markov process

Let $X=(X_t)_{t\in I}$ be Markov process with values in a Polish space $E$. I want to show, that there exists a stochastic kernel $\kappa:E\times\mathcal{B}(E)^{\otimes I}\to [0,1]$ such that ...
0
votes
0answers
20 views

Algorithm for identifying Markov chain communicating classes

Let $P$ be a transition matrix of a time-homogeneous Markov chain with at least one closed communication class. Is there an algorithm / optimization problem that outputs the identification of the ...
0
votes
1answer
41 views

Assume a die is rolled repeatedly. Find the markov matrix $P$ for the random variable of the time until the next $6$.

Assume a die is rolled repeatedly. Find the markov/transition matrix $P$ for the random variable $X_r$ = the time until the next six at time $r$. My solution was: For $i,j \geq 0$, $P$ is given ...
1
vote
0answers
19 views

Transient discrete time Markov chain on integers: can direction of flow be proven?

I'm not very familiar with the theory of Markov chains, and I'd like to learn how complicated the following problem actually is. Let there be a discrete time Markov chain on $\mathbb{Z}$, where the ...
0
votes
0answers
22 views

The difference in entropy rates between a hidden process and its observation

Let $S$ be a finite state space and $o:S\to S$ an observation function. Given a distribution $p$ on $S\times S$, consider the following optimization problem: $$\max \left[ EntropyRate(\{x_t\}) - ...
0
votes
0answers
19 views

Markov Chain with dependence between users

I am looking for a Markov Chain model that describes the following problem. I have $N$ indifferent users in the system, each of them has three states: $A$, $B$, $C$, and I know the transition ...
0
votes
0answers
16 views

Algorithm for getting Markov chain given the complex eigenvalues

Given real and complex eigenvalues (occurring in conjugate pairs) how to get a single instance of a Markov Chain which has these eigenvalues. I know the Markov chain is not unique as eigenvectors are ...
3
votes
2answers
55 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
26 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 [closed]

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
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
1answer
19 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
37 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. ...
0
votes
1answer
19 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
27 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
57 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
24 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
12 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
35 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
16 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
69 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
29 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
35 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
57 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
2answers
62 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
39 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
39 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 ...