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
2answers
39 views

Soft Question - book recommendation - Stochastic Processes

My mother language book on stochastic processes is pretty much complete(~500 pages) but would like another one in English, to have in my library. I'm looking for a similar book containing the ...
1
vote
0answers
14 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 ...
-2
votes
1answer
24 views

Markov's matrix into stationary Distribution [closed]

How do I know if this Markov's Transition Matrix converges into a stationary distribution? $$P= \begin{bmatrix} .8 & .2 & 0 \\ .3 & .4 & .3 \\ .2 & .1 & .7 \\ \end{bmatrix}$...
0
votes
1answer
46 views

Construction of continuous-time markov chain and finding stationary distribution

There are 15 lily pads and 6 frogs. Each frog, with rate 1, jumps to one of the other 9 unoccupied pads chosen uniformly at random. What is the stationary distribution for the set of occupied lily ...
1
vote
1answer
65 views

Prove that $Y_n=X_{n-1}X_n$ is a markov chain

Let $\{X_n\}_{n=0}^\infty$ a sequence of discrete random variables independent identically distributed. Let $Y_n$ such that $Y_n=X_{n-1}X_n$ for all $n\ge 1$ Is $\{Y_n\}_{n=0}^\infty$ a markov chain?...
1
vote
2answers
44 views

Find the general expression for the values of a steady state vector of an $n\times n$ transition matrix

I have a question that is asking to find the values of the elements in the steady state vector for a regular transition matrix P of size $n \times n$. All I'm given is that the the elements in each ...
0
votes
1answer
23 views

What is the (practical) difference between a stationary distribution and an equilibrium distribution of a MC?

I know that, for a Markov Chain, a stationary distribution is the (row) vector $\pi$ such that $\pi \cdot P = \pi$, where $P$ is the one-step transition matrix for the MC. Intuitively, I assume that ...
0
votes
1answer
68 views

prove homogeneous markov chain

$Y_0, Y_1,Y_2,\dots$ are independent and identically distributed random non-negative integer outcomes. Let X_0 = Y_0 $ Let $X_0 = Y_0$ and $X_n = X_{n-1} - Y_n$ if $X_{n-1}>0$, else $X_n = X_{n-1}...
0
votes
0answers
20 views

Exercises on the following topics on Markov Chains

We are being taught the following topics in Markov Chains: 1) Markov Chain Monte Carlo: Hard Core model, Counting random q-colourings of a graph 2) Total variation distance for a Simple Symmetric ...
1
vote
1answer
39 views

Transience, recurrence and null recurrence of markov chain

I am trying to get an intuition for transience, recurrence and null recurrence. I constructed an example MC for myself represented by this graph below: I'm thinking that all of the states are ...
0
votes
0answers
35 views

Defective Markov transition matrix and relation to its limiting distributions

Im trying to come to grips with what the physical interpretation of a non diagonalisable Markov Matrix means in terms of what we can deduce about it having a limiting distribution/ what potential ...
0
votes
1answer
49 views

Leaving time of a set

I want to prove the following result. Let $S_n$ be a symmetric irreducible random walk on the integers (d=dimension). Claim: If $x\in A$ and $P_x(T_A=\infty)>0$ then $\forall \epsilon>0\exists ...
0
votes
0answers
34 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 ...
2
votes
2answers
65 views

Renewal process problem, where $X_i$'s are i.i.d. with exponential distribution.

A room is lit by $2$ bulbs. Bulbs are replaced only when both bulbs burn out. Lifetimes of bulb's are i.i.d exponentially distributed with parameter $λ=1$. What fraction of the time is the room only ...
1
vote
2answers
20 views

Attitude true for Markov Chains(Maybe duplicate)

Suppose, that we have a Markov-chain with finite domain. For all $i,j$ elements $P_{i,j}>0$, where $P$ is our matrix. Show, that reversible(sorry, I forgot that out) stationary distribution exists ...
1
vote
2answers
60 views

Prove that $i$ is an accesible state in a markov chain

Let $i$ be a recurrent state of an homogeneous markov chain such that the state $j$ is accesible from $i$ (that is $\exists$ $k\ge 1$ such that $p_{ij}(k)>0$) Prove that $i$ is accesible from $j$ ...
0
votes
0answers
42 views

Computing hitting times from the stationary distribution

My question is whether it is possible to compute hitting times from the previously calculated stationary distribution $\pi$ of a continuous-time Markov process $(X_t)_{t \geq 0}$. I know that, from ...
2
votes
2answers
38 views

Mean number of tosses of a fair dice to get a sum of outcomes being a multiple of $5$

