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

Computing the PMF for N(t) in a renewal process

I'm in a stochastic processes course, and we just started on renewal theory. Unfortunately, we skipped the section on queuing theory, and nearly example in my textbook for renewal processes uses ...
1
vote
1answer
12 views

Strict proof of markovity of queing system of type $M/M/n/\infty$

I have a queing system of type $M/M/n/\infty$. The service time is exponential, and the arrival process is poisson. I do understand that because of these two facts the future of the system in ...
1
vote
0answers
20 views

Markov Chain Ergodic Theorem (Proof references)

Where can I find a proof of the erogidc theorem for Markov chains that doesn't use Birkhoff? The theorem states the following : Let $(X_n)_{n\in \mathbb{N}}$ be an irreducible and positively ...
0
votes
0answers
10 views

Discrete Time Markov Chain Proof Question

My instructor stated this result without proof, and I don't know enough about Markov Chains to 'Google' the name of theorem, but if anyone has a reference or a method of proof I'd appreciate it. The ...
1
vote
0answers
13 views

$X_n, n> 0$ is a Markov Chain, how to interpret $Z_n = (X_n,X_{n+1}), n > 0$?

Am a newbie to Markov Chain. So, this might be incredibly naive/stupid question. If $X_n, \, n > 0$ is MC, am having difficulty imagining/interpreting process $Z_n = (X_n,X_{n+1}), n > 0$. I ...
0
votes
1answer
13 views

Recurrence of infinite markov chain

I have a Markov chain with state space $S=\{0,1,2...\}$ and a sequence of positive numbers $p_1,p_2,...$ where $\sum p_i=1$. The transition probabilities are based on these where $p(x,x-1)=1, ...
0
votes
1answer
7 views

First property of discrete time homogenous markov chain

I'm trying to understand the properties of a DTHMC. I am having trouble understanding with the first one. My textbook says - "$X_t$ takes values in $X$ for all $t$ (i.e. $X_t$ is a random variable ...
1
vote
0answers
20 views

markov chain computation

I consider a 2 state Markov chain: $X = \{1,2\}$, transitions are $M(i,j)$ and the matrix has a unique stationnary distribution $\pi$: $$ \pi(1) = \frac{M(2,1)}{2-M(1,1) - M(2,2)} \\ ...
0
votes
0answers
23 views

Markov Chain Geometric Convergence

Perhaps due to my non-mathematician background (lack of Measure Theory knowledge), I have some difficulties about the Markov Chain Theory. Given an ergodic (irreducible and aperiodic) Markov Chain ...
0
votes
1answer
22 views

Markov chain probability that a state changes

For the Markov chain given below what is the best way to find the probability P{$x_n = x_{n-1}$} and P{$x_n \neq x_{n-1}$} The transition matrix of the chain is \begin{array}{} 1/3 & 2/3 & ...
0
votes
1answer
13 views

M/M/1 queue with probability of new client leaving

I'm looking at a M/M/1 queue system and trying to show that $\{M_t\}_{t\geq}0$, the number of clients in the system, is a birth-death process. In the simplest of cases this is true if $\lambda_i = ...
0
votes
0answers
12 views

radius of symmetric random walk on $\mathbb{Z}$

