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

Show that this Markov chain is recurrent

So I have a Markov chain on the nonnegative integers such that, starting from $x$, the chain goes to $x+1$ with probability $p$, $0<p<1$, and goes to state $0$ with probability $1-p$. I'm ...
0
votes
0answers
6 views

Equivalent Formulation of Markov Property for Homogeneous Chains

In Shiryaev's Probability (just above the strong Markov property, p.568), the author says that an equivalent formulation of the usual Markov property for homogeneous chains is $$P[\theta_nX\in B\mid ...
0
votes
1answer
17 views

$n$-step transition probability of a Markov chain

Let $(X_t)_{t\in\mathbb{N}_0}$ be a time-homogenous Markov chain over a finite state space $\left\{1,\dots,m\right\}$, so that we've got $$\Pr(X_{t+1}=j\mid X_t=i_t,\dots,X_0=i_0)=\Pr(X_{t+1}=j\mid ...
0
votes
0answers
19 views

Irreducible Markov chain being recurrent

I've come across the following theorem in Sheldon Ross's book whose converse part I am unable to prove. Theorem: An irrreducible Markov chain with state space 0,1,2,... is recurrent if and only $\ ...
2
votes
1answer
20 views

Interpretation for the determinant of a stochastic matrix?

Is there a probabilistic interpretation for the determinant of a stochastic matrix (i.e. an $n \times n$ matrix whose columns sum to unity)?
2
votes
1answer
27 views

Is this a Markov chain? [duplicate]

Let $\{\xi_n \}_{n \geq 1}$ be i.i.d random variables taking values on $\mathbb{Z}$. Let $\xi_0 = 0$. $S_n = \sum\limits_{i=1}^{n} \xi_i,$ where $S_0=0$ $Y_n = \sum\limits_{i=0}^{n} S_i$. My ...
3
votes
1answer
30 views

Mean exit time / first passage time for a general symmetric Markov chain

Suppose I have a Markov chain as depicted in the following figure: where $N$ is even. State 0 and $N$ are the two sinks of the chain. The transition probabilities have the following property: ...
0
votes
0answers
27 views

How to check if a given Markov chain is positive recurrent.

I'm trying to solve a problem which is related to my research, and I have to check whether this infinite-state Markov chain is positive recurrent or not. Suppose the Markov chain I have has state 0, ...
2
votes
1answer
73 views

Probability of a substring occurring in a string

Consider a random string of length $n<\infty$ where each digit can be between 0-9 with equal probability and a substring of length $k<n$ consisting of only zeros. What is the probability of ...
1
vote
2answers
36 views

$(S_0+\ldots + S_n)_{n\geq 0}$ not a Markov chain

Assume that $Y_0,\ldots , Y_n$ are independent random variables with the following identical distribution: $Y_i=1$ with propability $p$ and $Y_i=0$ with propability $1-p$. Also set $S_0=0$ and ...
2
votes
0answers
12 views

Proving that an inductively defined function is a Markov chain

Let $X_0$ be a random variable with values in a countable set $I$. Let $Y_1,Y_2,\ldots$ be a sequence of independent random variables, uniformly distributed on $[0,1]$. Suppose we are given a function ...
0
votes
0answers
28 views

Conditional expectation of a Markov-chain - can the conditioning Sigma-algebra be changed?

Let $(X_n)_{n \in \mathbb{N}_0}$ be a Markov-chain and $(\mathfrak{F}_n)_{n \in \mathbb{N}_0}$ the induced filtration $\mathfrak{F}_n := \sigma(X_0, \dots, X_n)$. Is then ...
0
votes
1answer
13 views

Modelling Transition Between States without Markov Property

I have a data set that I'm trying to model out. My data set tracks an individual items over 20 periods. In each period each item can be in one of four states. There are no restrictions on how items ...
1
vote
1answer
34 views

Proof of extinction probability in Galton-Watson-process using a Martingale

this problem is somewhat similar to the thread The extinction probability of Galton-Watson process from a Martingale perspective. I want to show, that for a Galton-Watson-process $Z_0,Z_1,\ldots$ with ...
1
vote
0answers
50 views

Decomposing a stochastic matrix into a product of stochastic matrices.

It is well-known that any square real matrix of small rank $k$ can be decomposed into a product of a skinny matrix with $k$ columns and a fat matrix with $k$ rows by means of an SVD. This question is ...
1
vote
0answers
15 views

Calculate ultimate survival when more than 1 survival curve is needed to determine outcome

I would like to know if it is possible to combine multiple survival curves via an equation (e.g., via matrix multiplication or whatever) rather than stepping through multiple equations. E.g., assume ...
0
votes
1answer
19 views

Expectation of staying in same state for a simple MC

