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
vote
0answers
30 views

Conditional return time of simple random walk

Consider a simple random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$, with $S_0 = 0$. The probability to jump to the right neighbour is $p \geq \frac{1}{2}$. Call $\tau_k = \min\{t \in \mathbb{N}\, : \, ...
1
vote
1answer
65 views

Markov Chain with Memory

One of the defining characteristics of a Markov Chain is that it is memoryless: the next state depends only on the current state, and not on the set of preceding states. I'm looking for a ...
1
vote
2answers
69 views

Measuring the entropy of a graph representing a transition probability matrix of a first order markov chain

There's a research project i'm currently working on which requires me to analyze various aspects of "worlds" represented by transition probability matrices, where the nodes represent objects in the ...
0
votes
0answers
15 views

For a general absorbing markov chain, if we have that $I-Q$ can be inverted, is it possible to prove the chain covers all stationary distributions?

If I have a general absorbing markov chain, there are nice properties when $I-Q$ is invertible. In my book, it claims it can be shown that a vector: $(0,0,0,...,0,v_1,...,v_{N-r+1} \in ...
0
votes
0answers
39 views

Exact probability distribution for hitting time of simple random walk

Consider simple random walk on the line starting from the site $y \in \mathbb{N}$. With probability $p$ the walker moves to the right and with probability $1-p$ to the left. Call $\tau$ the first time ...
0
votes
1answer
55 views

Application of Conjugate Gradient Method to non-symmetric matrices

I am currently working on a problem in which I am using the Conjugate Gradient method to solve for the steady state solution of a continuous time Markov chain. I am applying the algorithm found in ...
2
votes
1answer
36 views

Green's function of a Markov Chain, and maybe of a Feller Process?

How are the Green's functions of a Markov chain related to the notion from PDE theory? For instance, if the Markov chain (i.e. discrete state space) is continuous time, then the Green's function I'm ...
0
votes
0answers
41 views

Proof of Hammersley and Clifford theorem in Besag's paper

I am reading Besag's paper on Spatial Interaction and the Statistical Analysis of Lattice Systems, see http://www.cise.ufl.edu/~anand/fa11/Besag_Spatial_interaction.pdf. In section 3, it introduces ...
0
votes
1answer
78 views

Continuous time markov chains, is this step by step example correct

I have some questions regarding CTMC... and most importantly whether the step-by-step example I provide below is correct. My main sources about CTMC are: ([1], and [2]). Let's assume 3 possible ...
2
votes
1answer
44 views

Why left multiplication when it comes to Markov chains?

When working with Markov chains and transition matrices $P$ we multiply from the left, meaning that for example $\mu^{(n)} = \mu^{(0)}P^n$ or that the stationary distribution satisfies $\pi = \pi P$. ...
0
votes
1answer
53 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
19 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
47 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
29 views

Producing transient and recurrent examples for birth-death chains with mixed birth- and death-probabilities

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
27 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
44 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 ...
0
votes
0answers
19 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
39 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 ...
1
vote
1answer
39 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
25 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
41 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
76 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
75 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
66 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
18 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
34 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
21 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
44 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
25 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
64 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
45 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
37 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
17 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
48 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
41 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 ...
10
votes
1answer
172 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
vote
1answer
57 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
123 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
48 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 ...
6
votes
2answers
344 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
55 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
16 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
35 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
35 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
24 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
17 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
30 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
32 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
1answer
30 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
33 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 ...