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

What is the difference between a reversible markov chain and a reversible in equilibrium markov chain?

In the text i'm using it says: "Let X = {$X_n : 0 \leq n \leq N$} be an irreducible Markov chain such that $X_n$ has the stationary distribution $\pi$ for all $n$. The chain is called reversible if ...
0
votes
0answers
13 views

stopping criteria for power-iteration to find rank-1 matrix

I start with B=I, A positive matrix, and compute B=(BA)/norm(B) by iterating until B is sufficiently close to rank-1 matrix. What is a good stopping criterion for this algorithm? There's Birkhoff ...
-1
votes
0answers
14 views

Communicating classes of a power of the irreducible transition matrix? [on hold]

Suppose $P$ is an irreducible transition matrix, with period $d$. Consider the transition matrix $P^k$. In terms of $d$ and $k$, how many communicating classes does $P^k$ have, and what is the period ...
-1
votes
0answers
29 views

Entropy and Markov chain [on hold]

Assume that $X_n$ is a discrete Markov chain and $H$ is entropy function. I want to prove $$H\left(X_0\mid X_n\right) \geq H\left(X_0\mid X_{n-1}\right)$$ but I have no idea how to prove it. please ...
0
votes
0answers
7 views

Simple Markov property on stopping times

Suppose $(S_n)_{n\geq1}$ is a Markov chain on the two dimensional lattice of the integers. Then define the stopping time $\tau_A'=\inf\{n\geq1:S_n\notin A'\}$ and consider the following for $A\subset ...
1
vote
1answer
25 views

Show that it is a Markov chain, determine the transition-probability matrix and reversibility

Certain machine has three possible states: $0=working,\,1=broken\,and\, awaiting\,repair,\,2=broken\,and\,being\,repaired$. The permanence times (in minutes) in each state have independent geometric ...
4
votes
2answers
33 views

Distribution of throws of die rigged to never produce twice in a row the same result

A die is “fixed” so that each time it is rolled the score cannot be the same as the preceding score, all other scores having probablity 1/5. If the first score is 6, what is the probability that the ...
0
votes
1answer
18 views

Random walk mean number of visits to state before absorption

This is from Stirzaker's book Random Processes. Suppose we have a simple random walk with probability going "up" p, "down" q. At time 0 it stats at 0, so $$S_0 = 0$$ Now let $u_b $ be the mean ...
1
vote
0answers
19 views

Extension of erdodic theorem with WLLN

Suppose you have a ergodic (or irreducible) Markov chain $(A_t)_{t\geq0}$ in continuous time. denote by $\pi$ the invariant distribution of $A$. If $f$ is a function of $A_s$ which is integrable w.r.t....
-1
votes
0answers
33 views

Determining the infinitesimal generator of a Markov chain [on hold]

The infinitesimal generator of a Markov chain $X$ on a countable state space $S$ is defined by $$A(f)(x)=\lim_{t\downarrow 0} \frac{E^x(f(X_t))-f(x)}{t}.$$ Are there any ways of working out $A$ ...
1
vote
1answer
58 views

On the Markov chain defined by $X_n=U_nU_{n+1}$, where $(U_n)$ is i.i.d. symmetric Bernoulli

I came across this problem in homework: $U_n$ are i.i.d random variables with $P[Un=1]=P[Un=−1]=0.5$. a) Show that $X_n=U_nU_{n+1}$ is a Markov Chain. b) Show that $X_n=(U_n+U_{n+1})/2$ is not a ...
1
vote
2answers
65 views

Expected steps to eliminate a character? [closed]

This came up in a game theory crafting exercise. Imagine a character has 195 hit points. You can shoot at them and there are three results: Critical - 100 damage - 40% of shots Body - 50 damage -...
3
votes
2answers
223 views

Expected number of random binary vectors to make matrix of order n

I have the following problem: I pick random vectors from $\mathrm{F}_2^n$. The chance that position $i$ is $1$ equals $p_i$, $0$ otherwise (each position is picked independently). Let $X$ be a random ...
14
votes
1answer
422 views

What happens to a random walk when we increase the probabilities of going right?

Consider a random walk on the integers where the probability of transitioning from $n$ to $n+1$ is $p_n$ (and of course, the probability of transitioning from $n$ to $n-1$ is $1-p_n$); we assume all $...
1
vote
0answers
17 views

