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
1answer
92 views

spectral gap of the graph / Markov chain

Let $G=(V,E)$ be a graph. The gradient of a function $f:V\longrightarrow R$ is defined on the edges of the graph, given by the discrete derivative $$ \nabla f(e)=f(y)-f(x), \quad e=(x,y) \in E $$ ...
1
vote
1answer
152 views

Gradient of a function on the vertices of a graph

Let $G=(V,E)$ be a graph. The gradient of a function $f:V\longrightarrow R$ is defined on the edges of the graph, given by the discrete derivative $$ \nabla f(e)=f(y)-f(x), \quad e=(x,y) \in E $$ ...
1
vote
0answers
56 views

Markov chain supplementary litterature

I'm studying markov chains through Durrett and I'm finding it quite hard to read. Does anyone have a good idea to supplementary book, preferably one on his level of generality and which studies some ...
1
vote
0answers
49 views

How to sample the walk which visits each vertex of a graph specific number of times?

Is there any MCMC mathod that allow me to uniformly sample from all feasible walks where the following restrictions apply: ...
1
vote
0answers
101 views

Positive recurrence of a continuous-time jump process, from its jump chain

I am looking at an irreducible, continuous-time jump process $(X_t)_{t\geq0}$ with the following jump times. Let a Poisson process $(T_i)_{i=1}^\infty$ determine the event times. With probability $0&...
1
vote
0answers
202 views

Ergodicity and mixing

From MathOverflow, R W said: Unfortunately, the way the term "ergodic" is used in the theory of (finite) Markov chains is completely misleading from the point of view of general ergodic theory....
1
vote
0answers
201 views

Continuous-time Markov process - need help with flux and discrete-time equivalent

I have a continuous-time markov process and I need to calculate the following: transition frequencies matrix (aka intensity matrix) transition probabilities all parameters which define permanence ...
1
vote
0answers
127 views

Quasi-stationary distribution of a state in a birth-and-death MC

I need to find an expression for the first state in an MC with transition matrix $P$ with tridiagonal entries. The state space is $U={1,2,..n}$ with the last state being absorbing. Expressions for ...
1
vote
1answer
217 views

Can you fit a Markov chain transition matrix to a series of vectors?

Given a set of column vectors $v_1, v_2,...,v_t$ is there a way to calculate a unique transition matrix? In other words, is there one and only one matrix $A$ such that $Av_{i} = v_{i+1}$? ...
1
vote
0answers
174 views

Markov Chains - Using Gibbs & Metropolis algorithm.

Suppose $f_x,_y$ is bivariate normal distribution. I was given the parameters $(μ_1, μ_2, σ_1^2, σ_2^2)$ and $ρ=0.95$ the correlation coefficient. I want to generate $(x_1,y_1), (x_2,y_2)...,(x_n,y_n)$...
1
vote
0answers
30 views

How many observations is the minimum?

I want to estimate model transition matrix for a process (Markov chain). How much observiations of state do I need? I would prefer this as a function dependent on $n$, where $n$ is number of possible ...
1
vote
0answers
42 views

Integrating with respect to an MCMC Kernel

I'm currently trying to evaluate an integral with respect to an MCMC kernel, and I wanted someone else to read what I `proved' to see if it's really correct. It just doesn't feel right. Suppose I ...
1
vote
0answers
156 views

Cesaro mixing time: Show $t_m(2^{-k}) \le k t_m(1/4), k \ge 1$

Let $(X_t)_{t \ge 0}$ be a finite Markov chain with state space $\Omega$, transition matrix $P$ and stationary distribution $\pi$. Let $\| \cdot \|$ denote the total variation distance and define  $$...
1
vote
0answers
130 views

Irreducible Markov: harmonic function based on stationary distribution

