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
16 views

Alternate Markvov Chain Model.

In class we are working on DTMCs for past couple of week, and in our last lecture we did an example. Question was: In a city of nowhere it only rains if there are clouds for successive m-days. Any ...
1
vote
0answers
36 views

Expected number of steps for a random walk- robot

A robot is located at the top-left corner of a m x n grid The robot is trying to reach the bottom-right corner of the grid, he can move randomly in any of the directions: up, down, left, right. ...
1
vote
0answers
15 views

Irreducible finite-state Markov Chain

Could anyone help me with this? Let $X_n$ be an irreducible Markov chain on the state space $S=\{1,\ldots,N\}$. Show that there exist $C<\infty$ and $\rho <1$ such that for any states $i,j$, ...
1
vote
0answers
46 views

Wald's Identity for non-i.i.d. Case

I am looking for Wald's Identity for non-i.i.d. case as discussed in the following links: https://en.wikipedia.org/wiki/Wald%27s_equation What are the assumptions for applying Wald's equation ...
1
vote
0answers
33 views

A time reversible Markov chain problem on urns

Question: (Ross Probability Models, Ch. 4, Ex. 70) A total of $m$ white balls and $m$ black balls are distributed into two urns such that each urn contains $m$ balls. At each stage, a ball is selected ...
1
vote
0answers
30 views

The differences between the return times to a recurrent state of a discrete Markov chain are independent and identically distributed

Let $(\Omega,\mathcal A)$ be a measurable space and $\mathbb F=(\mathcal F_n)_{n\in\mathbb N_0}$ be a filtration on $(\Omega,\mathcal A)$ $E$ be an at most countable set equipped with the discrete ...
1
vote
0answers
56 views

Random walk evaluated by a Poisson process

I found the following proposition and I want to prove it. Let $S_n$ be a discrete-time random walk with increment distribution p and $N_t$ be a Poisson process with parameter $1$.Then the process ...
1
vote
0answers
31 views

An irreducible Markov chain is positive recurrent if and only if there is an invariant distribution

Let $E$ be an at most countable set equipped with the discrete topology $\mathcal E$ $X=(X_n)_{n\in\mathbb N_0}$ be a discrete Markov chain with values in $(E,\mathcal E)$, distributions ...
1
vote
0answers
24 views

Prove that $W_n := (X_n,Y_n)$ is a Markov chain and determine the transition probabilities.

Let $X_n$ be an irreducible, aperiodic, positive recurrent Markov chain $(\lambda,P)$ on a state space $I$, with stationary distribution $\pi$. Let $Y_n$ be Markov$(\pi,P)$, and independent of ...
1
vote
0answers
32 views

Probability Assessment of Interactive Markov Chain (IMC)

Firstly, consider a Markov chain in your mind. Probability of each state of the Markov chain can be obtained by following Chapman–Kolmogorov equation. $$ P(n\Delta t) = M^{n}P(0) $$ where P is the ...
1
vote
0answers
38 views

Blackwell's example in Markov process theory and Kolmogorov's extension theorem

I'm reading Continuous Time Markov Processes: An Introduction by Thomas M. Liggett. Chapter 2.4 is devoted to Blackwell's example. Let $E=\left\{0,1\right\}$, $\mathcal E:=2^E$ and $X$ be the ...
1
vote
0answers
29 views

Prove that uniform distribution on a set of vertices $V$ is stationary if the graph is regular.

I was going through Random walks on graphs: A survey It was stated that: Uniform distribution on a set of vertices $V$ is stationary if the graph is regular. Can anyone give me some hints to ...
1
vote
0answers
27 views

Convergence of autonomous system / time-scale separation

Let $x \in \Delta_n$, where $\Delta_n = \{u \in \mathbf{R}^n_{\ge 0} \mid \sum u_i = 1\}$ is the probability simplex. Suppose that I have an (autonomous) dynamical system $$ \dot{x} = A(x) \cdot x $$ ...
1
vote
0answers
46 views

Time reversible Markov chain

I have the following problem: A group of n processors is arranged in an ordered list. When a job arrives, the first processor in line attempts it; if it is unsuccessful, then the next in line tries ...
1
vote
0answers
25 views