How to calculate the radius of the symmetric random walk on $\mathbb{Z}$, i.e. $\limsup_k (p^{(k)}(0,0))^\frac{1}{k}$? ($p^{(k)}(0,0)$ denotes the probability to get from $0$ to $0$ in $k$ steps and ...
1
vote
1answer
43 views

Proving that Markov Chain Monte Carlo converges

I am trying to understand how the very basic Markov Chain Monte Carlo approach works: We try to approximately calculate the expected value $E_{\pi(x)}[X]$ by drawing sequential samples from a Markov ...
1
vote
0answers
11 views

Are there any models that have mean $\sqrt{t\log(t)}$?

R. Arratia (The Motion of a Tagged Particle in the Simple Symmetric Exclusion System on Z) shows in theorem 2 that for step initial condition in the SSEP, the position of the lead particle, $x_1(t)$ ...
3
votes
0answers
28 views

Invariant measure of Euler-Maruyama Discretisation of an Ito diffusion

Let $(X_t)_{t \geq 0}$ be a diffusion process with dynamics governed by the stochastic differential equation \begin{equation} dX_t = b(X_t)dt + \sigma(X_t)dW_t, ~~ X_0 = x_0, \end{equation} where ...
0
votes
1answer
32 views

Conditional mutual information and Markov chain.

If we have the Markov chain $X \to Y \to Z$, or equivalently $$I(X;Z| Y)=0, \tag{1}$$ where $I(\cdot)$ denotes the mutual information. Does the Markov chain $X \to (Y,W) \to Z$ also hold? Or ...
1
vote
1answer
38 views

Stickers in a box Markov chain problem

I'm revising for exams in June and my university, very irritatingly, doesn't provide mark schemes for past questions. I'm stuck a few parts into a question and am not totally confident of my preceding ...
0
votes
0answers
11 views

Gibbs sampler for MCMC is equilibrium distribution

Consider a Gibbs sampler, as in https://en.wikipedia.org/wiki/Gibbs_sampling, which we use to generate a Markov chain $x^0, x^1, x^2,...$ which samples from a distribution $\pi$. If we call ...
0
votes
0answers
25 views

Markov chain definition: should the conditional probability also hold if $P(X_{n} = i_{n}, \ldots, X_0 = i_0) = 0$? Is $S$ a set of real numbers?

Definition of Markov Chain (as it is stated in my textbook): Let $S$ be a set of states and $\mathbb P = \{p_{i,j}\}$, $i,j \in S$ a transistion matrix . Then the sequence of RV's $(X_{n})_{n \ge 0}$ ...
1
vote
1answer
20 views

rate of convergence of absorbing markov chain

Let $G$ be a biconnected and non-bipartite graph. I can simulate a random walk on this graph with a markov chain. The stochastic matrix is $M = AD^{-1}$, where $A$ is the adjacency matrix of $G$ and ...
0
votes
1answer
20 views

Steady state of a $4 \times 4$ transition matrix

Normally I just take $q(M_{m\times n} - I_{m\times n})$ to workout the steady state, but here I have: $$\left(\begin{array}{rrrr} 0 & 0 & .8 & .2 \\ .4 & .6 & 0 & 0 \\ .2 ...
0
votes
1answer
17 views

Limiting probability of Markov chain(Terminology)

If I am asked to find the limiting probability of a Markov chain, what does this pertain to? $\lim \limits_{n \to \infty} P^n$? Where $P$ is the stepping matrix and $n$ is the number of steps. "What ...
1
vote
0answers
26 views

How's the damping factor in Google PageRank algorithm calculated

I'm doing some researches about Google's PageRank algorithm for my thesis, I've found that the damping factor x (for example), where x is in : P` = x.P + (1-x)Q where P is the original ...
1
vote
0answers
25 views

showing a condition implies convergence to invariant distribution

For an arbitrary Markov chain, I'm trying to show that $\lVert{ P_{\mu}\circ \theta_n^{-1} - \nu \rVert}\to 0$ iff $\sum_j \lvert{ P_{ij}^n - \nu(j)\rvert}\to 0$, where $\theta_n^{-1}$ is a shift ...
0
votes
0answers
19 views

Discrete Markov Chain: probabilities

I'm confused about these: steady-state transition probabilities limiting probabilities stationary probabilities how are they different? I know the question is pretty vague, but I feel like I'm ...
0
votes
1answer
17 views

limiting probability - what matrix to write

To find the limiting probability you solve the systems of equations: $\vec{\pi}=P\vec{\pi}$ $\Sigma \pi_j = 1$ and my teacher told us "you could rewrite this as matrices". Having just completed a ...
1
vote
0answers
55 views

Markov Process Feller Construction

I have this assignment question and I am stumped on how to complete a Feller construction: A system consisting of two components is subject to a series of shocks . The time be- tween consecutive ...
1
vote
2answers
24 views

Transition Matrix eigenvalues constaints

I have a Transition Matrix, i.e. a matrix whose items are bounded between 0 and 1 and either rows or columns sum to one. I would like to know if it is possible that in any such matrices the ...
0
votes
1answer
26 views

Mean time spent in transient states/Markov chain

I dont get this in my book: For transient states $i$ and $j$ , let $s_{ij}$ denote the expected number of time periods that the markov chain is in state $j$ , given that it starts in state $i$. Let ...
3
votes
0answers
34 views

Markov chains and natural filtration

I have the following problem Consider a homogeneous Markov chain $(X_n)$ with countable state set $E$. Suppose that $A$ is a proper subset of $E$ and consider the stopping times $\tau^0=0 $ and ...
0
votes
1answer
15 views

How many iterations are generally required when using the power iteration method?

Suppose I have an n x n matrix and I want to find the dominant eigenvalue and its associated eigenvector. Given these dimensions, what is the minimum number of iterations of the power iteration ...
0
votes
0answers
20 views

How to get from this probability formula to the one I need?

I'm working on a gambler's ruin problem where a player starts out with $i$ money, and 'winning' is when their total money reaches $N$ (ie they will keep playing until they reach N or run out of money, ...
0
votes
0answers
11 views

Markov chains - Proof of how to check recurrent states

Question 1 I read a proof of how to check recurrent states. There is one = sign that I do not understand, see the image. ...
3
votes
0answers
30 views

Standard deviation of a quantum walk?

The standard deviation of a classical random walk with $n$ steps is $\sqrt n$ - Standard deviation of a random walk. I have read in many places that the standard deviation of a quantum walk $n$ with a ...
0
votes
1answer
30 views

Markov chains for group decision making

I am new to Markov chains since I am doing my own studying on it recently. I was doing some questions and came across this one that got me stuck. Suppose there are four employees and they need to ...
2
votes
1answer
51 views

continuous time Markov chain, something the book does not explain

I have a problem with something in my book, under the chapter of continuous time Markov chains. I will post a link to what the book does. They do something which they seem to take for granted, but I ...
0
votes
0answers
11 views

radius of markov chain

For an irreducible markov chain one can show, that $\limsup \sqrt[n]{p_{ij}^{(n)}}$ is independent of the choice of the states $i$ and $j$ where $p_{ij}^{(n)}$ is the probability to get from $x$ to ...
0
votes
0answers
14 views

Sapling/ counting order ideals

Is there anything known about sampling or counting ordered ideals in Posets of special cases?
1
vote
2answers
44 views

A Card game problem related to Markov chain

This card game problem originates from the killer game Sanguosha. We assume that all cards drawn in the game procedures below are with replacement, in order to keep the probabilities fixed when a card ...
1
vote
0answers
13 views

condition for recurrence of the chain

Let $\{X_n\}$ be an irreducible Markov chain with transition probability $P=(p_{ij})$ on a countable state space $S=\{0,1,2,\dots\}$.Suppose $s\in S$.Show that $s$ is a recurrent state if the there is ...
0
votes
0answers
16 views

Random Walk Prediction on a grid using markov chain

We have a m*n Grid and n no of robots in that grid which would perform a random walk simultaneously.Each robot can move in 4 direction specifically Up, Left, Down, Right. After x steps the random ...
0
votes
0answers
22 views

Transition matrix, stationary distribution and expected number

A company wants to operate s identical machines, but they are subject to failure according to a given probability law. To replace them, the company orders new machines at the beginning of each week to ...
0
votes
0answers
41 views

Expected time to reach 6th return time of Markov Chain

I'm having a hard time figuring out this problem from Resnick's Adventures in Stochastic Processes: Harry is negotiating a new tv show and the negotiations follow a discretely indexed Markov chain. ...
0
votes
1answer
47 views

Markov chain with infinite number of transient and positive recurrent states?

Is it possible to have a markov chain with an infinite number of transient states, and an infinite number of positive recurrent states? Thank you!
0
votes
2answers
221 views

Prove markov chain is null recurrent

Two fair coins are tossed repeatedly. Let Xn denote (Total Number of Heads from Coin 1)-(Total Number of Heads from Coin 2) after n tosses. Thus the state space is {0, ±1, ±2, .... }. Show that the ...
2
votes
2answers
119 views

How do you prove that the second largest number $Y_n$ shown among the first $n$ rolls is not a Markov Chain?

How do you prove that the second largest number $Y_n$ shown among the first $n$ rolls is not a Markov Chain? My attempt: Consider the case, $P(Y_{n+1}=3|Y_n=1)=\frac{1}{6}$ if the current ...
0
votes
2answers
41 views

Find steps to reach absorbing markov chain state

How can I find the steps it takes or days or whatever the time variable is till the matrix reaches the absorbing state. e.g. take the matrix (The probability of each column adds to 1) $$ \left[ ...
0
votes
0answers
8 views

How are Markov chains used in simulated annealing?

How are Markov chains used in simulated annealing? Is it only that the cooling scheme can provide ergodicity?
2
votes
2answers
71 views

Professor has 4 umbrellas, Markov chain and Probability

OK this problem is making me tear my hair out. I need someone to walk me through this in baby-steps method like 1 + 1 = 2. I am trying to figure out what I don't understand. I know this is going to be ...
2
votes
2answers
59 views

Mean recurrence time and stationary distribution of a Markov chain?

In a Markov chain is there a theorem relating the existence of the stationary distribution and the mean recurrence time? E.g. impossible for stationary distribution to exist therefore mean recurrence ...