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
votes
0answers
14 views

Markov Chain with transition matrix $Q=(I+P)/2$

I have finite irreducible Markov Chain with transition matrix $P$. 1) Prove that Markov Chain with transition matrix $Q=(I+P)/2$ is irreducible and aperiodic ($I$ is identity matrix); 2) Prove that ...
0
votes
0answers
21 views

Sum of two independent Continuous-Time Markov Chains [on hold]

This is the first time I have come across a question involving the sum of two independent continuous time Markov Chains.I know you can find the sum of two random variables Z = X + Y by finding the ...
2
votes
1answer
439 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. ...
0
votes
1answer
10 views

Probabilities in markov chain

I have problem with calculating the probability of Markov Chain with 3 states S = {0,1,2}. I need to calculate $P(X_1=1,X_2=1|X_0=2)$. In the answers to my workbook I am given solution: ...
0
votes
1answer
25 views

markov process and markov chains

I have learned that Markov processes are stochastic processes possessing certain mathematical properties (memoryless, etc). My question is, if you say that a process is Markov, is it automatic (as a ...
0
votes
0answers
17 views

Obtaining the transition probability matrix

Seven black balls are distributed among two persons $A$ and $B$ having urns $X_A $ and $X_B$ with three balls in $X_A$ and four in $X_B$. One white ball is in either $X_A $ or $X_B$. A game consists ...
0
votes
1answer
16 views

Aperiodicity in irreducible markov chains

I am stuck at aperiodic property of irreducible markov chain. Let us consider an irreducible markov chain. It's stated herein that for an irreducible markov chain, a single aperiodic state implies ...
2
votes
1answer
40 views

Markov Chain Detailed Balance property

I am having a hard time to understand the concept of the detailed balance; mostly because of the intermingled notation most of the resources use; which involves constant usage of random and state ...
0
votes
0answers
22 views

Question concerning invariant distribution

Let us consider the Markov chain $(X_n)_{n \in \mathbb{N}}$ with state space $I = \{0,1\}^m$ and transition probabilities $$ p_{xy} = \begin{cases} m^{-1} &\mbox{if } \vert x - y \vert = 1 \\ 0 ...
2
votes
0answers
26 views

Branching Process in simple random walk

Suppose we have a simple random walk on $\mathbb{Z}$ which stars at $1$, i.e. we have iid increment $X_n$ valued in $+1,-1$ with probability $\frac{1}{2}$ each and the sum $S_n=\sum_{i=1}^{n}X_n+S_0$ ...
0
votes
2answers
28 views

Determing a transition probability matrix

I need some support with this homework exercise: An urn contains at most $N$ balls. Let $X_n$ be the number of balls in the urn after the $n$-th execution of the following procedure: If the urn is not ...
0
votes
0answers
21 views

Is it true that $\tilde{P} = D^{\dagger} P D$ has non-negative entries?

Consider a $n \times n$ stochastic matrix $P$ (i.e. non-negative rows sum to one). We are interested in the matrix $\tilde{P} = D^{\dagger} P D$, where $D$ is a $n \times k$ matrix which is ...
0
votes
0answers
13 views

How to recompute the markov transition matrix given a reduction to the number of states? Clustering from a transistion matrix

I am been puzzled with this one for sometime. Given a transition matrix (as below) for a markov chain of N states; how do we calculate the transition matrix for N-1 states, where we combined stat n1 ...
-1
votes
1answer
32 views

Markov chain period

Let a Markov chain with State space $E=\{1,2,3,4\}$ and probability transition matrix: $$P=\begin{bmatrix} 0 & 1 & 0 & 0 \\ 1/4 & 0 & 1/4 & 1/2\\0 & 1& 0 & 0 \\ ...
1
vote
1answer
297 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
22 views

Finding the generating function of $H_{0}$ probability of hitting 0 in Markov Chain

Let $Y1 , Y2,...$ be independent identically distributed random variables with $\mathbb{P}(Y1 =1)=\mathbb{P}(Y1 =-1)=1/2$ and set $Xo=1,Xn =Xo+Y1+...+Yn$ for $n\geq1$. Define; $$H_o= inf\{n\geq0:Xn = ...
1
vote
1answer
36 views

What is the probability of arrive either A or B at starting point K?

There are two points which are $A$ and $B$. The distance between $A$ and $B$ is $50$ meter. One person goes to $A$ with probability $\frac{1}{6}$, he goes to $B$ with probability $\frac{3}{6}$. And he ...
5
votes
4answers
5k views

Why Markov matrices always have 1 as an eigenvalue

Also called stochastic matrix. Let $A=[a_{ij}]$ - matrix over $\mathbb{R}$ $0\le a_{ij} \le 1 \forall i,j$ $\sum_{j}a_{ij}=1 \forall i$ i.e the sum along each column of $A$ is 1. I ...
1
vote
0answers
22 views

Easy Question from Application: Estimate for transition probabilities of random walk - finding a coupling

SHORT VERSION: Find appropriate Coupling Suppose we have a random walk on the natural numbers, where we go to the left with probability $p_L \geq \frac{1}{6}$, to the right with probability $p_R\leq ...
1
vote
0answers
14 views

what's the potential application of low rank approximation of stochastic matrices

Suppose we have a stochastic matrix $P$ for a Markov chain, and we can compute a low rank approximation of $P$, say $P_k$, or we can find the nonnegative matrix factorization of $P$, i.e., $P=AW$ ...
3
votes
1answer
26 views

Generating Constrained Random Distributions

I am trying to help another StackExchange user. We are attempting to fill a 6x6 matrix with 12 A's, 12 B's, and 12 C's subject to the constraint that each row contains 2 A, 2B and 2 C and each column ...
0
votes
1answer
59 views

Can You Help Me With This Continuous Markov Chain Question?

Consider 2 machines, both of which have an exponential lifetime with mean $\frac{1}{\lambda}$. There is a single repairman that can service machines at an exponential rate $\mu$. Set up the ...
0
votes
0answers
8 views

Class properties Markov chain [closed]

How can we show that an open class in a Markov chain is transient (both for finite and infinite)?
2
votes
0answers
38 views

A(nother) variation of the coupon collector's problem

I have come across variation of the coupon collector's problem that goes like this. The coupons are of $n$ different types and in infinite number (or sampled with replacement after each draw, where ...
1
vote
1answer
554 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
26 views

Interesting question about markov chain [closed]

I just started with markov chains and i saw this question that looked really interesting, but i dont know how to solve it. Can someone help? Markov chain monte carlo
2
votes
0answers
39 views

Markov chain monte carlo

The target is to simulate a discrete random variable $Z$ with mass function satisfying $\mathbb{P}(Z=i)\propto \pi_i$, for $i\in S$ and $S$ countable. Let $X$ be an irreducible Markov chain with ...
0
votes
0answers
18 views

Interesting question about convergence of a Markov chain [closed]

I saw this question yesterday about convergence of a Markov chain, but I had no clue as to what the answer is and nobody replied, maybe someone can take a look? Convergence of a Markov Chain to the ...
1
vote
0answers
27 views

A 'mix' of simple and lazy simple random walk

Consider a $\mathbb{Z}$ valued markov chain $X_n$ which evolves as follows. $$P(X_{n+1}=y | X_n) =\begin{cases} \frac{1}{2}, y=X_n+1, X_n-1, |X_n|>K \\ \frac{1}{4}, y = X_n-1 , y= X_n+1, ...
0
votes
0answers
13 views

Markov chain simulation software

Does anybody know a software (applet) to simulate Markov chains (with finite values)? At least I want to be able to add states (like building a graph) with transition probabilities and it should ...
-3
votes
1answer
52 views

Markov chain problem 13 [closed]

I have this problem I don't understand, Can you help me, please?
3
votes
1answer
79 views

Frog on infinitely many lily pads (Markov chain)

A frog on pad $i$ hops to one of the pads $(1,2,...,i,i+1)$ with equal probability. I know that if the frog starts on pad $k$ the expected number of times the frog jumps, before returning for the ...
2
votes
0answers
32 views

Convergence of a Markov Chain to the normal distribution

If $i$ is a state of an irreducible, postive recurrent Markov chain $X$, and $V_n$ is the number of visits to $i$ between times $1$ and $n$, and further $\mu=\mathbb{E}_i(T_i)$ and ...
-2
votes
0answers
29 views

Interesting Markov Chain problem [closed]

I saw this question earlier and thought it was very interesting, but I've got no clue how to solve it: Frog on infinitely many lily pads (Markov chain) Can anybody help solve it?
2
votes
1answer
28 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 & ...
1
vote
1answer
23 views

Are Markov chains necessarily time-homogeneous?

I've seen a definition of Markov chains as a stochastic process $(X_t)_{t\in I}$ fulfilling the weak Markov property and having index set $I = \mathbb{N}_0$. But the weak Markov property ...
-1
votes
1answer
28 views

Birth and Death process, CTMC, how is the solution here derived? [closed]

My question is about how the solution is reached, as I am completely lost on how. Any thoughts? Consider a birth and death process with birth rates $λ_i = (i+1)λ \;\;, \;\; i≥0$, and death rates ...
10
votes
1answer
340 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
2answers
56 views

Difference between conditional expectation and conditional probabilty

These are known definitions: We have a probability space $(\Omega, A, P)$ Conditional probability is defined through $P(A|B) = \frac{P(A \cap B)}{P(B)}, P(B) > 0$. This is a real nunmber. Then ...
0
votes
2answers
30 views

Alternating Markov process

Given the situation: When Bob enters the room and the light is off, he turns it on with $P = 1/2$ when it is on, he does nothing. When Alice enters the room with light on, she turns it off with $P ...
0
votes
1answer
371 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 ...
-1
votes
0answers
24 views

In Markov chains, does $(I-N)^{-1}$ always exist? [duplicate]

Spins-off from these two questions. Under what conditions does $(I-N)^{-1}$ exist? If the entries of an invertible matrix N are between -1 and 1, is its operator norm less than 1? Apparently, in ...
0
votes
1answer
31 views
0
votes
2answers
56 views

what are “filtering” and “smoothing” mentioned in hidden Markov model wikipedia article?

the article mentions "filtering" and "smoothing" tasks, see here http://en.wikipedia.org/wiki/Hidden_Markov_model#Filtering . It gives brief explanation but no motivating examples and no references to ...
1
vote
1answer
30 views

Can You Help Me With This Markov Chain Question?

For a birth and death process with birth rates, $\lambda_i$ and death rates $\mu_i$ $(i=0,1,2...)$ respectively. Show that the transition probabilities, $P_{i,j}(t)$ satisfy the following differential ...
6
votes
1answer
96 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 ...
1
vote
1answer
13 views

Prove the following r-step transition

Let $X_0, X_1, X_2,...$ be a Markov Chain on state space $S=\{1, 2,..., n\}$ and let $P$ be the Transition Matrix of the above Markov chain Prove that $\Bbb{P}(X_{t+2}=j|X_t=i) = (P^2)_{ij} $ ...
3
votes
2answers
42 views

Markov chains diagram - what are the numbers above arrows?

Most if not all articles describe the numbers above arrows as probabilities of a transition in that direction, such as this one, or this one. But here, for example, something really weird is ...
2
votes
2answers
64 views

Under what conditions does $(I-N)^{-1}$ exist?

Given an nxn matrix N and $I=I_n$, under what conditions does $(I-N)^{-1}$ exist? On one hand $(I-N)(I + N + N^2 + ...) = (I + N + N^2 + ...) - (N + N^2 + ...) = I?$ On the other hand, $(I-N)(I + N ...
0
votes
0answers
23 views

Law of iterated logarithm for Markov Chains

Does anyone know where(or if) I can find a proof of law of iterated logarithm for irreducible and aperiodic Markov chain with finite number of states. All of the proofs I have seen so far are really ...