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

Harris Chain and Stationary Distribution

Consider a Harris chain given by $\{X_n\}$ with the following transition function, $X_{n+1}=\max \{0,X_n-b\} $ with probability $p$ and $X_{n+1}=\max \{0,a-\tau\} $ with probability $1-p$, where $\tau ...
1
vote
0answers
10 views

How to determine the transition probability in Sequential Importance Sampling (SIS) for Particle Filter

Given a state-space model \begin{align} x_k &= f_k(x_{k-1}, v_{k-1}),\\ z_k &= h_k(x_k, w_k), \end{align} where $x_k \in {\mathbb R}^{n}$ and $y_k \in {\mathbb R}^{m}$ are the system state ...
1
vote
0answers
30 views

Variation on the classic ABRACADABRA problem

Suppose letters are chosen randomly from the alphabet, one at a time. It is well known that the expected time until ABRACADABRA is spelled out is $26^{11}+26^{4}+26$. The proof uses discrete time ...
1
vote
0answers
23 views

How is the following attitude true?(Markov chains)

Let us have an $X_n$ Markov-chain with finite $S$ set as domain. $A \subset S$ is given, so that $P_x(T_A < \infty) > 0$ for all $x \in S$. $T_A=\inf \{ n \geq 1: X_n \in A\}$. Then we take a ...
1
vote
0answers
26 views

Transform Markov chain that doesn't have stationary transition probabilities to one that does?

This question concerns Exercise 7.3 in Walsh's Knowing the Odds. A Markov chain is defined as having stationary transition probabilities if for all $i, j, n$ we have $P(X_{n+1} = j \mid X_n=i) = ...
1
vote
0answers
18 views

Two Markov chains $X_t$, $Y_t$ have the same transition matrix $P$, show $\Bbb P(\tau_c\le t_0) = \Bbb P(\tau_c\le 2t_0|\tau_c> t_0)$

Given two Markov chains $X_t$, $Y_t$ characterized by the same transition matrix $P$, let $\tau_c$ be the first time the two chains have the same state, i.e. $\tau_c = \min\{t:X_t=Y_t\}$. The ...
1
vote
0answers
19 views

Is this the same thing as some simple discrete probability distribution?

I want to count the number of trials until one success in a sequence where the success probability is increased with each failure. For each trial, the success probability is ...
1
vote
0answers
40 views

Normalisation of an invariant measure

Is there an example of a Markov chain with invariant measure $\pi$ and $\sum_{i \in I}\pi(i) = \infty$ that can be normalised so that we can consider an invariant distribution instead? This is a ...
1
vote
0answers
28 views

Probability that sample path ends at a high.

I am trying to get the probability that a sample path ends at a high. To formulate the problem, let sequence $\{S_n\}$ be a random walk, with $S_0 = 0$, defined by $$ S_n = \sum_{k=1}^n X_k$$ Where ...
1
vote
0answers
14 views

marginalised markov chain

If there is a Markov chain for the joint variable $z=(x,y)$, the marginal process $x$ is not, in general, Markovian itself. However, if we consider the probability of a two time step process ...
1
vote
0answers
40 views

What is the invariance principle of Random Walks?

Several papers I have read allude to the fact that a random walk is invariant; however, I have been unable to find any reference to support this fact. Could anyone explain why random walks are ...
1
vote
0answers
42 views

Finite irreducible Markov chain

The question I have is stated as follows: Show that for any finite-state irreducible Markov chain $$\max_{i,j}\mathbb E_iT_j\le C$$where the constant $C$ only depends on the number of states and ...
1
vote
0answers
78 views

Deduce the definition of a harmonic function in the context of a Markov Chain

We know from PDE that a harmonic function $f$ satisfies the mean value property, namely, $f(x)$ = $\frac{1}{\vert{B_r(x)}\vert}\int_{B_r(x)}f(y)dy$ where $B_r(x)$ is the ball about $x$ with radius ...
1
vote
0answers
28 views

Irreducible and positive recurrent CTMC — first passage times are finite?

