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

7
votes
0answers
464 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 ...
6
votes
0answers
315 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). ...
5
votes
0answers
72 views

Simplifying Chain of Conditional Variances given a Markov Chain

$\newcommand{\Var}{\operatorname{Var}}$Suppose $X,Y,W$ form a Markov chain $X \to Y \to W$. Can we simplify the following expression? \begin{align*} E [ \Var ( \Var (X\mid Y) \mid W)] \end{align*} ...
5
votes
0answers
80 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 ...
4
votes
0answers
23 views

Find a Markov chain transition kernel

Let $f_{X}$ be a density we would like to sample from. For some reasons, $f_{X}$ may be analytically intractable or expensive to evaluate. A solution consists in considering a density $(x,y) \in X ...
4
votes
0answers
67 views

Distribution of $\max_{n \ge 0} S_n$, random walk.

Say I have a random walk that's a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
4
votes
0answers
82 views

Weak convergence of a sequence of stationary distributions to another stationary distribution

Let $\{X_n(t) \in \mathbb{R}^+\}$ for each $t \in (0,1)$ denote a discrete time Markov chain (with time index $n$ and parameterized by $t$). For each $t$, the Markov chain $\{X_n(t)\}$ has a unique ...
4
votes
0answers
117 views

Harmonic functions and null recurrence

Let $(X_n)_{n \geq 0}$ be a irreducible Markov chain defined on a countable state space $S$. It is known some ways to figure out if this chain is recurrent or not looking for superharmonic functions ...
4
votes
0answers
205 views

6-digit password - a special decoding method

Consider the situation of decoding a 6-digit password that consists of the symbols A to Z and 0 to 9, where all possible combinations are tried randomly and uniformly. Consider the ...
4
votes
0answers
70 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 ...
4
votes
0answers
107 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
152 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
255 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
42 views

$ X_n = 2 Y_n + Y_{n+1} $ (non)Markov Chain

Let $Y_1,Y_2,\dots$ be iid random variables with $P(Y_n=0)=1-p,\; P(Y_n=1)=p$ where $p\in(0,1)$. Define $$ X_n = 2 Y_n + Y_{n+1} $$ The question is, whether $\{X_n\}$ is a Markov chain or not. ...
3
votes
0answers
65 views

An irreducible Markov chain is a martingale

Let $\{X_n\}$ be an irreducible Markov chain. Does exist example of such $\{X_n\}$ which is also a martingale given that: a. $\{X_n\}$ is recurrent with finite number of states (but bigger ...
3
votes
0answers
48 views

Periodicity of Markov chains under cartesian product

Suppose that you have a finite state Markov chain, with $n$ states and characterized by $p_{i,j}$ the probability of reaching state $j$ from state $i$. Consider the new Markov chain with $n^2$ states ...
3
votes
0answers
135 views

Prove or disprove: If $h$ is harmonic on $E$, then $h$ is constant on each $C_i$

For a general finite Markov chain $(X_n)_{n\in\mathbb{N}_0}$ with state space $E$ and transition matrix $P=(p_{x,y})_{x,y\in E}$, not necessarily irreducible, we define the linear space of ...
3
votes
0answers
66 views

Why a positive recurrent Markov chain implies positive limiting probability?

Let $X=\{X_0,X_1,\ldots\}$ be an irreducible, positive recurrent, and aperiodic Markov chain with the state space $S=\{0,1,2,\ldots\}$ then how do we show that the probability $$ ...
3
votes
0answers
41 views

A basic doubt on Markov chain/ergodicity

Consider a finite state (no. of state $N$) Markov chain $\{X_n\}$ (all the random variables are bounded) such that there is a state $i*$ such that $$ \sum_{i=1}^{N}p_{ii*}^{(n)} > 0$$ for all ...
3
votes
0answers
88 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
212 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
79 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$ ...
3
votes
0answers
114 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
139 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
110 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
30 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 ...
3
votes
0answers
153 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
33 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
66 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} ...
2
votes
0answers
47 views

Norris exercise: Showing $P_0[X_n\neq0\forall n\geq1]=6/\pi^2$

Consider exercise 1.3.4 of Norris' Markov Chains. The question is as follows: Let $\{X_n\}_{n\geq 0}$ be a Markov Chain with state space $S=\{0,1,2,\dots\}$. Suppose the transition probabilities ...
2
votes
0answers
83 views

Probability mass function of the sum of the function of the sum of iid random variables

How can I get an expression of the probability mass function of: \begin{equation} Y_i=\sum_{k=1}^i f\left(\sum_{n=1}^{k} X_n\right) \end{equation} being $X_n, n=1,2,...$ iid random variables and ...
2
votes
0answers
46 views

Convergence of empirical average of Markov chain from transient class

