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

Example of a markov chain with transient and recurrent states

As the title says, I can't come up with an example of a markov chain with all possible states (transient, positive recurrent and null recurrent). I know that the state space must be infinite, ...
3
votes
1answer
22 views

Arguing a stationary distribution exists

I am trying to show that there exists a stationary distribution when $q>p$ for the Markov process with one-step transition matrix $$ \begin{bmatrix} q & p & 0 & 0 & ...
0
votes
1answer
26 views

why does $P(X_{n+m} = j| X_m = k, X_0 = i) = P(X_{n+m}= j|X_m = k)$ follows from the Markov Property

I've learned that the Markov property says the following: $$P(X_{n+1} = i|X_n = j, X_{n-1}= j_1,\dots, X_0 = j_n) = P(X_{n+1}= i| X_n = j)$$ For me it is not clear how you can derive the following ...
1
vote
2answers
36 views

Combining Markov chains

If the following Markov chain relations hold: $$X \rightarrow Y \rightarrow Z,$$ $$Z \rightarrow W \rightarrow Y,$$ can we combine them to have $$X \rightarrow Y \rightarrow Z \rightarrow W ...
2
votes
0answers
8 views

Likelihood that two markov chains are derived from the same transition matrix

Forgive me for my weak statistic background, hopefully what I'm asking makes sense. So some quick background, I have one markov chain from a data set and many additional chains that I'm producing from ...
0
votes
0answers
21 views

Proving that a process is not a Markov chain by using definition.

I want to prove that the queue length at a store is not a Discrete Parameter Markov Chain (DPMC). Now I have the equation: $$Q_k = (Q_{k-1} - 1) + V_k$$ $Q_k$ is the queue length at time instant ...
1
vote
0answers
18 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
22 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
42 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
18 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
56 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 & ...
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
30 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
24 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
2answers
43 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
35 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
71 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
58 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
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
50 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
63 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 ...