Let $P$ be the transition matrix of an irreducible Markov chain on a finite state space $\Omega$. Let $\pi_1$ and $\pi_2$ be two stationary distributions for $P$. Is the function $$h(x)={\pi_1(x) \...
1
vote
0answers
123 views

Expectation of an event

Let $S[4]$ be a binary array with elements of $S$ are taken uniformly and independently from $\{0,1\}$. Also take $k$ uniformly from $\{0,1\}$. Take $i=1$. Now run the following process: Take $a,b$ ...
1
vote
2answers
25 views

A property of irreducible and aperiodic Markov chains

Let $P$ denote the $s\times s$ Markov transition matrix. We know that irreducibility and aperiodicity implies the following: There exists an integer $N\geq 1$, such that $[P^n]_{ij}>0$ for all $i,...
1
vote
1answer
52 views

Markov chains transition identity proof

Let $X = (X_{n})_{n \geq 0}$ a Markov chain proof that $$\mathbb{P}(X_{n + 2} = j \mid X_{n} = i) = \sum_{l \in \mathcal{S}} \mathbb{P}(X_{n + 2} = j, X_{n + 1} = l \mid X_{n} = i)$$ Note: $\mathcal{...
1
vote
1answer
74 views

period of product markov chain

Consider $Z_n := (X_n,Y_n)$ where $(X_n)_{n\in \mathbb{N}}$ and $(Y_n)_{n\in \mathbb{N}}$ are irreducible markov chains with periods $\lambda$ and $\mu$. We know that $(Z_n)_{n\in \mathbb{N}}$ is a ...
1
vote
1answer
301 views

Markov Chains as Autoregressive Processes

Is there a simple way to approximate a Markov Chain as an Autoregressive Process, for instance, an AR(1) process? I am aware that it is easy to approximate an AR(1) process with a Markov Chain, but I ...
0
votes
2answers
139 views

Expected number of steps to absorbtion - Markov chain

I want to calculate the expected number of steps (transitions) needed for absorbtion. So the transition probability matrix $P$ has exactly one (lets say it is the first one) column with a $1$ and the ...
0
votes
2answers
101 views

Probability of wearing a hat [closed]

A man has n hats that he keeps in two drawers. Every morning, he flips a (fair) coin to choose a drawer at random to take a hat from, if there is one. Every night, he flips a coin to choose which ...
0
votes
2answers
159 views

Using the canonical Markov property to prove an obvious fact about Markov chains [closed]

Given a Markov chain $\{X_n: n \geq 1 \}$, such that $$\mathbb{P}(X_{n+1} = x_{n+1} | X_n = x_n) = \mathbb{P}(X_{n+1} = x_{n+1} | X_n = x_n, \ldots X_1= x_1)$$ How can I formally prove that: $$\...
0
votes
3answers
623 views

Please give me a more thorough explanation: Computing the first return time for a Markov Chain

This is not a wikipedia question, because I cannot find it there. How does one compute the first return time of a time-homogeneous Markov chain. There are a lot of neat notions such as recurrence and ...
0
votes
3answers
71 views

markov chains and coin flips

A coin that comes up heads with probability p is continually flipped until the pattern T T T H appears. Let X denote the number of flips, find EX. If I use Markov chains is there a simpler way to ...
0
votes
1answer
41 views

Proof with stationary distribution

Let $\pi(k)$ the stationary distribution of the Markov Chain. Show that if $$p_{ij}^{(n)}\geq\varepsilon$$ for some $i,j,n,\varepsilon$ then $$\pi(j)\geq \varepsilon \pi(i)$$ I'm litle lost here ...
0
votes
1answer
47 views

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

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

Expected number of steps to traverse a graph

i have a graph adj(a)={b,e} adj(b)={a,c} adj(e)={a,d} adj(d)={e,c} adj(c)={b,d} at any vertex i can go it's adjacent vertex with probability 1/2. So what is the expected number of steps to reach 'c' ...
0
votes
3answers
160 views

Calculating probability in a Markov Chain

Suppose I have this Markov chain: And suppose that: $P_{AA} = 0.70$ $P_{AB} = 0.30$ $P_{BA} = 0.50$ $P_{BB} = 0.50$ I realize that $P_{AA} + P_{AB} = P_{BA} + P_{BB}$ but when I simulate I'm ...
0
votes
2answers
43 views

Different limiting distributions but they both satisfy same equations

I needed to find the limiting distribution of the matrix $$\pmatrix{ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0}$$ Instead of $\pi$ I'll use $A, B$ and $C$ ...
0
votes
2answers
7k views

When is a Markov chain null recurrent? [closed]

Are there any necessary and sufficient conditions for a Markov chain to be null recurrent? What about sufficient conditions? Naturally, I am not looking for tautological statements, e.g., a Markov ...
0
votes
2answers
158 views

Issue with calculating the cholesky decomposition

I am trying to calculate the cholesky decomposition of the matrix Q= ...
0
votes
3answers
110 views

Capacity of a discrete channel in the telegraphy case

I'm reading Shannon's article A Mathematical Theory of Communication, and I'm stuck at the telegraphy case example, on page 4. Shannon writes a formula involving $N(t)$, the number of sequences of ...
0
votes
2answers
292 views

Markov Chains with variable probabilities?

I'm asking a general question I think, but I couldn't find the answer myself. I have a system in which the next action depends on some variables, and those variables changes over time. At first I ...
0
votes
1answer
31 views

Equilibrium distribution exponentially fast

I need to prove that for an aperiodic, irreducible Markov Chain $X_n$ with stationary distribution $\pi$ holds that $P_x[X_n=j]\to\pi(j)$ exponentially fast. I found some proof of that statement but ...
0
votes
2answers
28 views

Show that this MC is ergodic?

Suppose I have a Markov Chain with States, $S = {1,2,3,4}$ and a PTM given by $P =$ $\begin{pmatrix} .25 & .25 & .25 & .25 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\\ 0 &...
0
votes
1answer
30 views

Finding Initial state vector with given values

I am not sure how to use a given values to form a initial state vector. There are 30% of customers from Company A switch to company B every month, and 35% customers from Company B switch to company A ...
0
votes
1answer
56 views

Finite-state Markov chain

Suppose $X_n$ is a Markov chain with transition probability matrix $p$ where the set of possible states is $S = \{1,2, \ldots, k\}$. If we are given, $X_1$, $X_2, \ldots, X_{2000}$, can we say about ...
0
votes
2answers
42 views

Expectation of stopping time on a random walk

Assume $X_1 , X_2 , \cdots$ are i.i.d. with distribution Bernouli$(\frac{1}{2})$, i.e., $P(X_i = 0)=P(X_i=1)=\frac{1}{2}$. Denote $S_0 := 0$, $S_n := \sum\limits_{i=1}^n X_i$, and $\tau_{1000} := inf\{...
0
votes
1answer
44 views

Markov Chain that isn't Irreducible

What is an example of a Markov chain that isn't irreducible but has a unique distribution, such that its distribution converges to that unique invariant distribution for any initial distribution.
0
votes
1answer
27 views

If I have a two-state Markov Chain, and I start a chain at state 1, and another at state 2, what is the expected time before they hit?

I have a two-state Markov Chain that looks like: $$ P= \left(\begin{matrix} 0.4 &0.6 \\ 0.7 & 0.3 \end{matrix} \right). $$ From this, suppose I define $X_t$ and $Y_t$, where $X_t$ starts ...
0
votes
1answer
104 views

Flea on a triangle

"A flea hops randomly on the vertices of a triangle with vertices labeled 1,2 and 3, hopping to each of the other vertices with equal probability. If the flea starts at vertex 1, find the probability ...
0
votes
2answers
72 views

Probability in a fixed die

I have that transition matrix is $$\begin{bmatrix}0&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}\\\frac{1}{5}&0&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&...
0
votes
1answer
44 views

Random walk on $\mathbb{Z}$ (probability to be again in the starting point after n steps)

Consider the random walk on $\mathbb{Z}$, where the probability of going one step to the right from any given state shall be $p\in (0,1)$. Starting in 0, what is the probability of returning to 0 in $...
0
votes
1answer
58 views

How to apply the strong Markov property in this case?

I'm trying to understand the following proof: Theorem: Let $(X_n)$ be an irreducible $(\alpha, \mathbf p)$-Markov chain with a finite state space $S$. Then $(X_n)$ is positive recurrent. ...
0
votes
1answer
41 views

A discrete time Markov chain with such a transient state that $\mathbb P(T_i<\infty \ | \ X_0=i) \neq 0$

All examples of discrete time Markov chains my text provides are where $S$ is finite, and as far as I can tell, it makes all transient states have $$\mathbb P(T_i<\infty \ | \ X_0=i) = 0.$$ Are ...
0
votes
2answers
54 views

Markov chain, successive running average

Here's my question: Take three numbers $x_1$, $x_2$, and $x_3$, and form the successive running averages $$x_n = \frac{x_{n-3} + x_{n-2} + x_{n-1}}{3}$$ starting with $x_4$. Prove that $$\lim_{n \to \...
0
votes
2answers
174 views

Calculate average time to empty the router

Consider a buffer, in which every second the number of packets increases by 1 with probability $.4$ and decreases by 1 with probability $.6$. Currently there are $n$ packets in the router. ...
0
votes
1answer
509 views

Markov chains - transition matrix - probabilty formula and application help?

Consider the $3\times3$ transition matrix $$ \begin{array}{c|ccc} &A &B &C \\ \hline A &0.2 & 0.3 &0.5\\ B &0.3 & 0.5 &0.2\\ C &0.3 & 0.3 & 0.4 \end{...
0
votes
2answers
632 views

Markov chain, Q matrix, jump matrix and invariant distribution

For the following Q matrix i want to find the jump matrix and the invariant distribution. \[ Q= \begin{pmatrix} -2 &1 &1 &0\\ 2 & -4 &1 &1\\ 1 &0 &-1 &0\...
0
votes
2answers
964 views

Branching Process Extinction Probability

I'm doing a branching process problem and am not sure I did it correctly. Suppose $X_0 = 1$ and $p_0 = .5, p_1 = .1,$ and $p_3 = .4$ represent the probabilities that zero, one, and three individuals ...