Let $S_n$ denote the sum of the outcomes of the $n$ tosses of a fair dice. Let $T=\inf\{n>0: S_n$ is a multiple of $5\}$. Compute $E(T)$ (by means of markov chains). Attempt. Instead of ...
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 $...
0
votes
1answer
23 views

Mean number of steps needed to reach a recurrent state in a finite irreducible Markov chain

Let $\mathbb{X}$ be a finite state space of an irreducible markov chain $\{X_n\}$ and let $T_x=\inf\{k\geq 0\mid X_k=x\}$ be the number of steps until $\{X_n\}$ reaches state $x\in \mathbb{X}$. True ...
1
vote
1answer
47 views

Markov chains and queues

I do not understand how may I use the Markov Chain $Y$ and and describe the system $X$ using the states that the exercise suggest. I was searching queue's examples and -i understand this is a M/M/1 ...
0
votes
0answers
24 views

Binary Hidden Markov Model

Consider a binary HMM with 2 observed variables $O_n \in \{0,1\} \; \forall n \in \mathbb{N}$. Suppose that the hidden Markov process $X_n$ is characterised by a known transition probability matrix ...
1
vote
2answers
39 views

Continuous time Markov Chain's Natural Filtration

Given a continuous time Markov chain $\left(X_t \right)_{t\geq 0} $ with finite or countable state space $S$, transition matrix $P(t)$, what I want to prove is: $$\text{Let} \quad f:S \to \mathbb{R} ...
1
vote
1answer
37 views

Connection between Ergodic Theory and Markov Chains

Could someone suggest a good reference where the connection between Ergodic Theory and (ergodic) Markov Chains is nicely explained ?
0
votes
0answers
25 views

Distribution of states given observations in HMM

Suppose you have an HMM with two states $(S_1, S_2)$ and two observations $(a, b)$. We know the following: $P(S_1|S_1) = 0.5$ $P(S_1|S_2) = 0.25$ $P(a|S_1) = 0.25$ $P(a|S_2) = 0.5$ Initial state at ...
0
votes
1answer
53 views

Markov chain - distribution of probability of state at generic step

Let $S$ be a finite discrete state set. Let $X(i) \in S, i = 1,2, \ldots$ be a random variable sequence. I've built-up a Markov transition matrix from a set of sequences of states. State $s_1 \in S$ ...
0
votes
0answers
20 views

probability a markov chain leaves a transient state in favor of a recurrent state

Let $\{X_n\}$ be a time-homogenuous markov chain, with state space $\mathbb{X}$ and transition matrix $P$. Let $C_1$ be a transient class and $C_2$ be a recurrent class and let also $x\in C_1,~y\...
0
votes
1answer
61 views

Application of CLT to random walks

Let $X_1,X_2,\ldots$ be an iid sequence such that $P\{X_1 = 1\} = p$, $P\{X_1 = -1\} =p$ and $P\{X_1 = 0\} = 1-2p$. We have that $E[X_1] = 0$ and $E[X_1^2] = 2p$. Define $S_n = \sum_{i=1}^nX_i$ and $...
0
votes
0answers
34 views

Finiteness of the hitting time of random walk

Let $X_1,X_2,\ldots$ be an iid sequence such that $P\{X_1 = 1\} = u$, $P\{X_1 = -1\} = d$ and $P\{X_1 = 0\} = 1-(u+d)$. We have that $E[X_1] \neq 0$. Define $S_n = \sum_{i=1}^nX_i$ and $S_0 = 0$ and ...
0
votes
0answers
50 views

Ergodic Theorem for Markov Chain with one closed communicating class and several transient states

It is known, that if a markov chain with a finite state space has only one closed aperiodic communicating class and several transient states, then there is a unique stationary distribution for this MC....
2
votes
2answers
94 views

Convergence of mean of an irreducible Markov chain / ergodic theorem

