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

Probability of getting disease and Markov chain

I am studying marcov chain. The question is . There are 5 people ( 4 diseased / 1 healthy) Two people are selected randomly and assumed to interact. If one is diseased and the other is healthy, ...
0
votes
0answers
13 views

How to estimate a hidden model for an unstationary Markov process?

I have a problem that is very similar to the one solved by the Baum–Welch algorithm. I have a process that is very similar to a hidden Markov process. The only difference is that I have an observable ...
0
votes
0answers
18 views

Null recurrence to positive recurrence in DTMC

What are some examples of null recurrent DTMC whose jump chain is positive recurrent? Specifically, for this null recurrent DTMC, removing self loops and normalizing the other outgoing edges from each ...
0
votes
0answers
32 views

recurrence/transience on random walk

Let $X_n$ be a markov chain, $p>\frac{1}{2}$ and $E=\{0,1,2,...\}$ its state space. Let $\Pi$ be its transition matrix with $\Pi(0,0)=p$, $\Pi(i+1,i)=p$, $\Pi(i,i+1)=1-p$ , $i\ge0$. ...
1
vote
1answer
32 views

Determining probabilities Markov Chain

If I have a Markov Chain $X_0, X_1, X_2 \dots$ that has a transition probability matrix $ \textbf{P} = \matrix{~ & 0 & 1 & 2 \cr 0 & 0.3 & 0.2 & 0.5 \cr ...
0
votes
1answer
24 views

Card shuffling transition matrix

a short understanding question. Consider a pile of $n$ cards. At every step we choose randomly 2 cards and transpose them. Now $X_n$ should be a Markov chain which describes the order of the pile at ...
1
vote
1answer
67 views

Determining a transition probability matrix

If I have that $X_n$ is a two-state Markov chain whose transition probability matrix is: $P = \left( \begin{smallmatrix} \alpha & 1-\alpha\\ 1-\beta & \beta \\\end{smallmatrix} \right)$ ...
-1
votes
1answer
48 views

Calculate expected value for a lazy Random Walk

Calculate the mean of time needed for a lazy random walk on $[0,n]$ which starts on $0<k<n$ to hit $0$ or $n$ if in each step the walk stays in probability $\frac 1 3$, goes to the right in ...
0
votes
1answer
138 views

Random Surfer as a Markov Chain

Consider a random surfer who begins at a web page (a node of the web graph) and executes a random walk on the Web as follows. At each time step, the surfer proceeds from his current page A to a ...
0
votes
2answers
87 views

In M/M/1 Markov process, why must entering and leaving the zero state be equal?

According to the image below, which I snipped from this article, the rate of leaving State 0 and the rate of arriving into ...
2
votes
0answers
38 views

An irreducible Markov chain is a martingale

Let $\{X_n\}$ be an irreducible Markov chain. Does exist example of such $\{X_n\}$ which is also a martingale given that: a. $\{X_n\}$ is recurrent with finite number of states (but bigger ...
0
votes
0answers
21 views

Reference on Discrete Markov Chains

I am essentially looking for reference books on Discrete Markov Chains. You can see our full syllabus here.
1
vote
1answer
33 views

How long does it take two identical hidden Markov models run on same observations to forget their initial distributions (if ever)?

Let $H_1$ and $H_2$ be two instances of a finite Hidden Markov Model (HMM) $H$. That is, $H_1$ and $H_2$ have identical state spaces $Q$ as well as identical transition $A$ and emission probabilities ...
1
vote
0answers
19 views

Calculate $P(X_{16}=2|X_0=0)$

Given a Markov Chain with three states 0,1,2 with the following State Transition Probabilites: $$M = \left( \begin{array}{ccc} 0.3 & 0.3 & 0.4 \\ 0.2 & 0.7 & 0.1 \\ 0.2 & 0.3 ...
0
votes
0answers
21 views

Show recurrence of a class

I am a little bit confused with the definition of recurrence with respect to Markov chains. For example consider the transition matrix $$ P=\frac{1}{2}\begin{pmatrix}0 & 1 & 1 & 0 & ...
1
vote
2answers
44 views

Expected first return time of Markov Chain

Given the following Markov Chain: $$M = \left( \begin{array}{cccccc} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 \\ \frac{1}{4} & \frac{3}{4} & 0 & 0 & 0 & 0 ...
1
vote
1answer
65 views

Intuition behind Stopping Times

I'm attending a stocahstic processes course. I have some trouble with the intuition behind a stopping time. I will consider the discrete case to make it simpler. a stopping time is given by ...
1
vote
0answers
36 views

How to find the long range transition matrix L of P

P is the transition matrix of a regular Markov chain. Find the long range transition matrix L of P. $$ P = \begin{bmatrix} 1/2 & 1/4 & 1/4\\1/2&1/2 &1/4\\0 &1/4 & ...
2
votes
1answer
36 views

Can two nodes in a Markov chain have transitions that don't total 1?

In all the Markov diagrams I see, the transitions from state A to B always total to one. Just one of many examples, this image ...
0
votes
0answers
38 views

Dynamics of birth-death process with discouraged arrivals (alternatively, M/M/1 queue with balking customers)

Take a continuous-time birth-death process, where $k \in \{0,1,\ldots\}$ is the count and the arrival rate of death is $\mu \geq 0$ for $k = 1, 2, \ldots$ the arrival rate of births is $\alpha_k ...
2
votes
0answers
19 views

How do I integrate this master equation from a time-continuous Markov chain?

I hope the question is not too vague. My calculus courses are way in the past and I can't remember how to do it :-). I have this master equation for a time-continuous Markov chain I have a two ...
0
votes
1answer
21 views

Every finite closed class is recurrent

Let $(X,E,P)$ denote a Markov chain, where $X=(X_n)_{n\in\mathbb{N}_0}$, $E$ is finite state space and $P$ is the transition matrix. Claim: Every finite closed class is recurrent. Here is ...
1
vote
2answers
42 views

In Markov chains a limit distribution is invariant

Suppose we have a Markov chain $(X_n)_{n \geq 0}$ with state space $S$. Suppose that $(\pi_i)_{i \in S}$ is a limit distribution. Then is $(\pi_i)_{i \in S}$ an invariant distribution ? I know the ...
1
vote
1answer
31 views

Why does a process only satisfy the Markov property if and only if the random times are exponentially distributed?

Given, for example, a birth death process with a set of jump times. These jump times have to be exponentially distributed in order for this process to satisfy the Markov property. Why is this? Why ...
1
vote
0answers
4 views

Why does a Markov chain with one irreductible class has a lower triangular transition matrix?

Given a Markov chain on an infinite and countable set of states, with one irreductible class that has a finite number of states, why can its transition matrix be put in a lower triangular form ? ...
0
votes
0answers
25 views

Does a state which is passed at least 3 times had to be passed 5 times in Markov chain

Prove of disprove: Let $\{X_n\}_n$ be homogenous Markov chain. if we start from state $i$, there is a positive probability that we pass at least 3 times at state $j$. Does it follows that exists ...
1
vote
0answers
72 views

Exercise on Markov chains

I'm preparing my Probability exam and I'm having trouble with exercise 2 here. The question is to consider the random walk on $E$ with transition matrix $p$ and find the communication classes (or ...
0
votes
0answers
15 views

continuous markov chain generator

I am trying to learn Markov process with my own. I am a little confused about the generator of markov process. I understand that Markov process consists of embbedded Markov chain matrix and the ...
0
votes
0answers
45 views

Proof of “strong law of large numbers” in Markov Chains

I have been given a theorem stating an analogue of the strong law of large numbers for Markov chains. It states that if $X=(X_n)_{n\in\mathbb{N}}$ is a Markov chain with transition matrix $p$ and ...
2
votes
1answer
72 views

Conditional independence given elementary events implies conditional independence given $\sigma $-algebra

Proposition: Let $X$ be a continuous markov chain with discrete state space $S$. Let $Z$ be the corresponding jump chain and $\left\{ {{W_i},i \in \mathbb{N}} \right\}$ its holding times. Let ...
3
votes
0answers
35 views

Periodicity of Markov chains under cartesian product

Suppose that you have a finite state Markov chain, with $n$ states and characterized by $p_{i,j}$ the probability of reaching state $j$ from state $i$. Consider the new Markov chain with $n^2$ states ...
0
votes
1answer
73 views

Markov chain doesn't sum up to 1

Let $\{X_n\}$ be a Markov chain on $S=\{1,2,3,4,5,6\}$ with the matrix suppose we define a new sequence $\{Y_n\}$ by $$Y_n=\cases{1\quad X_n=1\vee X_n=2\\2\quad X_n=3\vee X_n=4\\3\quad ...
1
vote
0answers
13 views

Marcov Chain confirmation

I am currently having some problems on the following question: Given is the function $f(x)$: $f(x) = 0,1,2$ with probability $\frac{1}{3}$ for each. I have to give the state space, transition ...
0
votes
0answers
30 views

Proof of theorem on markov chains

If $X=(X_n)_{n\in\mathbb N}$ is a Markov chain on a space $E$, it has an initial distribution $(\lambda_i)_{i\in E}$ such that $\sum\lambda_i=1$ and a transition matrix $(p_{ij})_{i,j\in E}$ such that ...
0
votes
1answer
66 views

Why does from Perron-Frobenius follow that that constant functions are the only harmonic functions here?

in our reading we had the following example for a Markov chain. State Space $E=\left\{1,2,3,4\right\}$ and Transition Matrix $$ P=\frac{1}{3}\begin{pmatrix}0 & 1 & 1 & 1\\1 ...
0
votes
0answers
33 views

non-integer powers of transition matrices with complex eigenvalues and resulting negative probabilities

I am currently working on a Markov Chain model for transition probabilities of a certain set of states. I am trying to figure out how to scale my transition matrix to arbitrary time periods by raising ...
0
votes
0answers
19 views

Memory less property of a Markov chain- Validation methods

Are there any tests to check the memory less property of a discrete time homogeneous Markov chain? I found a chi squared test to verify the time homogeneity of a Markov chain constructed from a set of ...
0
votes
0answers
5 views

Hastings algorithm

Let $Q=\begin{pmatrix} 0 & 1 & 0 & 0 & 0\\0.5 & 0 & 0.5 & 0 & 0\\ 0 & 0.5 & 0 & 0.5 & 0\\ 0 & 0 & 0.5 & 0 & 0.5\\ 0 & 0 & 0 ...
0
votes
1answer
27 views

Transition probability matrix of Markov chain

Given that $g(x)=\begin{cases} 1/3 \quad\text{for } x=0\\ 1/3 \quad \text{for } x=1\\ 1/3 \quad \text{for } x=2\end{cases}$ Explain why independent draws $X_1,X_2,\dots$ from $g(x)$ ...
0
votes
0answers
22 views

Markov chain general help

If I have an absorbing state markov chain (with 2 absorbing states, graduate and dropout), and I know how many people I have in each state (say total for all states is 1000), how would I work out what ...
8
votes
2answers
159 views

$L^2$ Bounds for Markov Chains.

Consider a non-negative, square stochastic $n \times n$ matrix $P$ (rows sum to one, $P$ is ergodic). We are interested in characterizing the set of $n \times n$ invertible matrices $A$ such that we ...
0
votes
1answer
56 views

Proof that there exists a non-negative eigenvector corresponding to eigenvalue 1 of stochastic matrix

Let $P \in [0,1]^{n \times n}$ be a [irreducible or reducible] stochastic matrix where its rows sum to 1 i.e. $$ \forall i \in \{ 1 , \dots n \} \quad \sum_{j=1}^{n} P_{ij} = 1 $$ It is easy to show ...
0
votes
0answers
43 views

Create a Martingale out of a Markov Chain.

Consider a homogeneous finite state Markov chain $\{X_n\}$ with transition matrix $P$ and state set $S$ consisting of real numbers. How to choose the elements of $S$ so that $\{X_n\}$ be a ...
0
votes
0answers
6 views

Condition under which Markov Chain remains in a compact set a.s.

Let $\{Y_n\}$ be a Marov chain. Is it good question to ask under what conditions this chain will take values from a compact set a.s. ?
0
votes
0answers
12 views

Given stochastic matrices D and K, under what conditions can I find stochastic matrices that satisfy a given equality?

Let $D \in \Re^{n \times m}$ and $K \in \Re^{m \times n}$ be two stochastic matrices, with $n > m$. The problem is to determine under which conditions there exist stochastic matrices $P \in \Re^{m ...
1
vote
1answer
101 views

Couple/Compare two stochastic processes and prove an intuitive proposition

Consider a stochastic process (denoted $X$) $X_0, X_1, X_2, \ldots$ (not necessarily a Markov Chain) over state space $\{0, 1, \cdots, n \}$. The transition probabilities are ($n$ is the sink state) ...
0
votes
1answer
36 views

Simple Random Walk; Proof hitting theorem; Ballot Theorem

Suppose that $(X_{n}:n\in\mathbb{N})$ is a $\pm1\mbox{-valued sequence.}$ Let $p\in(0,1)$ and $p=\mathbb{P}(X_{i}=1)\mbox{ and}\mathbb{P}(X_{i}=-1)=1-p=q$ . Define the simple random walk ...
0
votes
0answers
28 views

Stationary solution of a binary Markov chain of order m

Let $X$ be a binary Markov chain of order m. What is the stationary solution of X? In other words, find $\lim_{n\to \infty} P( (X_{n-m+1},X_{n-m},...,X_{n}) =(a_1,a_2,...,a_m))$, for arbitrary values ...
0
votes
0answers
27 views

Steady state of a specific Markov martirx

Let $n = 2^L$ for an arbitrary integer $L>0$ and let $A=(a_{i,j})$ be an $n \times n$ matrix with the following structure: For $1\leq i \leq \frac{n}{2}$, $a_{i,2i-1} = p_i$, $a_{i,2i} = 1- ...
2
votes
1answer
51 views

Eigenvectors of transition matrices in PageRank algorithm

In my probability course, we were discussing applications of Markov Chains to computer science -- in particular, how the PageRank algorithm goes about finding stationary distributions, and thus, ranks ...