A non-absorbing state of a discrete Markov chain is recurrent if and only if the Green's function explodes at this state

Let $E$ be an at most countable Polish space and $\mathcal E$ be the Borel $\sigma$-algebra on $E$ $X=(X_n)_{n\in\mathbb N_0}$ be a Markov chain with values $(E,\mathcal E)$, distributions ...
1
vote
0answers
63 views

Best way to compress a noisy observation

Say we have a discrete signal $X\in \mathcal{X}$, and a noisy observation $Y\in\mathcal{Y}$. We wish to encode $Y$ into some encoding $U$ with rate $R$. That is, $H(U)=R>0$. And we want $U$ to have ...
1
vote
0answers
36 views

Reversibility and stationary probability

Let $X_n$ a markov chain with transition matrix given by $$\begin{bmatrix}0.7&0.3&0\\0.2&0.7&0.1\\0.4&0.1&0.5\end{bmatrix}$$ i) Find the stationary probability ...
1
vote
0answers
17 views

Discuss the recurrence of such a Markov chain

$\{X_n:n\ge0\}$ is a Markov chain in $\{0,1,2,\ldots\}$ whose transition probability satisfy $p_{01}=1, p_{i,i+1}+p_{i,i-1}=1$ and $$ p_{i,i+1}=(\frac{i+1}{i})^\alpha p_{i,i-1}, ...
1
vote
0answers
19 views

Parameter Values From Asymmetric Probability Distributions

I am performing a Multipole Decomposition Analysis on some experimental data, essentially fitting a set of experimental data with a linear combination of functions. Annoyingly these functions are not ...
1
vote
0answers
73 views

Determining if a stochastic process is a markov chain

Let $\{X_t\}_{t \geq 0}$ be two-state Markov Chain with state space $S=\{0,1\}$, transition matrix $$ P= \begin{bmatrix} 1-p & p \\ q & 1-q \end{bmatrix} $$ and initial ...
1
vote
0answers
21 views

How to write spectral form of probability matrix

I am trying understand Markov chain in genetics process. In book that I am using (Mathematical Population Genetics) (pag 87): (P is matrix transition probability). $E_0$ and $E_M$ are absorbing ...
1
vote
0answers
38 views

Interpolation of random processes

Let $\left(\Omega, \mathcal{F}, \left\{\mathcal{F}_{t}\right\}_{t\geq 0}, P \right)$ be a complete probability space with a nondecreasing family of right continuous sub-$\sigma$-algebras ...
1
vote
0answers
57 views

Markov Chain- Internet Router Buffer

At each time slot, a router's buffer receives a packet with probability $p$, or releases one with probability $q$, or stays the same with $r$. Initially empty, what is the distribution of the packets ...
1
vote
0answers
61 views

Gibbs sampling for Hidden Markov Model