First time of passage, discrete random walk with disjoint absorbing regions

I have a sum $T^i$ of zero/one Bern$(p)$ random variables $T_i$ and multiple disjoint absorbing regions, i.e. the absorbing region is a union of disjoint, closed sets: $$T^i \in \bigcup_{u \in \...
2
votes
1answer
196 views

How to transform a process into a Markov Chain?

This problem is in the book Introduction to Probability. The question goes this way. Consider the process {$ X_n, n = 0,1,...$ } with values $0,1$ or $2$. If $$P\left\{X_{n+1} = j \mid X_n = i, X_{...
0
votes
0answers
30 views

Application Strong Markov Property

I am considering a random walk $S_n$ on a state space $\mathbb{Z}^d$. I want to show that $E_x\left[\sum_{n=0}^{\tau_A-1}{1_{\{S_n=y\}}}\right]=\frac{1}{P_x[\tau_A<\tau_y]}$, where $\tau_A=\inf\{n\...
1
vote
0answers
10 views

Filtering/MCMC methods for this HMM

I have a Discrete HMM with hidden Markovian signals of the form $\{X_t\}_{t \in [0, \infty)} \in \{ 1,2,3\}$ and observed outputs of the form $\{Y_n\}_{n \in \mathbb{N}} \in \{ 1,2\}$. Each ...
-1
votes
0answers
14 views

how to find transition matrix given initial state and state after $n$ steps

Is it possible to reverse-engineer the transition matrix of a Markov Chain, knowing only the initial state, and the state after a number of steps? I realize that there may be an infinite number of ...
1
vote
1answer
30 views

Steady state distribution needed

I have a chain $C_t$. At every instant $t$ an exponential random variable $X_t$ with parameter $\lambda$ is added to the chain or if the chain has a value greater than $Q$ then a value $Q$ is ...
1
vote
0answers
92 views

Probability of losing lotteries needed

A person earns $x_i$ amount of money every month where $x_i$ is an exponential random variable with parameter $\lambda_1$. The amount $x_i(1-p)y$, here $0 \leq p\leq 1$ and $y$ is exponentially ...
1
vote
0answers
33 views

Better to go first in Snakes and Ladders?

We consider the game as described in http://www.datagenetics.com/blog/november12011/ . Each person rolls a dice and the person who gets 6 on the face can start and the other keeps waiting. If the ...
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
votes
1answer
37 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 $a$...
-1
votes
0answers
46 views

Computing $\mathbb{E}[Z_n\mid Z_0=1]$ for a branching process [closed]

I came across a question whilst revising material to do with Branching processes. I am looking for help with part $(iii)$, here is my working: \begin{align*}&\mathbb{E}[Z_n\mid Z_0=1]\\&=\...
-1
votes
0answers
14 views

how to check if a process satisfies the markovian property with continuous time?

as an example we have A source transmitting messages is alternately on and off. The off-times are independent random variables having a common exponential distribution with rate α and the on-...
0
votes
0answers
15 views

Is there a way to “normalise” probability values of Markov chain transitions for comparison?

Suppose I have a series of states and I've a database of frequencies (probabilities) of the states transiting from one to another. I've a set of states ${A...G}$. Let's say I've a state transition (...
0
votes
0answers
17 views

Stationary distribution of finite-state Markov chain in terms of determinants/products of eigenvalues

I have an $M$-state continuous-time Markov chain with transition-rate matrix $K$ (the column sums are zero), which has $M$ distinct eigenvalues $\lambda_i$, $i=1,\dots,M$. $\lambda_M=0$, so $K$ has ...
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
539 views

What are “Filtering” and “Smoothing” with regards to Hidden Markov Models?

The Wikipedia article about Hidden Markov Models mentions "filtering" and "smoothing" tasks, see here: http://en.wikipedia.org/wiki/Hidden_Markov_model#Filtering. It gives a brief explanation but no ...
2
votes
1answer
40 views

Bayesian Estimator and Markov Chains

This is Exercise 6.1.14 from Dembo's notes found here. At this point, we are just beginning a discussion of Markov chains. I have no prior experience with estimators and so I am a bit lost with this ...
0
votes
1answer
27 views

Check that stopping time is a.s. finite

I have the following situation. Let $(X_i)_{i\geq1}$ be a sequence of iid random variables in $\mathbb{Z}$ and consider the random walk $S_n=\sum_{i=1}^n{X_i}$, $S_0=x$. Let $y>x$ and consider ...
2
votes
1answer
51 views

Find the mean number of steps in a Markov chain

Let $S = \{1,2,3,4\}$ be a state space like this $$\begin{array}\\ 1 & - & 2 \\ | & & |\\ 3 & - & 4 \end{array} $$ and let $P$ be the transition matrix given by $$P = \begin{...
0
votes
1answer
35 views

Stopping times of random walk with time dependent absorbing barriers

I have a Bern$(p)$ random walk ($Y_i = 1$ with probability $p$ and Y_i = 0 with $1-p$) with two absorbing boundaries, $A: Y^i \leq t_i$ and $B:Y^i \geq d_i-t_i$. Now, both $d_i$ and $t_i$ are evolving ...
0
votes
2answers
45 views

Recurrence Relation with two parameters and Summation

This is a recurrence relation with two parameters which came up in a problem I was trying to solve. Given $$\begin{align}&A_n=pB_{n-1};\qquad &&B_n=q(A_{n-1}+B_{n-1})\\ &A_4=p; \...
0
votes
0answers
23 views

HMM limiting distribution

Consider a hidden markov model (HMM) with two hidden states $A$ and $B$ and emission support $1$ and $2$ fitted with initial state distribution $$\lambda = [\begin{array}{cc} .7&.3\end{array}]$$ ...
0
votes
0answers
30 views

Error term in the definition of the transition rates of a continuous time Markov chain

I'm studying G.F.Lawler's stochastic process book. There he defines the transition rates $\alpha(x,y)$ from the state $x$ to state $y$ (the state space is countable) of a continuous time Markov chain $...
1
vote
2answers
37 views

General Two-State Markov Chain: $P(X_{n}=1)=\frac{b}{a+b}+(1-a-b)^n \big(P(X_0=1)-\frac{b}{a+b}\big)$

Consider a general chain with the state space $S=\{1,2\}$ and write the transition probability as $$\begin{pmatrix} 1-a&a\\ b&1-b\end{pmatrix}$$ Use the Markov property to show that $$P(X_{n}=...
0
votes
1answer
22 views

Long-run fraction Markov Chains

A machine has three critical parts (1,2,3) but can function as long as two of these parts are functional. When two are broken, they are replaced and the machine is functional the next day. The state ...
0
votes
0answers
36 views

Lebesgue Integral vs. Lebesgue Stieltjes Integral

Forgive me if this has been addressed in a question already on here (and for my lack of comfort with measure theory), but is there any difference between the Lebesgue integral and the Lebesgue-...
6
votes
2answers
116 views

Confusion in the proof of properties for $\psi$-irreducibility

Let $P$ be a stochastic kernel on a measurable space $(\mathsf X,\mathfrak B(\mathsf X))$. The kernel $P$ is called $\varphi$-irreducible if for a positive measure $\varphi$ and for all measurable ...
0
votes
0answers
22 views

implementing particle filters without a priory distribution

i am implrmrnting the particle filter, and i have some problem understanding the algorithm. given the state equations: $$ x_k = f(x_{k-1},v_k) $$ $$ z_k=h(x_k,u_k) $$ where $v_k, u_k$ are process ...
0
votes
1answer
114 views

Ergodicity of this Markov Chain

I was recently involved in a debate with a friend over the following graph, and whether it is ergodic or not. In the following diagram, each edge has a strictly positive probability of being travelled ...
4
votes
1answer
79 views

Markov chain ergodicity

$(X_n)_n$ is a discrete-time, time-homogenous Markov chain. I have have the following transition matrix and want to show whether the chain is ergodic. $$P = \begin{pmatrix} \frac{1}{2} & 0 & ...
2
votes
1answer
439 views

Gradient-descent and Hidden Markov Models

I would like to use gradient-descent to fit the parameters of a simple 2-state HMM. This paper Levinson, S. E., Rabiner, L. R. and Sondhi, M. M. (1983), An Introduction to the Application of the ...
0
votes
0answers
47 views

First return times and continuous markov chains.

We are given a generator matrix $Q$ (Q-matrix) for a continuous time Markov chain $(X_t)_t$. We want to calculate the probabilities of: returning to State 3 before State 1, while starting at State 3:...