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

Simultaneous multiple perturbations in Markov chain Monte Carlo

I'm coding a McMC algorithm for geophysical applications. Using the Metropolis-Hastings scheme to accept/reject the proposed models is smth that i thought i completely understood, but i don't. To be ...
0
votes
0answers
13 views

Control principal eigenvector of a row stochastic matrix

I am just trying to consider the classical discrete-time Markov Chain problem. Consider the transition matrix P, which transforms state vector $x(k)$ to $x(k+1)$, satisfying: $x(k+1)$ = $P*x(k)$ It ...
0
votes
0answers
12 views

Cesaro limit of stochastic matrices [on hold]

For a Markov chain, we can write the transition matrix as $$ P = \left( \begin{matrix} Q & R_1 & R_2 & \cdots & R_h \\ 0 & B_1 & \mathbf{0} & \cdots & \mathbf{0} \\ 0 ...
0
votes
1answer
15 views

Q-matrix vs. P-matrix description of a Markov chain

Consider a continuous time Markov chain $(X_t)_{t \geq 0}$ on some state space $S$ with transition matrix (P-matrix) $p_t(x,y)$, the probability density of jumping from $x$ to $y$ in time $t$. The ...
2
votes
2answers
23 views

Probability of returning to a given state after n transitions-Markov chains

Let us denote $f_j^{(n)}$ denote the probability of the first return to state $j $after n transitions. Let $p_{jj}^{(n)}$ be the probability of returning to the state $j$ after $n$ transitions when ...
1
vote
1answer
23 views

Symmetric random walk and the distribution of the visits of some state

I need help with this problem: Let $(S_n)_n$ a symmetric random walk in $\mathbb{Z}$ i.e $S_n=X_1 + \cdots + X_n$ with $(X_n)$ iid $\mathbb{P}(X_n=1)=\mathbb{P}(X_n=-1)=\frac{1}{2}$. Let $m \in ...
0
votes
1answer
71 views

How to make sense out of this: Ergodic theorem for Markov chains

We had the ergodic theorem for Markov chains, stating that: For a state space $S \subset \mathbb{N}$ and all functions $f \in L^1$ (meaning that $\sum_{s \in S} |f(s)|\pi(s) < \infty$) and an ...
3
votes
1answer
54 views

2D random walk variation

If a point on a 2D lattice is allowed to take a random walk by taking a unit step either up, down, left or right, there is probability $1$ of reaching any point (including the starting point) as the ...
1
vote
1answer
55 views

Need help with a basic exercise about Markov chains

Suppose $\left\{ X_{n}\right\} _{n=1}^{\infty}$ is a Markov Chain taking real values. Are the following Markov Chains? $$Y_{n}=\sum_{i=1}^{n}X_{i} , Z_{n}=\left(X_{n},X_{n-1}\right)$$ Edit1 I ...
0
votes
1answer
15 views

Is there a relationship between the mean matrix and the transition matrix of a multi type branching process?

Let $\mathbf{M}$ be the mean matrix of a multi type branching process $(\mathbf{Z}^{(n)})_{n\geq1}=((Z^{(n)}_1,\ldots,Z^{(n)}_k))_{n\geq1}$. This matrix is defined as follows $$M_{i,j}=\mathbb ...
0
votes
1answer
28 views

Long run behavior of a absorbing markov chain

$$A=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0.2&0&0.6&0.2\\0&0.2&0.2&0.6\end{pmatrix}.$$ In the above matrix how do I calculate the probability that in the ...
0
votes
1answer
19 views

Return Lemma MC

If a Markov chain is $\phi$-irreducible and has stationary distribution $\pi$, then $\phi\ll \pi$, Proof: We use the irreducibility of the chain to write the state space $E = \bigcup_{n,m \in ...
0
votes
0answers
38 views

Can ergodic Markov chains be periodic?

I found a statement in one of my notes which said If a state is persistent, aperiodic and not null the it is said to be ergodic Is it necessary that it should be aperiodic? This statement ...
1
vote
1answer
21 views

Markov chains: An issue in classification of states

I recently came across a lemma which goes as follows. Suppose a Markov chain has N states. Let i and j be pair of states. Then j can be reached from i iff there is an integer $ 0 ≤n< N$ such ...
0
votes
2answers
52 views

Expected number of steps to absorbtion - Markov chain

I want to calculate the expected number of steps (transitions) needed for absorbtion. So the transition probability matrix $P$ has exactly one (lets say it is the first one) column with a $1$ and the ...
0
votes
2answers
41 views

Given a Markov-chain, what is the probability of being at a given state?

Given a Markov-chain, what is the probability of being at a given state? I drew the diagram below just as an example, there is nothing special about it but it would be nice if your answer used it as ...
0
votes
1answer
34 views

How do you find the probability of a certain state in Markov Chain?

This question appears without answer in an old exam I found (not a homework question) Suppose messages that enter a system need to be processed by two servers. They arrive at the system at a ...
0
votes
0answers
14 views

Solution to linear system around the topic of Markov-chains

Let $(X_n)_{n\geq 0}$ be a Markov-chain with the state space $S$ and transition matrix $P=(p_{xy})_{x, y \in S}$. For $A\subset S$ be $H^A:=\inf\{n = 0, 1, \dots | X_n \in A\}$ the first visit time ...
0
votes
1answer
23 views

Are random walk variations Markov-Chains?

Let $S_{n}:= S_0 + \sum_{i=1}^{n}X_i$ be a simple random walk, $X_i$ are independent random variables with $P[X_i=1] = p, P[X_i = -1] = 1-p$. Let $M_n:=\max\{S_0, \dots, S_n\}$. The task at hand is ...
0
votes
1answer
23 views

Transition probabilities in a finite state machine

Assume I have a finite state machine and a bunch of tokens. Transitions happen every time a token is inserted. Transitions are based on the token (i.e. at state S, inserting a blue token would give a ...
9
votes
1answer
119 views

Can we qualitatively predict the strategy of the German and US teams in today's World Cup soccer match?

In today's World Cup soccer match between Germany and the US, both teams only need a draw to advance to the next round. There's been speculation about possible collusion, especially given the friendly ...
0
votes
0answers
9 views

Limiting Behaviour Transition Matrix

If I was given a transition matrix, and I want to know the limiting behaviour(limiting values) is there a "trick" or a quicker way instead of keep squaring my transition matrix? Also, if my only way ...
1
vote
1answer
46 views

First hitting time expectation and Markov property

Let $H_A$ be the first hitting time, such that $H_A\geqslant1$, so we have $X_0=i\notin A$. All texts I looked at, state without any further justification that $$ \mathbb E(H_A\mid X_1=j, ...
2
votes
2answers
109 views

Using Markov - Chain to find average and probability

Suppose a computer generate a random vector of n positions where each position appears on of the numbers from 1 to n. The generation is performed uniformly on the $n!$ possibilities. In the problem we ...
1
vote
1answer
28 views

Proving Product of Transition Matrices is again a Transition Matrix.

Let $P = [p_{ij}]$ be an $n\times n$ transition matrix for an $n$-state markov chain. How do you prove that $P^2$, or even better, that $P^n$ is again a transition matrix? My approach leaves me ...
-1
votes
0answers
15 views

Does a transition matrix has only real positive eigenvalues? [duplicate]

I am analyzing an ergodic Markov Chain of an $N\times N$ lattice grid and I have written down my Transition Matrix, i.e. all values are between $0$ and $1$ and the elements of each row sum up to $1$. ...
5
votes
2answers
328 views

In a tournament $n$ players take part in a series of duels

I've recently been thinking about this problem and I think I solved it correctly. However, I was using a rather peculiar method with lots of algebra. I'll post my solution as an answer below. Is there ...
1
vote
0answers
54 views

Use Hasting-Metropolis to generate a random element from a large complicated combinatorial set L

Let $P$ the set of all permutations $(x_1, \ldots, x_n)$ of numbers $(1, \ldots,10)$ and $L$ the subset of $P$ where $\sum_{j=1}^{n}jx_j> a$. To use Hasting-Metropolis algorithm I followed the ...
0
votes
0answers
13 views

Skew and Kurtosis of Absorbing Markov Chains

An absorbing Markov chain $P$ can be put in canonical form: $$ P = \left( \begin{array}{cc} Q & R\\ \mathbf{0} & I_r \end{array} \right), $$ where $Q$ is a t-by-t matrix, $R$ is a nonzero ...
0
votes
1answer
16 views

Writing down the transition matrix of a discrete Markov chain

Please consider the following scenario: One person is walking along a discrete circle induced by $\mathbb{Z}/n\mathbb{Z}$ In each round we roll a dice with $w\in\left\{2,\ldots n\right\}$ sides If ...
2
votes
0answers
25 views

Geometric ergodicity and mixing - stationary case

I have this theorem: The Markov Chain {$X_n$} is stationary and geometrically ergodic if and only if {$X_n$} is stationary and absolutely regular with $\beta_n=O(\gamma^n)$ for some $\gamma\in ...
2
votes
1answer
19 views

Applying transition matrix to a probability vector seems to ruin its normalization

I had a little bit about stochastic processes during my "Statistical Physics" course and on my exam I got a problem with a Markov chain. My solution seems to be without computational mistakes (checked ...
0
votes
0answers
12 views

Proof of mean recurrence time theorem in a Markov chain?

How can this formula been proven? $$\lim_{n\to \infty} p_{i,i}^{[n]} = {1\over \mu_{i,i}}$$ where $p_{i,i}^{[n]}$ is the probability that we've returned to state $j$ after $n$ steps in the Markov ...
2
votes
1answer
28 views

Markov chains by hand

If I have a starting point: $A_T=[0,1]$ at $T=1$ and a one step transition matrix of: $B=\left[ \begin{align} &\frac34 & \frac14& \\& \frac1{20}& \frac {19}{20} &\end{align} ...
0
votes
1answer
28 views

A discrete time Markov chain with such a transient state that $\mathbb P(T_i<\infty \ | \ X_0=i) \neq 0$

All examples of discrete time Markov chains my text provides are where $S$ is finite, and as far as I can tell, it makes all transient states have $$\mathbb P(T_i<\infty \ | \ X_0=i) = 0.$$ Are ...
0
votes
0answers
14 views

$(X_t)$, $(X_t,Y_t)$ Markov $\Rightarrow$ $Y_t$ Markov?

Is it true that if $(X_t)$ and $(X_t,Y_t)$ are both Markov chains, then so is $(Y_t)$. Otherwise which conditions could we impose on $X_t,Y_t$ so that this is true?
0
votes
1answer
22 views

Why does this hold for the mean hitting time?

Let $X$ be a Markov chain and $T_A$ the hitting time. My text uses this in a proof: $$\mathbb E[T_A \ | \ X_0=k ] = \sum_{l\in S} \mathbb P(X_1=l \ | X_0=k\ )(1+\mathbb E[T_A \ | \ X_0=l ])$$ and I ...
0
votes
1answer
27 views

Integration with respect to conditional measure?

Let $(X_n)$ be a Markov chain. For $i\in S$ my text defines $$N_i:=\sum_{n=0}^\infty \mathbf 1_{\{ X_n=i \}}$$ and then, as a part of a larger proof, claims that $$\mathbb E_i(N_i)=\sum_{n=0}^\infty ...
0
votes
1answer
27 views

Inferring transition rates from continuous markov chain question

A house has 2 rooms of similar sizes with identical air conditioners equipped with thermostats which turn on and off as needed to maintain the temperature in each room to a desired level of 22 ...
1
vote
1answer
56 views

random walk with sticky barriers

Consider a random walk on the line 1,...,d. You start at point 1. At each step you flip a coin: heads means go left, tails means go right. If you're at 1 and get a heads, just stay where you are ...
0
votes
0answers
16 views

Transition matrix in left-right hidden semi-Markov model

I'm developing a hidden semi-Markov model left-right . In a left-right model a sequence of $M$ states starts in state $1$ and ends in state $M$, with no repetition of states. Since the model is ...
0
votes
2answers
36 views

four state Markov chain

If there are four states:A,B,C,D. Probability of moving to the left is b and prob of moving to the right is a. If starting at state B, what is probability of arriving at state D? The hit says to ...
0
votes
0answers
23 views

Does Markov property imply $\mathbb P (X_n=i \ | \ X_0=j)= \mathbb P (X_{n+1}=i \ | \ X_1=j)$?

If the future depends only on the present and not on the past (aka Markov property), one could expect $$\mathbb P (X_n=i \ | \ X_0=j)= \mathbb P (X_{n+1}=i \ | \ X_1=j)$$ to hold. Is that true? I've ...
1
vote
0answers
32 views

Finding a probability measure

Could someone helpme with this problem? First, consider the transition kernel in $\mathbb{R^2}\times B(\mathbb{R})$ given by $K(x,A)=U_{S^1}(A-x)$. We can than define an other kernel in ...
1
vote
2answers
20 views

Can the ergodic theorem for Markov chains be proved with linear algebra?

This theorem is in my book, let me just say that it is for discrete-time Markov chains, that are time-homogeneous. Ergodic is defined in the book as being positive recurrent and aperiodic. The ...
0
votes
0answers
28 views

Probability of not reaching completion in Markov process

This question is supposed to be easy but is very hard for me. The Norwegian Skating Association has mass produced certain "collectors' cards" with all $N$ speedskaters (Norwegian as well as ...
0
votes
1answer
34 views

Markov chain exercise

Hello i have this Markov chain exercise: Basically we can always move up 1 step, but there is always a possibility that we will go down to the first state 0, the Markov chain consists of N states. ...
0
votes
1answer
57 views

The expected number of visits before hitting zero in simple random walk

I am learning Markov chains and encounter the following problem: Suppose in simple random walk, we start from state k. What's the expected number of visits to k before we hit 0? The book does not ...
0
votes
0answers
14 views

action of transition operator on function

Let $P$ be the transition operator of a markov chain with discrete time and discrete state space $X$. The action of the transition operator on a function $X \to \mathbb{R}$ is defined by $Pf(x) = ...
0
votes
1answer
33 views

Markov’s inequality

The annual return, R, of a certain stock is a random variable with mean 10. Use Markov’s inequality to obtain a bound for the probability of the stock return being at least 20. Assuming now that R ...