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

Gambler's Ruin Duration with 10 Chips, 50% Chance of Ruin

Abraham and Blaise each have $\$10$. They repeatedly flip a fair coin. If it comes up heads, Abraham gives Blaise $\$1$. If it comes up tails, Blaise gives Abraham $\$1$. What is the expected number ...
4
votes
2answers
488 views

Random walk, Cat and mouse

Here is the problem. In graph G, on different vertices there is cat and mouse. Cat and mouse do independent random walk, but time is synchronous, in one unit of time both cat and mouse do one step. ...
-1
votes
1answer
24 views

Function Composition over a Markov Chain [on hold]

Can any one give me an example of how a composition of a function $F\circ(S,P)$ is not a Markov chain? if $(S,P)$ is a finite and discrete Markov Chain. I want to know how to construct a function F ...
0
votes
1answer
33 views

Markov processes: Hitting times for a point form an i.i.d. sequence

Say that I have a recurrent time-homogenous diffusion process X (continuous strong markov process) and two points $x,y$. If $X_t$ goes from $y$, to $x$ and then back to $y$ again we denote it as a ...
0
votes
1answer
618 views

Expected state of a Markov chain

Let's start with a slightly trivial Markov chain defined as follows: the beginning state is called $1$ and the set of states is $\mathbb{N}$. At each step, when the current state is $n$, the ...
2
votes
0answers
19 views

a conceptual question on markov chain [duplicate]

Suppose $\{X_n,n\ge 0\}$ and $\{Y_n,n\ge0\}$ are two independent discrete-time markov chains (DTMC) with state space $S=\{0,1,2,\ldots\}$. Prove or give a counterexample to: $\{X_n+Y_n,n\ge 0\}$ is ...
-1
votes
0answers
31 views

Showing that $(X_n)$ obeys the Markov Property. [closed]

Consider a process $(X_n)_{n\geq0}$ where we define $X_0 = 0$ and for $n \geq 1$: $$X_n = X_{n-1} + Z_n$$ where $Z_n$ for $n \geq 1$ are independent random variables on $\{ -1, 1 \}$ with ...
0
votes
0answers
19 views

Compute distribution in Hidden Markov models

Let $Z_1, Z_2, ..., Z_n$ be the latent variables, and $X_1, X_2, ... X_n$ be the observed ones in a hidden markov models. Let's assume that the parameters of the hidden Markov models are known: the ...
2
votes
1answer
46 views

Error in Billingsley?

Problem 8.25 in the third edition of Probability and Measure by Billingsley (1995, p. 142) is as follows: Suppose that an irreducible [Markov] chain of period $t>1$ has a stationary ...
0
votes
0answers
21 views

Difference between AR model and Markov Chain

We know that Markov Chain can be represented as $$x_t=ax_{t-1}+\epsilon_t,$$ where $\{x_t\}$ are states, $\epsilon$ is noise, and $a\neq 0 \in R$. For the AR model, we know that, the first order ...
-1
votes
1answer
57 views

How many steps would it take to get to the top of this staircase?

There are 26 steps in a staircase. You have a 51% chance to step onto the next step, and a 49% chance to step back down to the step prior. Assuming you are already on the first step, how many steps ...
0
votes
1answer
17 views

Find $P(\eta_t=m)$, $m=0,1,2,\dots,$

Let $\epsilon_t$, $t=1,2,\dots$ independent random variables with $P(\epsilon_t=1)=p$ and $P(\epsilon_t=-1)=1-p$. If $\eta_0=0,\eta_t=\eta_{t-1}+\epsilon_t$ , $t=1,2,\dots$ where $\eta_t$ is ...
12
votes
1answer
363 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 ...
3
votes
2answers
44 views

Ergodic components of Markov chain by transition matrix