I am trying to get an intuition of how to understand the limit of the empirical average $$\frac1n\sum_{i=1}^nX_i\tag{$\ast$}$$ of some Markov chain $(X_n)_n$ with transition matrix $P$ (let's assume ...
2
votes
0answers
49 views

distribution of times that a traveller passes by vertex

a traveller is travelling on a map. arriving every vertex of the map, the traveller could choose to go to next vertex according to a constant probability. The probabilities are represented in a matrix ...
2
votes
0answers
37 views

Markov chain limit problem

Let $X_n$ be a Markov chain on a countable state space, $\mathbb{S}$. Let $N_n(x) = \sum_{k=1}^n\mathbb{1}_{\{X_k=x\}}$ denote the number of times the chain visits state $x\in \mathbb{S}$. Let ...
2
votes
0answers
33 views

A Poisson process game

An interesting puzzle I came across: For $T>1$, observe a Poisson process of rate $1$ on the time interval $(0,T)$. Every time we observe a point, we may choose to stop. To win the game, we ...
2
votes
0answers
36 views

Markov chain and laws of large number

Let $X_n$ be a (could assume this is homogenous) markov chain on a countable state space $S$, and write $N_n(x)=\sum_{k=1}^n 1_{\{X_k=x\}}$. Let $z\in S$ be a recurrent state, denote by $R_z$ its ...
2
votes
0answers
65 views

Equalizing Geometric means of Graph Cycles

Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers to each edge of $G$ so that the geometric mean of all cycles are equal? ...
2
votes
0answers
24 views

Calculating integral with antithetic variables

Use simulation with antithetic variables and find $$\int_{-\infty}^\infty \int_0^\infty \sin(x+y)e^{-x^2+4x-y} \, dx \, dy.$$ so, my question and doubt is how struggle with the infinite limit ? It ...
2
votes
0answers
43 views

Excursion of random walk conditioning on return

Consider a simple random walk in one dimension starting from the origin. Let $\epsilon>0$. How to prove that, conditioning on the event that the random walk is at the origin at time $n$, the ...
2
votes
0answers
39 views

Compute the value of $\mathbb{P}_{0}\left[\tau\geq n\right]$ and $\mathbb{P}_{0}\left[\tau=+\infty\right]$

We consider the Markov chain $\left(X_{n}\right)_{n\geq0}$ on $\mathbb{N}$ whose transition matrix $P=\left(p_{k,l}\right)_{k,l\geq0}$ given by $$\forall k\in\mathbb{N} ...
2
votes
0answers
17 views

How to compute Generalized Group Inverse?

Given a transition matrix $P \in \mathbb{R}^{n \times n}$, i.e. $\sum_j P_{ij} = 1$ and $P_{ij} \geq 0$ for all $i,j$. One can show that there exists a unique group inverse $B$ of $A:= I - P$ which ...
2
votes
0answers
11 views

The restriction of the green function is non-degenerate

On the context of irreducible Markov chains on a finite graph one defines $$G = \sum_{k=0}^\infty \hat{Q}^k $$ where $\hat{Q}$ is the restriction of a stochastic matrix to a subset (one can think ...
2
votes
0answers
165 views

When the sum of Markov chains is a Markov chain: “dumb” algorithm

Suppose I have two (independent) discrete-time and space, preferably non-homogeneous Markov chains $\Gamma^{(i)}=\{\gamma_1^{(i)},\gamma_2^{(i)},...\}, \ i=1,2$ and I want to find a way to check when ...
2
votes
0answers
36 views

Expected response time of Continuous time Markov chain

I'm studying CTMC (Continuous Time Markov Chains). I came across the following slide I don't understand how they got $M(t+h) = M(t) + \alpha h + M(t)\lambda h - M(t) \mu h +o(h)$ Could anyone ...
2
votes
0answers
52 views

Why is the stationary distribution a distribution?

Suppose we have a time-homogeneous, discrete-time, aperiodic, positive recurrent, irreducible Markov chain $(X_t)_{t \geq 0}$ on a discrete state space $E$. It is known that its stationary ...
2
votes
0answers
81 views

Unique stationary distribution (or measure?) of a Markov Chain

Let $(X_n)_{n \geq 0}$ be a irreducible, positive recurrent Markov chain. We have a theorem that states that the unique stationary distribution is then given by $$\pi(x)= \frac{1}{E_x[H_x]},$$ where ...
2
votes
0answers
25 views

Likelihood that two markov chains are derived from the same transition matrix

Forgive me for my weak statistic background, hopefully what I'm asking makes sense. So some quick background, I have one markov chain from a data set and many additional chains that I'm producing from ...
2
votes
0answers
38 views

MLE for CTMC parameters

Let the data set be $$D = \{(s_0, t_0), (s_1, t_1), ..., (s_{N-1}, t_{N-1})\}$$ where $N=|D|$. Each $s_i$ is a state from the state space $S$ and during the time $[t_i,t_{i+1}]$ the chain is in state ...
2
votes
0answers
36 views

Consequence of random walk with positive speed on a graph

Consider a random walk $X(n)$ on a vertex-transitive graph where the random walk has positive speed, i.e., $$ \lim\limits_{n \rightarrow \infty} \frac{d(X(n), X(0))}{n}= \alpha>0$$ almost surely. ...
2
votes
0answers
46 views

Branching Process in simple random walk

Suppose we have a simple random walk on $\mathbb{Z}$ which stars at $1$, i.e. we have iid increment $X_n$ valued in $+1,-1$ with probability $\frac{1}{2}$ each and the sum $S_n=\sum_{i=1}^{n}X_n+S_0$ ...