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
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, ...
5
votes
0answers
130 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
81 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
222 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
66 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 ...
4
votes
0answers
128 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
170 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
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 ...
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 ...
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 ...
3
votes
0answers
73 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
94 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
89 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
108 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 ...
3
votes
0answers
94 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
133 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
32 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
59 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
235 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
27 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
0answers
56 views

What does a customer see when it begins to be served in $M/M/1$ queue?

In queueing theory, the PASTA (Poisson Arrivals See Time Averages) principle [wiki] justifies $a_n = P_n$ where $$a_n = \text{proportion of customers that find } n \text{ in the system when they ...
2
votes
0answers
30 views

Powers of (large) lower triangular matrix

Consider the following "game" of chance. Each time the player pushes a button he is awarded a random (finite, integer, non-negative) number of points. The probability of receiving any particular score ...
2
votes
0answers
39 views

Markov Chain with Normal Transition Matrix

Consider a (sub)-stochastic matrix $P$, and the associated Markov chain $X$ with \begin{align*} \mathbf P [X_n =y | X_0 = x] = P_{xy}^n. \end{align*} Suppose we have the condition $P^T P = P P^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 ...
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 ...
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
59 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
95 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
158 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
25 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
71 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
19 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
200 views

In finite-state Markov chain state $i$ is transient

Can you help me please with proof of this question: Prove, that in finite-state Markov chain state $i$ is transient if and only if is exist state $k$ such that $i\rightarrow k$ but k $\nrightarrow ...
2
votes
0answers
183 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
168 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
566 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
22 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 ...
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 ...
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
0answers
19 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 ...
1
vote
0answers
24 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 ...
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 ...
1
vote
0answers
23 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 ...
1
vote
0answers
12 views

Birkhoff-Neumann like result for stochastic matrices?

during my research I came along a nice lemma which looks like a Birkhoff-Neumann-theorem result, but in a version for stochastic matrices. Namely, I have: Lemma. Let $M$ be a stochastic matrix, then ...
1
vote
0answers
12 views

Changes in the transition matrix of a Markov chain

In most or all Markov chain theories that I know of assumes that the transition matrix does not change over time. But what if certain changes are expected to occur at certain times in the transition ...
1
vote
0answers
35 views

Problem with stochastic processes book - should I switch.

I've been reading "Essentials of Stochastic Processes" (second edition) by "Richard Durrett" and I quite liked it, it's a nice size book and it's very easy to read. However, and this is quite a big ...
1
vote
0answers
50 views

iterates of generalized matrix system

This may be somewhat of an underspecified question but I'll nonetheless give it a try. In the context of applied work, I've recently come across systems of the form $$ ...
1
vote
0answers
29 views

References for time-inhomogeneous Markov jump processes?

In some central models in life insurance mathematics, the state of the insured is modeled using a continuous-time time-inhomogeneous Markov process with finitely many states. While many results for ...
1
vote
0answers
43 views

Continuous transition kernel for Markov Chains

I am trying to show that the stationary distribution for a Markov Chain on a continuous state space can be obtained by building a transition density kernel, which obeys the detailed balance rule where ...