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

5
votes
0answers
74 views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N ...
5
votes
0answers
77 views

Confusion in the proof of properties for $\psi$-irreducibility

Let $P$ be a stochastic kernel on a measurable space $(\mathsf X,\mathfrak B(\mathsf X))$. The kernel $P$ is called $\varphi$-irreducible if for a positive measure $\varphi$ and for all measurable ...
5
votes
0answers
207 views

Potential theory: discrete-time Markov processes

Recently I've found lecture notes on "Analysis on Graphs" where the potential theory methods were used to study discrete-time, time-reversible Markov chains (i.e. the state space is countable). ...
4
votes
0answers
60 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, ...
4
votes
0answers
121 views

Conditional probability and integrating out part of a random walk

Suppose that I have a random walk process defined by $\alpha_{t+1}$ ~ N$(\alpha_t, \omega^2)$. Given $\alpha_t$ and $\alpha_{t+2}$, I understand why the conditional formula for ...
4
votes
0answers
161 views

estimation of transition probabilities from aggregate data

Please, O mathematicians, help me understand the approach to the problem of estimating transition probabilities given only aggregate data in Kalbfleisch & Lawless' 1984 paper "Least-Squares ...
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 ...
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 ...
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 ...
3
votes
0answers
61 views

Markov Chain Alternate Expectation

Consider a Markov chain defined by transition matrix $P$ such that for each transition from state $i\rightarrow j$ the probability is $p_{ij}$. Now say there is an associated value for each transition ...
3
votes
0answers
50 views

A Continuous-Time Markov Process Taking All Possible Values

Let $\mathbb{N}$ be the set of positive integers. For each $n \in \mathbb{N}$, let $X^{(n)}=\{ X^{(n)}(t): t \geq 0 \}$ be a Markov chain with state-space the two point set $\{0,1\}$ and $Q$-matrix ...
3
votes
0answers
83 views

SLLN of Markov chains .

Let $X_1$, $X_2$,... be a finite state, irreducible and aperiodic Markov chain with initial state $X_0=i$. It is known that \begin{equation} \mathrm{P}\Big\{\lim_{n\rightarrow\infty} ...
3
votes
0answers
85 views

Prove the 2 definitions of the periodicity of Markov Chain are equivalent.

In many textbooks, there are basically 2 ways of defining the periodicity of Markov Chain. One is by partitioning the graph in to subgraph such that transition in one group of state leads to the other ...
3
votes
0answers
90 views

maximum renewal rate of a Markov chain

Consider a Markov chain $(X_t)$ on a state-space with a countably generated $\sigma$-algebra and assume this Markov chain allows for small sets of order one. This means there exist sets $\mathfrak{S}$ ...
3
votes
0answers
128 views

Generalization of Dobrushin's Ergodic Decomposition for continuous Markov Chains

Let $T$ be the shift transformation. Let $P$ be invariant for $T$ and also define a discrete state space Markov Chain. Let $C_{1},\ldots,C_{n}$ be the connected components of the Markov Chain. It ...
3
votes
0answers
30 views

Name for maximum transition probability

Let $p(x,y)$ denote the transition probability of a markov chain. Similarly, let $p^n(x,y)$ be the n-step transition probability. My question is, is there a formal name for $S(x,y):=\sup_n p^n(x,y)$. ...
3
votes
0answers
56 views

When is this reversible diffusion on the integer lattice non-exploding?

Let $U\in C^{\infty}(\mathbb R^n;\mathbb R)$ and consider a continuos time Markov chain on the scaled integer lattice $\delta\mathbb Z^n$ with jump rates given by $r_{\delta}(x,y) := \begin{cases} ...
3
votes
0answers
226 views

Probability question about change in vending machines; maybe markov chain?

Suppose there are vending machine that sells its goods for $3$. It's known that a third of the buyers use three coins of $1$, a third of the buyers use $2$ and $1$, and the last third use $5$. The ...
2
votes
0answers
6 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 ...
2
votes
0answers
31 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 ...
2
votes
0answers
70 views

simple proof of the $L^2$ weak law for discrete-time ergodic Markov processes

Let $\{X_t\}_{t\in\mathbb{Z}}$ be a stationary and ergodic stochastic process with finite second moment. Von Neuman's ergodic theorem implies that the time average $(1/N)\sum_{j=0}^{N-1} X_j$ ...
2
votes
0answers
56 views

Intuition behind criterion for an irreducible Markov chain to be transient

I have been looking over my notes for Markov chains, and I have come across the following: Theorem: An irreducible Markov chain is transient iff for some state $i$ there exists a nonzero vector $y$ ...
2
votes
0answers
91 views

Monotonic convergence of powers of a stochastic matrix

Let $P$ be a stochastic matrix (nonnegative and each row summing to 1). Assuming that $P^n$ converges to $\textbf{1}\pi$ as $n \rightarrow \infty$, where $\pi$ is a row vector (stationary distribution ...
2
votes
0answers
94 views

Markov chain from Poisson

Let $K_t$ be a Poisson process with rate $1$ and $X_n=K_n-n$ $, \ \ \ n\in \mathbb{N}$ am asked to determine whether it is null or positive recurrent, we already know it is recurrent. I ...
2
votes
0answers
152 views

Boundedness of expected reward Markov chain (may be related to discret $M/M/\infty$ queue)

[EDIT]: I read a bit on $M/M/\infty$ queue and it may not be the right comparison and my notation may be confusing (I'm in discrete time and $\lambda,\mu$ look likes rates when they are probability). ...
2
votes
0answers
23 views

Ruin time with a maximum purse size

Imagine I have a gambler's ruin scenario where I start with $m$ dollars and I cannot have more than $N$ dollars. For each of however many rounds, I flip a coin, and with probability $p$ I win a ...
2
votes
0answers
26 views

Broken disk head

Broken disk head: We would like to read 1 byte = sequence of 8 bits from a disk, starting from bit 0. Our disk head reads 1 bit at a time. Disk head can only move forward, but after reaching bit 7 ...
2
votes
0answers
68 views

Is the following interpretation for the stationary distribution of a Markov process correct?

Imagine I have some Markov process with stationary distribution $\pi$ and a mixing time of $\tau$ after which $|Prob[x=s_i] - \pi(s_i)| \leq \epsilon$. Can I assume the following: A state $(x=s_i)$ ...
2
votes
0answers
18 views

Problem with the uniform transience

Let $X$ be a Borel space and let us consider a Markov Chain $(\Phi_n)_{n\geq 0}$ on this space given by the stochastic kernel $$ P(x,\mathrm dy) = p(x,y)\mu(\mathrm dy) $$ where the density $p$ is ...
2
votes
0answers
169 views

Computing the stationary distribution of a markov chain

I have a markov chain with transition matrix below, $$\begin{bmatrix} 1-q & q & & & \\ 1-q & 0 & q & & \\ & 1-q & ...
2
votes
0answers
156 views

Ergodicity and mixing

From MathOverflow, R W said: Unfortunately, the way the term "ergodic" is used in the theory of (finite) Markov chains is completely misleading from the point of view of general ergodic ...
2
votes
0answers
556 views

Classifying a Stochastic Process as transient, null-recurrent or positive-recurrent

For a discrete time Markov chain with state-space the non-negative integers, for $j>0$, $$ p_{j,k} = \begin{cases} p/j & \text{for } k = j+1 \\ 1 - 1/j & \text{for }k=j \\ (1-p)/j & ...
1
vote
0answers
17 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 ...
1
vote
0answers
19 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)} \\ ...
1
vote
0answers
10 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)$ ...
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 ...
1
vote
0answers
51 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
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 ...
1
vote
0answers
33 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} = ...
1
vote
0answers
45 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
0answers
53 views