Consider a continuous-time Markov chain (CTMC) $X$ on a countably infinite state space $S$. The CTMC is irreducible and all the states are positive recurrent. Let $T(i,j)$ be the first passage time to ...
1
vote
0answers
13 views

Rigorous Derivation of Metropolis-Hastings Transition Density

The Metropolis-Hastings MCMC algorithm is as follows. Set $X_0$ to some initial value in the support of the target density $f$ and choose a proposal density $q(y \mid x)$; a density in $y$ for each ...
1
vote
0answers
31 views

The “how many pieces do you have buy on average” problem, a markov problem?

I recently discovered a problem similar to this one in a book about Markov chains: Assume you can buy $n-$ different set of cards in a store, but you do not know which one you'll buy: What is the ...
1
vote
0answers
43 views

Identity for return times in continuous Markov chain

I need help with this problem about return times in continuous time Markov chains: We are given a continuous time Markov chain $(X_t)$. Define $T_i=\inf{\{t>0; X_t=i, X_{t-} \neq i\}}$, which ...
1
vote
0answers
33 views

An example of Markov chain with no closed class?

What is an example of Markov chain with no closed communicating class? Closed class means that once we are in that class, there would be no escape from it. I am thinking that an example would be ...
1
vote
0answers
18 views

recurrence time for transient state

I have the following transition matrix for a MC with state space $S = \{ 1,2,3,4,5,6,7,8 \}$ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.4 ...
1
vote
0answers
48 views

Eigenvectors of Approximations to Infinite Stochastic Matrices

Given a function $[0,1]\to[0,1]\times[0,1]$ on the reals, such that the function is "stochastic" (probably an abuse of vocabulary: defined such that integrating along any vertical line gives $1$), ...
1
vote
0answers
59 views

Does a Markov process have memory zero?

I have the following question: The Markov process with two states and a transition matrix $$P =\begin{pmatrix} 0.3 & 0.7 \\ 0.3 & 0.7 \end{pmatrix}$$ has memory zero. Is it true? My ...
1
vote
0answers
31 views

Simple random walk on the $N$-cycle

I am considering the following example: In my lecture notes we noted that "the functions $(\phi_j)_j$ form a basis". I think they refer to the space $\mathbb{C}^G$ where $G$ is the above ...
1
vote
0answers
39 views

Markov chain of transition probabilities

Let $P$ be a transition matrix on a discrete state space with $N$ elements. $P_{i,j}$ is the probability of going from state $i$ to state $j$. Let $\pi$ be the stationary distribution. Let $\{X_n\}$ ...
1
vote
0answers
43 views

Birth-Death process with shifted exponential distribution

In the general framework of $M/M/1$ queue we have rate $\lambda$ and an exponential service time $\mu$, we can set up the transition rate matrix intuitively. However, if the service times satisfy ...
1
vote
0answers
24 views

Understanding a Markov decision process

We have an insect that is resting on a vertex of a square at each point of time $t=0,1,2..$. The vertices are labelled from 1 to 4. 1 is given to the lower left vertex, 3 to the upper left vertex, ...
1
vote
0answers
54 views

Finding a stationary distribution for a Markov chain with a binomially distributed transition matrix

The distribution isn't exactly binomial.. I'll explain what I mean: I am considering a Markov chain with N+1 states (denoted by $0,1,...,N$), the probability of going from state $i$ to state $j$ is ...
1
vote
0answers
18 views

convergence of markov chain, find distribution of limit

let $T=\mathbb{N}$ and $(X_t)_{t \in T}$ be a markov chain with state space $E=\{a,b\}$. the one step transition matrices are given by \begin{equation*} P(t,t+1)= \begin{pmatrix} 0,2+0,8f(t) ...
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
51 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
25 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
76 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
43 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
34 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
59 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
35 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
30 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
34 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
45 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
34 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
96 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
28 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
65 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
41 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
21 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
87 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
37 views

Euler-summability of a convergent sequence and its limit

In the book Finite Markov Chains by John G.Kemeny and J.Laurie Snell, the authors introduce the following concept of Euler-summability of a sequence: Having a sequence $(s_n)_{n \geq 0},$ we ...
1
vote
0answers
24 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 ...