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
0answers
8 views

Markov chain convergence without total variation norm

Can this theorem be reformulated so that the total variation norm $\|\cdot\|_{TV}$ is not used?
1
vote
1answer
8 views

Interperetation of tau in marokov chains

I'd like to ask you a question about the meaning of certain equation in my exercise. This concerns Markov Chains I have: $\tau =inf\{n>=1:X_n\in\{3,5\}\}$ and I have to calculate $P(\tau=1)$ ...
2
votes
1answer
30 views

Using a markov chain to calculate the expected value of conditional/constrained choices (TopCoder PancakeStack)

I've been working on a programming challenge (link) where an expected value is calculated. Recently I learned about Markov chains and successfully applied them to solving a set of problems, but the ...
1
vote
0answers
21 views

Compute the stationary distribution of a Markov Chain on an infinite state space

I have a Markov Chain on $\mathbb N_0^2$ with a given initial state $(x_0,y_0)$. The allowed transitions for example are of the following form: $(x,y) \mapsto (x-1,y+2)$ with probability $\propto x$ ...
-2
votes
0answers
21 views

Markov Chain with transition matrix $Q=(I+P)/2$ [on hold]

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
38 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 ...
0
votes
1answer
13 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
17 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
0answers
28 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
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 ...
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
14 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
33 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
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 = ...
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 ...
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 ...
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
15 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
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 ...
-2
votes
0answers
27 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
40 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, ...
2
votes
0answers
34 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 ...
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 ...
3
votes
1answer
89 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 ...
-1
votes
1answer
29 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 ...
-3
votes
1answer
54 views

Markov chain problem 13 [closed]

I have this problem I don't understand, Can you help me, please?
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 ...
-1
votes
0answers
25 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 ...
3
votes
2answers
43 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 ...
0
votes
0answers
24 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 ...
0
votes
1answer
31 views

If the entries of an invertible matrix N are between -1 and 1, is its operator norm less than 1?

For Euclidean norm. If so, why? If not, might $(I-N)^{-1}$ exist some other way? This spins-off from here.
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} $ ...
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
1answer
32 views

Distribution of particles at infinite time

Let any site of $\mathbb{Z}$ host a number of particles $\eta_0(x)$ which is distributed according to some probability distribution independently and identically for any site $x \in \mathbb{Z}$. At ...
0
votes
0answers
4 views

Long time statistics of random functions

I'd like to understand if an average over random functions can be approximated with a Markov process in the long-time limit. Let $$ X_t = \sum_k a_k \cos(\omega_k t + \phi_k) $$ a random function, ...
0
votes
0answers
16 views

Computing Steady State Probability for 3 state markov chain

I have the equation $\frac{d}{dt}\vec{p(t)} = \vec{p(t)}Q$ here Q is a 3x3 transition matrix. $\vec{p} = (p_a,p_b,p_c)$. I have already solved Q where each row sums to 0. I have been trying to find ...
0
votes
0answers
29 views

Is this type of Markov chain known?

I am looking at a situation where we have $N$ urns and $K\le N$ balls. Consider some allocation of the balls to the urns. When any urn contains two or more balls, we call it a colliding urn. The ...
1
vote
0answers
30 views

Understanding the strong Markov property

I have problems to understand the strong Markov property (Klenke, p. 356): Let $I \subset [0,\infty)$ be closed under addition. A Markov process $(X_t)_{t\in I}$ with distributions $(\mathbf{P}_x, ...
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 ...
-2
votes
0answers
55 views

Random walk of a bishop [closed]

If an erratic bishop starts at bottom left of a chessboard and performs random but legal moves (all with equal probability and independently of earlier moves) and $X_n$ is the positon after $n$ moves, ...
0
votes
1answer
25 views

Absorbing Markov chain when less transient states than absorbing states

I have a probability matrix: 1 2 3 1 0.5 0.3 0.2 2 0 1 0 3 0 0 1 I understand that: $$ Q = \left(\begin{array}{c} 0.5 \end{array} ...
0
votes
1answer
20 views

How to calculate steps of a Markov chain with an unknown probability?

I have the matrix: A B C A 0.80 0.10 0.10 B 0.2 0.75 0.05 C 0.10 0.10 0.80 They ask me: if $ A $ is 40% right now, what's the probability of $A$ ...
0
votes
1answer
16 views

Formula for average time in Markov chain

I have a model like: A B C A 0.80 0.10 0.10 B 0.20 0.75 0.05 C 0.10 0.10 0.80 How do I get the average time from B to A? I understand that ...
0
votes
0answers
2 views

Simple Hidden Markov Model with Autoregressive Structure - Estimation?

I observe a two series over time $Y_{1:T}=\{ Y_{1}, \dots, Y_{T}\}$ and $X_{1:T}=\{ X_{1}, \dots, X_{T}\}$ where the $X$ series supposed to be exogenous (I do not define any stochastic proecess for ...
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 ...