I would like to find an algorithm for obtaining all ergodic components of a finite Markov chain with discrete time defined by its transition matrix (i.e. ergodic subchains into which the given chain ...
0
votes
1answer
82 views

Combinatorics Statistics Probability of a Letter Chain

What formula could help me quantify the probability of a chain of three letters (English Alphabet) where each letter is based on the previous one (stochastic modeling, Markov-chains, probabilities) ...
0
votes
0answers
25 views

Can an irreducible, recurrent continuous time Markov chain have spontaneous states?

Let $(X_t)_{t\geq0}$ be a continuous time Markov chain on some (possibly countably infinite) state space $S$ with Q-Matrix $q(\cdot,\cdot)$, transition function $p_t(\cdot, \cdot)$ and invariant ...
0
votes
1answer
388 views

Renewal Processes for Uniform and exponential Distributions

Suppose the lifetime of a component $T_i$ in hours is uniformly distributed on $[100, 200]$. Components are replaced as soon as one fails and assume that this process has been going on long enough to ...
7
votes
1answer
466 views

Intuition on Harris recurrence

I am trying to get some intuition on Harris recurrence in Markov chains. Define state space $\mathcal S$ comprising a single communication class, $f_{ii}^{(n)}=P(X_n=i, X_{n-1}\ne i,\ldots X_1\ne ...
0
votes
1answer
37 views

Show that if $\{X_n\}$ is a Markov Chain

Show that, if $\{X_n\}$ is a Markov Chain then $$P(X_n=j\mid X_k=l,X_m=i)=P(X_n=j\mid X_m=i),0\leq k<m<n$$ What I did is $$P(X_n=j\mid ...
0
votes
0answers
11 views

Metropolis Markov Chain and Mixing Time

I have a statistical mechanical system, which I would like to sample with the Gibbs distribution using a Metropolis-Markov chain. I think the following are standard questions, but I am not sure what ...
2
votes
0answers
102 views

When the sum of Markov chains is a Markov chain: “dumb” algorithm

Suppose I have two (independent) discrete-time and space, preferably non-homogeneous Markov chains $\Gamma^{(i)}=\{\gamma_1^{(i)},\gamma_2^{(i)},...\}, \ i=1,2$ and I want to find a way to check when ...
2
votes
0answers
12 views

How to compute Generalized Group Inverse?

Given a transition matrix $P \in \mathbb{R}^{n \times n}$, i.e. $\sum_j P_{ij} = 1$ and $P_{ij} \geq 0$ for all $i,j$. One can show that there exists a unique group inverse $B$ of $A:= I - P$ which ...
1
vote
0answers
15 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 ...
5
votes
3answers
404 views

From a deterministic discrete process to a Markov chain: conditions?

When will a probabilistic process obtained by an "abstraction" from a deterministic discrete process satisfy the Markov property? Example #1) Suppose we have some recurrence, e.g., $a_t=a^2_{t-1}$, ...
2
votes
1answer
20 views

Survey on large deviation bounds of queuing delay in CSMA scheduling

I am trying to do some literature survey on the theoretical guarantees in uplink scheduling algorithms. I found there exist a series of papers from UIUC and UC Berkeley by L.Jiang, J. Walrand, R. ...
1
vote
1answer
459 views

Best martingale for sequence of “dozen” bets at roulette game

Jim goes the Casino to play roulette. He only makes “dozen” bets at each spin ; his probability of winning is therefore $\frac{1}{3}$ every time (to simplify, we neglect the effect of the zeros in ...
2
votes
2answers
297 views

probability terminology for parameter in a Markov process

Suppose $$P(\text{feature present at time} \ t \ \text{and} \ t+\Delta t) = \beta^{2}+\beta(1-\beta) \exp(\Delta t/\tau)$$ where $\tau = 1/(\pi_{01}+\pi_{10})$. What is $\tau$?
1
vote
1answer
51 views

Population exercise with Markov chains

I am totally stuck with this exercise on Markov chains. Maybe someone can help me :). Red and green bacteria A growth medium at time $t = 0$ has 500 red bacteria and 500 green bacteria. Each ...
2
votes
1answer
825 views

Long run probability of going to a state from another

We consider the following transition matrix for a markov chain with state space {A,B,C,D,E} : $P= \left( \begin{array}{ccccc} \frac{1}{2} & 0 & 0 &0 &\frac{1}{2} \\ 0 & ...
1
vote
3answers
590 views

Expected number of visits to state $j$ between successive visits to a state $i$ in a Markov chain given conditional information

Say I have a Markov chain $\{X_n: n \geq 1\}$ with state space $E = \{1,2,3,4,5\}$ and transition matrix, $$ P = \begin{bmatrix} 0 & 1/2 & 1/2 & 0 & 0 \\\ 1/2 & 0 & 1/2 & ...
3
votes
1answer
320 views

Probability of being at a certain point after $N$ steps in Random Walk with a single absorbing barrier

A random walker in $1$ dimension starts walking from a point $k>0$ with an absorbing barrier at point $0$. What is the probability that he will reach a point $m>0$ in $N$ steps? How should I ...
2
votes
2answers
60 views

Markov chains and conditioning on impossible events

Consider a Markov chain $(X_0,X_1,\ldots)$ with a state space $S\equiv\{s_1,s_2\}$ and the following matrix of “transition probabilities” (I will explain the use of quotation marks below): ...
5
votes
1answer
60 views

Analytic Center of Convex Polytope

I have a convex polytope defined by $Ax \leq b$. I want to know how to find the "analytic center" of my convex polytope, because my goal is to sample from the polytope using Monte-Carlo Markov ...
0
votes
2answers
27 views

Markov chain periodicity

Can a Markov chain have 5 states, one open and one closed class and all the states be periodic (e.g. period 2)? I tried the following: https://www.dropbox.com/s/v818oqlizaci23m/Untitled.png?dl=0 but ...
1
vote
1answer
128 views

Transition Matrix $P$ of a Linear Birth-Death process

I am working on a problem where I have to prove that $P_{20}(t)=P_{10}^2(t)$, given that I have a linear Birth and death process: i.e. $\lambda_n=n.\lambda$ and $\mu_n=n.\mu$. I think the solution ...
1
vote
1answer
33 views

Stationary distribution in continuous-time Markov chain

Consider a barbershop with one barber who can cut hair at rate 4 (people per hour), and three waiting chairs. Customers arrive at rate 5 per hour. Customers who arrive to a fully occupied shop ...
1
vote
0answers
25 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
30 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
20 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}, ...
2
votes
0answers
10 views

The restriction of the green function is non-degenerate

On the context of irreducible Markov chains on a finite graph one defines $$G = \sum_{k=0}^\infty \hat{Q}^k $$ where $\hat{Q}$ is the restriction of a stochastic matrix to a subset (one can think ...
0
votes
1answer
24 views

What is the practical meaning of probability vectors?

I have been reading a lot about probability vectors, as a part of "Introduction to Probability" course. Now, whenever it was mentioned, it was defined theoretically as a vector whose entries add up to ...
4
votes
0answers
54 views

Weak convergence of a sequence of stationary distributions to another stationary distribution

Let $\{X_n(t) \in \mathbb{Z}^+\}$ for each $t \in (0,1)$ denote a discrete time Markov chain (with time index $n$ and parameterized by $t$). For each $t$, the Markov chain $\{X_n(t)\}$ has a unique ...
0
votes
1answer
36 views

What is wrong with matrix [[1,.5,0] [0,0,0] [0,.5,1]] steady state?

I know that Markov matrices have steady state since they always have eigenvalue $\lambda = 1$. We just solve the system of equations $A\vec x = 1 \cdot \vec x$ or $$\begin{cases} k_{a\to a} a + ...
1
vote
1answer
326 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 ...
1
vote
0answers
34 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
19 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
1answer
78 views

Expected Value of a Mosquito

A mosquito is walking at random on the nonnegative number line. She starts at $1$. When she is at $0$, she always takes a step $1$ unit to the right, but, from any positive position on the line, she ...
6
votes
1answer
62 views

Martingale converges to the boundary

I asked an almost same question before and it is solved by considering adjacent $Z_n$ can not be far away and obtain a contradiction. However, if the setting is altered a bit, I wonder whether it is ...
4
votes
0answers
71 views

Harmonic functions and null recurrence

Let $(X_n)_{n \geq 0}$ be a irreducible Markov chain defined on a countable state space $S$. It is known some ways to figure out if this chain is recurrent or not looking for superharmonic functions ...
-1
votes
1answer
57 views

Billingsley Exercise 8.8 (Markov Chains)

I am studying from Billingsley and would like some hints on the following exercise. Suppose $S = \{0,1,2,...\}$, $p_{00} = 1,$ and $f_{i0} > 0$ for all $i$. Here, $S$ represents the state ...