Markov Chains: Limiting probabilities of positive recurrent states sum to one?

I have a question about Markov chains. I am trying to understand the proof of Proposition 2.6 of http://www.columbia.edu/~ks20/stochastic-I/stochastic-I-MCII.pdf. The setting is: we have a positive ...
1
vote
0answers
18 views

Finite state Markov chains and expectations

Let $X_t$ be a finite state Markov chain with generator matrix $Q$. For a give function $f(x)>0$ define: $$ u(t, i) = \mathbb{E}\left[\int_t^T f(X_s) \mathrm{d} s| X_t = i\right] $$ Are there any ...
1
vote
0answers
32 views

Markov Chain depicting unruly customer behavior

A store has 2 bins of balls. 1 bin is red, and contains 3 red balls. The other bin is gray and contains 2 gray balls. Every minute, on the minute, exactly one customer comes by the bins, picks up ...
1
vote
0answers
27 views

period of product markov chain

Consider $Z_n := (X_n,Y_n)$ where $(X_n)_{n\in \mathbb{N}}$ and $(Y_n)_{n\in \mathbb{N}}$ are irreducible markov chains with periods $\lambda$ and $\mu$. We know that $(Z_n)_{n\in \mathbb{N}}$ is a ...
1
vote
0answers
22 views

Prove equilibrium theorem without irreducibility and aperiodicity

I have to solve the following question: Consider a random walk Markov chain on $S = \{1, 2, \ldots, 100\}$. If the chain is between 2 and 99, it selects one of the adjacent states with equal ...
1
vote
0answers
39 views

Two independent renewal processes

We have two urns (blue and red) that are connected, and two particles, $p_1$ and $p_2$, are traveling between these urns independently. The amount of time $Z_1$ that $p_1$ spends in blue urn is iid ...
1
vote
0answers
37 views

probability with exponential distribution

there is a barber shop with two waiting chair and one barber.suggest that,when a customer comes in,and two waiting chair are full,he goes to another barber shop. The time between entering of two ...
1
vote
0answers
64 views

A matrix of size $n\times n$ with several properties like Markov matrices

Could you find a square matrix $A=[a_{ij}]$ of size $n$ such that satisfies to following properties 1) For all $1\le i\le n$, $\sum_{j=1}^n a_{ij}=0$ 2) For all $i$, $a_{ii}<0$ and for $1\le i\ne ...
1
vote
0answers
19 views

Continuous time markov chain: $p_{ij}(t + h) - p_{ij}(t)$

Given a continuous time markov chain: According to Ross: $P_{ij}(t+h) - P_{ij}(t) = \sum_{k \ne i} P_{ik}(h)P_{kj}(t) - (1 - P_{ii}(h)P_{ij}(t)$ What does $(1-P_{ii}(h))$ mean here? I am assuming ...