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
1answer
49 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 = ...
-1
votes
1answer
18 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
66 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
14 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
39 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
44 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
46 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
26 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
55 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
27 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
23 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
47 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
1answer
21 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
68 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 ...
2
votes
2answers
56 views

Transition Matrix eigenvalues constraints

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 ...
1
vote
1answer
71 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
41 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
24 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 ...
1
vote
0answers
22 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
14 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
42 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
35 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
63 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
14 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 ...
1
vote
2answers
56 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
1answer
50 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
231 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
61 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
9 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
130 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
141 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 ...
1
vote
0answers
38 views

Parametric transition matrix in Markov Chains

I am trying to model a discrete-time MC with transition probabilities that depend on some function of parameters i.e $p_{ij} = f(X_0,X_1)$. Suppose we take a log-linear model where $p_{ij} = ...
2
votes
1answer
51 views

Probability distribution of Poisson process

Let $X_t$ and $Y_t$ be two independent Poisson process with rate parameter $\lambda_1$ and $\lambda_2$, respectively, measuring the number of customers arriving in stores $1$ and $2$, respectively. ...
0
votes
0answers
69 views

proving null recurrence of random walk (Markov chain)

How would I prove that the zero state of a random walk with a positive probability of staying in the same state is null recurrent. (sorry if this isn't a random walk and just a Markov chain.) eg. ...
1
vote
0answers
51 views

Markov chain question

Consider an irreducible, recurrent Markov Chain ($X_n$) on a countable state space $S$ with transition probability $p(x,y).$ Pick a sigma-algebra $A \subset S$ and let $T_k=\inf\{n>T_{k-1}:X_n \in ...
1
vote
1answer
94 views

Markov chain problem, Help!

I am stuck on this question for a long time Question: Consider 4 balls, labelled from 1 to 4 and distributed amongst two urns (Urn 1 and Urn 2). At each time $n>1$, a number from 1 to 4 is chosen ...
0
votes
0answers
7 views

How can I calculate distribution of minima of sections of a continuous path (from a stochastic process)?

I have a long slab whose width is defined by a stochastic process, whose complete statistics I am aware of, say. I now cut it into smaller sections of uniform length, and calculate the minimum width ...
0
votes
1answer
28 views

Show $P(S_{2n}=x|S_0=x) \ge \frac{1}{N}$

Let $X_n$ be an aperiodic, discrete-time Markov chain so $S=\{1,...,N\}$ whose transition probability is symmetric. How can I show that for all $x \in S$ and all integers $n$, $P(S_{2n}=x|S_0=x) \ge ...
0
votes
0answers
112 views

understanding submartingale proof with discrete state space

I am reading a text about branching markov chains: My question is about the first half of page 8 where $Q(t)$ is proven to be a submartingale. Briefly the used notation: $t$ is discrete time, $n(t)$ ...
2
votes
0answers
11 views

$\psi$-irreducibility of m-skeletons.

In Proposition 5.4.5 of Meyn and Tweedie's Markov Chains and Stochastic Stability, it is said that if a chain $\Phi$ is $\psi$-irreducible and aperiodic, then every $m$-skeleton of it is also ...
1
vote
2answers
41 views

Looking for good literature on Markov Chains with explicit calculations

I am currently starting my thesis on Markov Chains and am looking for good books and papers that include explicit calculations. I have taken a small course on Markov Chains so the subject is not ...
2
votes
0answers
32 views

markov spectral radius independent of states?

Let $\Pi$ be a stochastic matrix of an irreducible markov chain. We define the spectral radius of $\Pi$ as: $\rho(\Pi) := \limsup_{n \to \infty} \left( \pi^{(n)}_{(a,b)} \right)^{\frac{1}{n}}$ Why ...
0
votes
0answers
16 views

Hidden Markov Model Confidence Interval (preferably in MATLAB)

I'm trying to uncover the transition parameters of data of a hidden Markov Model using MATLAB. Using the built in hmmtrain function, I can estimate the parameters quite well (I already know what they ...
5
votes
0answers
75 views

Spectral gap of mixture of Markov chains

Context Let $P$ be the transition matrix of an irreducible, aperiodic, discrete-time Markov chain. The spectral gap is given by $$\xi = 1 - \lambda_\max$$ where $\lambda_\max = \max\{\lambda_2, ...
2
votes
2answers
48 views

Generate random sample with three-state Markov chain

I have a Markov chain with the transition matrix $$\pmatrix{0 & 0.7 & 0.3 \\ 0.8 & 0 & 0.2 \\ 0.6 & 0.4 & 0}$$ and I would like to generate a random sequence between the three ...
0
votes
0answers
14 views

References for non-homogeneous continuous-time Markov chains

In one applied problem that I'm trying to solve, I want to apply nonhomogeneous continuous-time Markov chains. But cannot find a good reference on these kind of chains. I mean with simple worked-out ...
0
votes
1answer
52 views

Proving a chain is aperiodic, and finding a stationary distribution.

We have an irreducible Markov chain with a not necessarily finite state space. It has a transition matrix $P$ such that $P^2=P$. Prove (1) the chain is aperiodic, and (2) prove $p_{ij}=p_{jj}$ ...