I want to understand how to derive the update formula for Gibbs sampling for Hidden Markov Model, for example, in here: $p(z_t | \mathbf{x}, \mathbf{z}_{\setminus t}, \boldsymbol{\alpha}, ...
1
vote
0answers
39 views

Transition density of an AR(1) process?

If we have an AR(1) process, i.e: $X_{t+1} = \alpha X_t + e_{t+1}$ with $X_0=0$ then what is its Markov Chain transition density? We know that for a Markov chain, the following holds: $P(X_{t+1}\leq ...
1
vote
0answers
35 views

Relaxation time and Mixing time of Markov chains

The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer. Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite ...
1
vote
0answers
43 views

Defining a function over time in terms of a random variable that is undefined at a certain time

Let $X_n$ be a random variable taking on one of three values $a,b$ or $c$ over time. That is, for each $n \in \mathbb{N}$, we have $X_n \in \{a,b,c\}$. Also, for each $n \in \mathbb{N}$, let $F_n$ be ...
1
vote
0answers
24 views

Markov-Chain Monte-Carlo: Are transformations on the inputs valid?

The problem: I am trying to solve a high dimensional (up to ~50) class of data fitting & modelling problems. The user specifies the problem, so I would like to make the configuration as easy as ...
1
vote
0answers
28 views

Determanistically skipping through time of a time homogeneous Markov chain

Suppose I have an infinite number of time steps $X_0,\ldots,X_i,\ldots$, where each $X_i$ is an infinite dimensional random vector consisting of 0's and 1's. I now specify $P(X_i|X_{(i-1)})$ and an ...
1
vote
0answers
213 views

From one-dimensional to two-dimensional Markov chains

I have a $M/M/1$ queueing system that is described below: There are two types of customers in the system with different arrival rates, $\lambda_{sg}$ and $\lambda_{sb}$. Service rate is $\mu$. Type ...
1
vote
0answers
65 views

Understanding the formula

Let $P$ the transition probability matrix and $\mu$ the row vector of initial distribution. $$P_\mu(X_n=j)=\sum_j\mu(i)p^n(i,j)=\mu p^n(j)$$ I don't want to make a proof of that, I want to ...
1
vote
0answers
23 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 ...
1
vote
0answers
34 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
48 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 ...
1
vote
0answers
16 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
0answers
41 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 ...
1
vote
0answers
29 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) - ...
1
vote
0answers
53 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 ...
1
vote
0answers
49 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
24 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 ...
1
vote
0answers
43 views

Compute the stationary distribution of a Markov Chain on an infinite state space

I have a Markov Chain on $\mathbb N_0^2$ with a given initial state $(x_0,y_0)$. The allowed transitions for example are of the following form: $(x,y) \mapsto (x-1,y+2)$ with probability $\propto x$ ...
1
vote
0answers
47 views

Finding the generating function of $H_{0}$ probability of hitting 0 in Markov Chain

Let $Y1 , Y2,...$ be independent identically distributed random variables with $\mathbb{P}(Y1 =1)=\mathbb{P}(Y1 =-1)=1/2$ and set $Xo=1,Xn =Xo+Y1+...+Yn$ for $n\geq1$. Define; $$H_o= inf\{n\geq0:Xn = ...
1
vote
0answers
32 views

Easy Question from Application: Estimate for transition probabilities of random walk - finding a coupling

SHORT VERSION: Find appropriate Coupling Suppose we have a random walk on the natural numbers, where we go to the left with probability $p_L \geq \frac{1}{6}$, to the right with probability $p_R\leq ...
1
vote
0answers
38 views

what's the potential application of low rank approximation of stochastic matrices

Suppose we have a stochastic matrix $P$ for a Markov chain, and we can compute a low rank approximation of $P$, say $P_k$, or we can find the nonnegative matrix factorization of $P$, i.e., $P=AW$ ...
1
vote
0answers
38 views

A 'mix' of simple and lazy simple random walk

Consider a $\mathbb{Z}$ valued markov chain $X_n$ which evolves as follows. $$P(X_{n+1}=y | X_n) =\begin{cases} \frac{1}{2}, y=X_n+1, X_n-1, |X_n|>K \\ \frac{1}{4}, y = X_n-1 , y= X_n+1, ...
1
vote
0answers
71 views

Understanding the strong Markov property

I have problems to understand the strong Markov property (Klenke, p. 356): Let $I \subset [0,\infty)$ be closed under addition. A Markov process $(X_t)_{t\in I}$ with distributions $(\mathbf{P}_x, ...
1
vote
0answers
88 views

markov process and markov chains

I have learned that Markov processes are stochastic processes possessing certain mathematical properties (memoryless, etc). My question is, if you say that a process is Markov, is it automatic (as a ...
1
vote
0answers
269 views

Sum of i.i.d. random variables is a markov chain

I think I have some problem understanding markov chains, because we defined them as abstract objects but our professor does proofs with them as if they where just elementary conditional probabilities. ...
1
vote
0answers
52 views

Distribution of continuous time markov chain

I'm having trouble understanding the question below. I understand the continuous time markov chain and unique stationary distribution but not sure what it is asking. I have a continuous-time Markov ...
1
vote
0answers
32 views

Merging rates on a CTMC model

first time question here. I'm having a rough time trying to represent the following CTMC. Any help would be gladly appreciated. We consider a server with a infinite buffer connected to a network. ...