Let $\{X_n\}$ be an irreducible Markov chain on a discrete state space $\mathbb{N}$, that has a stationary distribution $\pi$. Prove or disprove : with probability $1$: $$\lim_{n\rightarrow +\...
1
vote
1answer
55 views

Markov Chain Questions

I've been stuck on these problems for a while. I keep banging my head against the wall, but my calculations are incorrect each time. I sum the probabilities together for each possibility (it's a ...
1
vote
0answers
30 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) = P(...
0
votes
1answer
34 views

Number of $1's$ in a string in terms of successive pairs

Problem. Let $X_n=0$ or $1$ and set $Y_n=(X_n,X_{n+1})$. Set also $\displaystyle \sum_{k=1}^{n}\mathbb{I}_{\{X_k=1\}}$ be the number of times $X_k's$ become $1$, from $X_1$ till $X_n$ ($\mathbb{I}_{A}$...
1
vote
2answers
63 views

Non-symmetric random walk on $\mathbb{Z}^2$

a random walker, walks on a lattice with non-negative coordinates. In each step, if he is in a positive coordinate, say $(a,b)$ where $a,b>0$ he will go to $(a-1,b)$ or $(a,b-1)$ with same ...
0
votes
1answer
34 views

What does it mean $f \mu$, when f is a function and $\mu$ a measure?

Let $f$ be a function and $\mu$ a measure. I saw in Revuz's $\textit{Markov Chains}$ the following notation: $$f \mu$$ What does it mean? Thank you!
0
votes
1answer
43 views

calculating limit of a markov chain

I want to calculate the following limit $lim_{n \to \infty}\ A={\begin{bmatrix}1 & 0 &0 & 0&0\\1-p & 0 & p & 0&0\\0 & 1-p & 0 & p&0\\0&0&1-...
1
vote
1answer
52 views

A fair die is thrown repeatedly until we obtain the same number twice in a row.

A fair die is thrown repeatedly until we obtain the same number twice in a row. Compute the expected number of throws. For this, I found $6$ finding the transition matrix and using first step ...
0
votes
0answers
24 views

Markov Chain, probabilities of future generations

Suppose the number of daughters of a woman is 0, 1, 2, or 3 with respective probabilities 0.3, 0.4, 0.2, 0.1. Suppose further that the number of daughters of each of her descendants has the same ...
5
votes
1answer
55 views

Branching Process: generation survival or extinction?

Let $p\in [0,1]$, and consider a branching process where the number of offspring of an individual is zero with probability $p$, and is two with probability $1-p$. Initially there is one ...
0
votes
0answers
40 views

Time to absorption for infinite state Markov chain

I have a Markov chain with a single absorbing state $s_{-1}$. The transient states have absorption probabilities $p_{i,-1} = 1-f_i$ and transition probabilities to the next state $p_{i,i+1} = f_i$. We ...
0
votes
1answer
36 views

Relating the stationary distribution of an ergodic Markov chain to its mean return time

Let $X_t$, $t=0,1,2...$ be an ergodic Markov chain on $S=\{1,...,n\}$ with transition matrix $P=\left(P_{ij}\right)_{i,j\in S}$. Let $T^i=\inf\{t\geq1:X_t=i\}$ and $h_j^i=\mathbb{E}\left(T^i\right\...
0
votes
0answers
90 views

Expected infimum of a 1d random walk

Consider a simple symmetric random walk on $\mathbb{Z}$ starting from $0$, $S_n$. Let $I_n := \inf\{S_0, S_1, S_2, \ldots S_n\}$. Is an explicit formula for $E[I_n]$ known?
2
votes
0answers
53 views

Limiting products of realizations of an integer-valued Markov chain

Let $(X_m)$ be a finite space discrete time irreducible and aperiodic Markov chain with stationary distribution $\pi$. The state space is a finite set of positive integers $\{x_1, x_2, \dots, x_l\}$. ...
1
vote
1answer
30 views

Irreducible and recurrent Markov chain - theorem notation question

In [J. R. Norris] Markov Chains (Cambridge Series in Statistical and Probabilistic Mathematics) (2009), page 35, Theorem 1.7.5 says: In (ii), does it mean $\gamma^k$ is notation for $\gamma^k_i$ ...
1
vote
1answer
137 views

Stochastic Markov Chain Application: Rat in the maze problem, a modification

I am really new to Stochastic processes, and this is one of the supplementary practice questions that I stumbled across whilst studying: Modify the situation as described in http://www.ucl.ac.uk/...
0
votes
0answers
11 views

Alternated Ehrenfest Chain (Welfare Distribution)

Consider a simple wealth distribution model with two trading agents. Let N denote their total wealth (represented by balls of two colors, black and white). At each time the agents may trade, i.e. we ...
1
vote
0answers
20 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 ...
0
votes
1answer
27 views

Symmetric Simple Random Walk - Definition Clarification

I'm finding conflicting answers everywhere, including in my own notes. In the phrase "symmetric simple random walk", which part, "symmetric" or "simple" refers to having a probability of $0.5$ to go ...
1
vote
1answer
37 views

regular Discrete Time Markov Chains

I have a transition matrix $P$. I know that $P$ is regular if all $p^{(n)}_{ij}>0$ for some $n \geq 1$. Is there an algorithm that can help me to verify whether $P$ is regular without calculating $...