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
40 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
53 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
36 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
29 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
29 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
144 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
48 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
118 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
32 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 ...
5
votes
2answers
338 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
15 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
23 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
30 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
22 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
14 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
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
31 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
30 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
59 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
21 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 ...
1
vote
2answers
23 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
30 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
36 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
61 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
34 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 ...
1
vote
0answers
21 views

Visualizing second-order Markov chain

You can visualize a first-order Markov chain as a graph with nodes corresponding to states and edges corresponding to transitions. Are there any known strategies to visualize a second-order Markov ...
0
votes
1answer
38 views

Markov Chains and Return Times

Let $(X_n)_{n≥0}$ be a Markov chain with transition kernel $p$ on a countable state space $S$, starting at $x∈S$ $T^{(1)}=\inf\{n≥1:X_n=x\} \quad \quad$ first return time to $x$ ...
1
vote
0answers
26 views

Markov decision processes with action space only revealed at point of decision.

I have a problem which looks like a finite horizon Markov decision process, except the actions space at each time is revealed at the decision making point. There is no way to know before hand the ...
0
votes
1answer
50 views

Understanding detailed balance equations

I'm trying to understand how the equilibrium distribution satisfy the detailed balance equation. To my understanding, I only understand that a detailed balance equation would only be satisfied if ...
4
votes
1answer
47 views

Finding Hitting probability from Markov Chain

I have a Markov chain with states {1,2,3,4,5} which has the following transition matrix: $$P= \begin{bmatrix} 0.3 & 0 & 0.7 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0.5 & 0 ...
5
votes
1answer
87 views

Compute a probability in Random Walk by Martingales

Let $X_n$ be the state at time $n$ of a Markov chain with these transition probabilities : $$p_{i,i+1}=p_i\qquad,\qquad p_{i,i-1}=q_i=1-p_i$$ $(a)$ Show that $Z_n=g(X_n)\,;\,n\geq0$, is a ...
1
vote
1answer
24 views

Characterization of conditional independence

Definition: Let $\mathcal{G},\mathcal{K},\mathcal{H}$ be $\sigma $-subalgebras of $\mathcal{F}$, where $\left( {\Omega ,\mathcal{F},\mathbb{P}} \right)$ is a given probability space. We say that ...
0
votes
2answers
42 views

Proof that steady state is not affected by initial distribution in Markov chain.

I was following a proof provided in Gilbert Strang's book "Introduction to Linear Algebra". And I am confused by one step of the proof. Suppose we have a $n$ by $n$ stochastic matrix $A$, where all ...
1
vote
0answers
18 views

Markov chains mixing time

Informally, the mixing time of a Markov chain is the time it takes to reach “nearly uniform” distribution from any arbitrary starting distribution. What does it mean by nearly uniform? I hope some one ...
0
votes
0answers
30 views

Perron Frobenius Theorem and Markov chains and more

I came across few ways of calculating convergence rates of Markov chains but I am a bit confused as to how these differ from each other and what may be the best way to calculate. The second ...
2
votes
1answer
62 views

Monotonicity and Convexity of Stochastic Matrices

The definition of stochastic monotonicity and convexity is given by "Stochastic Orders and Their Applications" by Moshe Shaked and George Shanthikumar (1994) as: Let $P = \{p_{i,j} \}$ be a ...
1
vote
2answers
50 views

Convergence time of a Markov chain

We know that a regular Markov chains converges to a unique matrix. The convergence time maybe finite or infinite. My interest is in the case where the convergence time is finite. How can we accurately ...
0
votes
3answers
87 views

How fast does this Markov chain converge?

Observe the above a Markov chain and limiting matrix of it. Finding the limiting matrix if it exists is easy but I am curious as to how fast this given matrix converges to its limiting matrix. Is ...
1
vote
0answers
27 views

A Central Limit Theorem to Markov Chains

I am looking for some textbook or paper that treats this question: Let be $X_{1}, X_{2}, \ldots$ the random variables from a Markov Chain (MC). Is there any Central Limit Theorem (CLT) envolving ...
0
votes
0answers
70 views

Application of Markov Chain to Game of Life Board Game

I need to calculate the expected outcomes for the Game of Life. I believe that if I multiply the probability of landing on a particular square with the payoff of said square and add up all these ...