Consider a simple dicrete-time Markov Chain $X_t$ with finite state $\Omega = \{1,2,3\}$. At time 0 the chain is with probability 1 in state 1 $\mathbb{P}(X_0 = 1) =1$. Then the transition probability ...
0
votes
0answers
14 views

Markov vs reinforcement learning

What's the different between markov chain ,markov decision process and reinforcement learning? when we can apply these theories?
0
votes
0answers
11 views

markov process with extra boundary

In a markov process a random walker has to reach N (absorbing boundary) from $x_o$ on a $[0,N]$ lattice, where $0$ is the reflecting boundary. To find the first exit time of the random walker via N, i ...
1
vote
1answer
51 views

Markov Chains : Can anything be said about what happens in between two transition?

In time homogeneous discrete Markov chains we take a set period for a single transition. In examples we see sometimes depending on the examples the transition period being a a month a week etc. I'm ...
1
vote
1answer
27 views

Steps in a proof from Spectral Graph Theory by Fan Chung

On page 15 of Spectral Graph Theory by Fan Chung, http://www.math.ucsd.edu/~fan/research/cb/ch1.pdf, before eq (1.14) is the step, $\displaystyle || \sum_{i\neq 0} (1-\lambda_i)^s a_i \phi_i ...
0
votes
0answers
16 views

A basic problem on Markov chain

Consider an irreducible finite state Markov chain. Can we say that the following quantity is independent of $s$. $$\frac{E[\sum_{i=1}^{T} X_i]}{E[T]}$$ where $T$= time between two successive visit to ...
0
votes
0answers
8 views

minimum condition under which time avg. and ensemble avg. are equal for a markov chain

What is the minimum condition under which time avg. and ensemble avg. are equal for a markov chain. Is it ergodicity ?
-1
votes
0answers
16 views

A basic doubt on ergodic markov chain

