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

Can the transition probabilities of an inhomogeneous Markov chain be written as an exponential?

If $Z_t$ is a homogeneous continuous-time Markov chain with finite state space $E=\{1,\ldots,p\}$, transition matrices $(P(t))$ and intensity matrix $Q$, it holds that $$ P(t) = \exp(tQ), $$ see for ...
0
votes
0answers
17 views

Initializing MCMC walkers with ambiguous direction (-/+)

I'm running a sampler program where there are observations given as sample data which are derived from an equal sized population of parameters that are converted to the observations using a known ...
2
votes
1answer
26 views

Finding the probability of ever visiting a transient state for a zero-seeking device for a Markov Chain?

A zero-seeking device operates as follows: if it is in state $j$ at time $n$, then at time $n+1$, its position is $0$ with probability $\frac{1}{j}$ or $k$ with probability $\frac{2k}{j^2}$, where $k$ ...
1
vote
1answer
14 views

Producing a transient & recurrent example for a birth-death chain with a more complex relationship between the $p_x$ and $q_x$.

Suppose we have a birth-death chain with a state space $$ S = \{0,1,2,\ldots\} $$ and transition probailities: $$p(x,y)=\begin{cases}q_x, &\text{if } y = x-1, &\text{i.e. death}\\ ...
1
vote
0answers
21 views

A question about Markov

There is a continuous-time markov chain,and we know the probability transition matrix P.The time between 2 states can be formulated as a exponential distribution whose u is related to the 2 states.Now ...
0
votes
1answer
29 views

Board Game Markov Process - Transient Probabilities

I need to write an essay on the Game of Life board game, and so I studied up on Markov Chains to help me calculate the probabilities and average payoffs for the spaces; however I'm not sure whether ...
1
vote
1answer
23 views

DTMC random walk [closed]

For a discrete Markov chain random walk with p < 0.5 with state space S= {0,1,2..} What is the stationary distribution? I could use any help. Thank you
0
votes
0answers
14 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
1answer
25 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
1answer
25 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
25 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
57 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
56 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
17 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
29 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
39 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
42 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
16 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
24 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
127 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 ...
-1
votes
0answers
13 views

Limiting Behaviour Transition Matrix [closed]

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
111 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
29 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
332 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
17 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
26 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
20 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
13 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
19 views

$(X_t)$, $(X_t,Y_t)$ Markov $\Rightarrow$ $Y_t$ Markov? [closed]

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
23 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
28 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
29 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
17 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
37 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
33 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 ...