Given an ergodic markov chain $\{X_n\}$ is there any easy way to calculate the following in terms of $i$ and transition probabilities ? $$ \inf(\lambda \in \Bbb R_+ : \sum_{n=0}^{\infty} \lambda^{-n} ...
1
vote
1answer
22 views

In an irreducible, aperiodic, null-recurrent Markov chain holds $\sum_n p_{ij}^{(n)} = \infty$

My lecture notes state the following theorem: Theorem 2. Let $(X_n)$ be an irreducible, aperiodic, null-recurrent Markov chain. Then $$\forall i,j \in S : p_{ij}^{(n)}\to 0 \text{ and } \sum_n ...
1
vote
1answer
87 views

A Markov Chain Problem.(Change the color of ball)

There are $n$ different color balls in a box. Take two balls in turns, and change color of the second ball to the first. (This is one operation). Let $k$ be the (random) number of operations needed to ...
0
votes
0answers
48 views

Dining philosophers using markov chains

We have 5 philosophers sitting at a table, where between each pair of philosophers is a single chopstick. They alternatively think and eat. When they want to eat, they pick up the chopsticks either ...
1
vote
1answer
28 views

Markov property for discrete Markov chains. A question about “adjacent random variables”

Consider a discrete Markov chain (with values in $\mathbb R$) $\{X_n:\, n\in\mathbb N\}$: namely the state space $S$ is a countable subset of $\mathbb R$ and the random variables are $X_0, X_1, ...
0
votes
1answer
33 views

M/G/1 queue has embedded Markov chain

I tried to prove that the M/G/1 queue has an embedded discrete-time Markov chain. But I'm not sure if I have done it right and properly. Specially I'm not 100% sure if i calculated right the ...
0
votes
1answer
40 views

How to apply the strong Markov property in this case?

I'm trying to understand the following proof: Theorem: Let $(X_n)$ be an irreducible $(\alpha, \mathbf p)$-Markov chain with a finite state space $S$. Then $(X_n)$ is positive recurrent. ...
0
votes
0answers
24 views

A linear-algebraic property of stochastic matrices.

All matrices are real, $n \times n$. By a stochastic matrix, I mean any non-negative real matrix with rows summing to one. Denote the set of all stochastic matrices by $\mathcal{S}$. By $I_k$ I mean ...
1
vote
1answer
37 views

How to find the conditional expectation of the following random variable?

Let $\{N_n; n=1,2,3,\dots,\}$ be an irreducible and aperiodic Markov chain with transition probability matrix $\mathcal{P}=\begin{pmatrix} p_{0,0} & p_{0,1}&p_{0,2}&\cdots \\p_{1,0} & ...
1
vote
0answers
22 views

Cereal boxes - Mean time spent in transient states

Problem: A cereal company gives 2 images in each cereal box it has. There are a total of 5 images. Once a buyer have 5 images she wins a prize. No box contains 2 images that are the same. What is the ...
1
vote
1answer
26 views

Branching process: Why does the population die or explode?

Consider a population such that each member, independently from other members, at a certain instant of time is replaced by its offspring. Lets denote with $X_n$ $({n\ge 1})$ the amount of the ...
1
vote
1answer
20 views

Max of independent and identical random variables is Markov

I'm supposed to show that given a sequence $\{Y_n\}$ of i.i.d the stochastic process $$X_n=\max(Y_0, Y_1...,Y_n)$$ is a Markov of chain. I think I could do it by induction but I would rather see how ...
1
vote
1answer
34 views

Markov Property as given in Norris' book on Markov chains vs standard formulation

In the book, Markov Chains, the following theorem is mentioned: Let $(X_n),n≥0$ be Markov$(λ,P)$. Then, conditional on $X_m=i,(X_{m+n})_{n≥0}$ is Markov$(\delta_i,P)$ and is independent of the random ...
1
vote
0answers
54 views

Follow-up on solution to Markov process equation

I asked a question here about solving a system related to an absorbing Markov chain. I now have a variation where there are $m$ types (of student, job seeker, etc) each of which applies to ...
1
vote
1answer
15 views

Limit distribution is invariant

Consider a homogeneous Markov chain $\{X_n\}_{n\in\mathbb N}$ with a countable (but not necessarily finite) state space $S$. Suppose that there exists a limit distribution $\pi$, namely: ...
1
vote
1answer
21 views

About homogeneous Markov chains

Consider a homogeneous Markov chain $\{X_n\}_{n\in\mathbb N}$ with discrete state space $S$. Now consider the map $$T_{ij}=\text{min}\{n\in\mathbb N\,:\, X_n=j\mid X_0=i\}$$ where $T_{ij}$ is defined ...
-1
votes
0answers
24 views

Distributive Law on Sum Product

I am reading a tutorial on Conditional Randome Fileds, Here is the link: http://people.cs.umass.edu/~mccallum/papers/crf-tutorial.pdf in the equation 1.24 it defines: $p(x,y) = \prod_{t=1}^{T} ...
0
votes
0answers
15 views

Markov Models and Applications

I am looking for resources in Markov models and its applications. I'm looking for tutorials, videos, books etc which provide the following Explain Markov chains in layperson terms and provide ...
0
votes
0answers
11 views

Definition of Perron-Frobenius eigenvalue

Consider a Markov chain with state space $X$ and transition prob. matrix $P=(p_{ij})$. Then a paper claims the following : Let $\theta \in X$ denote some fixed state. The Perron-Frobenius eigenvalue ...
-1
votes
0answers
14 views

positive kernel induced by the transition probability P and the function F

Consider a markov chain $\{X_n\}$ and let $F:X \to \Bbb R_+$ a fixed, positive-valued function on $X$. Consider the process $\{F(X_n)\}$. Then what is meant by the positive kernel induced by the ...
1
vote
1answer
41 views

Why are points from this matrix geometric sequence co-planar?

Let $ M= \left[ {\begin{array}{ccc} a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \\ \end{array} } \right] $, such ...
3
votes
0answers
32 views

A basic doubt on Markov chain/ergodicity

Consider a finite state (no. of state $N$) Markov chain $\{X_n\}$ (all the random variables are bounded) such that there is a state $i*$ such that $$ \sum_{i=1}^{N}p_{ii*}^{(n)} > 0$$ for all ...
3
votes
1answer
82 views

For finite Markov Chain, time average distribution is always a stationary distribution?

Given some finite state space $\Omega\equiv\{\omega_1,\ldots,\omega_n\}$ be given, and let any Markov chain $\{X_t\}$ with $n\times n$ transition matrix $A$ on $\Omega$ be given. I would like to know ...
0
votes
0answers
44 views

A question about a Markov Chain

I encountered a question about Markov Chains which looks interesting. Given a homogeneous, irreducible, non cyclic Markov Chain with $K$ possible states and a transition matrix $Q$. We define $T_i$ ...
0
votes
1answer
24 views

Supply the transition matrix for these (possible) Markov chains

Reading Grimmet, Stirzaker: Probability and Random Processes, which unfortunately doesn't have solutions. Trying to make sure I understand Markov chains. A die is rolled repeatedly. Which of these ...
0
votes
0answers
16 views

Probabilities in a Markov Model

I am reading a paper on Markov Models and I am trying to figure out how to compute the probabilities for the $\alpha$-pass. I am given an $N\times N$ matrix $A$, that has the probabilities of ...
0
votes
0answers
28 views

Can ergodic theorem be used here

Suppose I have an ergodic Markov Chain $\{X_n\}$ where $X_n$ are bounded. Now, Can I say anything on the limit $$ \lim_{n\to\infty} \frac{1}{n}\ln E\left[e^{\sum_{i=0}^{n} X_i}\right]$$ I don't ...