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

6
votes
0answers
274 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
62 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 ...
5
votes
0answers
305 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 ...
4
votes
0answers
52 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
148 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
58 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
85 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
146 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
210 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

Martingale converges to the boundary

I asked an almost same question before and it is solved by considering adjacent $Z_n$ can not be far away and obtain a contradiction. However, if the setting is altered a bit, I wonder whether it is ...
3
votes
0answers
25 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
36 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
105 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
53 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
38 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
76 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
151 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
108 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
129 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
105 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
140 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
65 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
252 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
38 views

A(nother) variation of the coupon collector's problem

I have come across variation of the coupon collector's problem that goes like this. The coupons are of $n$ different types and in infinite number (or sampled with replacement after each draw, where ...
2
votes
0answers
39 views

Markov chain monte carlo

The target is to simulate a discrete random variable $Z$ with mass function satisfying $\mathbb{P}(Z=i)\propto \pi_i$, for $i\in S$ and $S$ countable. Let $X$ be an irreducible Markov chain with ...
2
votes
0answers
32 views

Convergence of a Markov Chain to the normal distribution

If $i$ is a state of an irreducible, postive recurrent Markov chain $X$, and $V_n$ is the number of visits to $i$ between times $1$ and $n$, and further $\mu=\mathbb{E}_i(T_i)$ and ...
2
votes
0answers
24 views

$T_n$ stopping time, is $\{X_{T_n}\}$ markov chain

Let $\{X_n\}$ be a Markov Chain with finite state space $S$. Let $T_n$ be the $n$-th hitting time of $A \subset S$ i.e. $n$-th time it hits some state from the set $A$. Is $\{X_{T_n}\}$ a Markov chain ...
2
votes
0answers
19 views

Formal argument on independence of consecutive hitting times of a Markov chain.

I'm refering to the question: Differences of consecutive hitting times. I'm interested in the independence of consequtive hitting times of certain values of a Markov chain. And I do "understand" the ...
2
votes
0answers
69 views

Why are inter arrival times in the continuous version of discrete-time Markov chains always exponentially distributed?

I am curious whether there exist continuous time Markov processes for which the times between jumping times (which I call inter arrival times) are not exponentially distributed, but have some other ...
2
votes
0answers
19 views

Showing which classes are recurrent and which are transient

If I have a Markov chain on states {0,1,2,3,4,5} $$ \mathbf{a} = \matrix{~ & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1/3 & 0 & 2/3 & 0 & 0 & 0 \\ ...
2
votes
0answers
32 views

Define Markov chain and rewrite to recursively solve

Customers arrive at a server with rate $\lambda$ and are served at rate $\mu$. The server breaks down with rate $\gamma$, which causes all customers to leave. New customers can only arrive once the ...
2
votes
0answers
62 views

Model as a continuous time Markov Chain

A system consists of two machines, of which one works and the other is standby. Only the working machine can break down (with rate $\lambda$). If it breaks down the other machine takes over (if it ...
2
votes
0answers
23 views

Probability of going from a set $S$ to its complement on a Markov chain

I need to show that if $\pi$ is the stationary distribution of a Markov chain $M$, then for every set of vertices $S$, the probability to choose a random node in $S$ according to $\pi$ and then going ...
2
votes
0answers
43 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 ...
2
votes
0answers
19 views

How do I integrate this master equation from a time-continuous Markov chain?

I hope the question is not too vague. My calculus courses are way in the past and I can't remember how to do it :-). I have this master equation for a time-continuous Markov chain I have a two ...
2
votes
0answers
46 views

Mixing time for metropolis chain on graph coloring

I'm reading the Markov Chains and Mixing Times by David Levin et al.. In section 5.4 page 71 a proof is given for a bound of mixing time for the Metropolis Chain on graph coloring. In the proof, such ...
2
votes
0answers
22 views

Estimating the discrete laplacian to prove recurrence of simple random walk for d=2

Given a function $f : \mathbb Z\times \mathbb Z \rightarrow \mathbb{R}$ we define the discrete laplacian of $f$, $\triangle_df$, by the following rule $\triangle_df(x,y)= \dfrac{f(x + 1, y)+f(x, y + ...
2
votes
0answers
73 views

Induced Markov chain - verify Markov property and another property

First, here is how we defined induced Markov chains: Suppose that $(X,E,P)$ is an irreducible Markov chain, where $X=(X_i)_{i\in\mathbb{N}_0}$, $E$ is the state space and $P=(p_{i,j})_{i,j\in E}$ is ...
2
votes
0answers
57 views

Invariant Probability of Discrete Time MC from Continuous Time Markov Chain

Given rates α of an irreducible continuous-time MC on finite state space and told that π is the invariant probability measure of this chain, we define a discrete time MC as having transition ...
2
votes
0answers
103 views

How to prove a matrix norm inequality?

$P$ is a stochastic matrix i.e. square, non-negative, rows sum to one. Let $\Phi$ be a real matrix of size $n \times k$ with independent columns and $k < n$. Let $\Xi$ be the diagonal matrix with a ...
2
votes
0answers
11 views

Monte Carlo Markov Chain Simulation Issues

The Markov Chain is uniformly distributed across all $50$x$50$ matrices of entries $0$ and $$1 with no neighboring $1's$. I am supposed to run a MC simulation to check the probability that the ...
2
votes
0answers
26 views

The independence of random variables

Here is my question: Consider a homogeneous ergodic Markov chain on a finite state space $X=\{1,\ldots,r\} $. Define the random variables $\tau_n \,,n\ge1$ as the consecutive times when the Markov ...
2
votes
0answers
21 views

Proving that an inductively defined function is a Markov chain

Let $X_0$ be a random variable with values in a countable set $I$. Let $Y_1,Y_2,\ldots$ be a sequence of independent random variables, uniformly distributed on $[0,1]$. Suppose we are given a function ...
2
votes
0answers
79 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
97 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
16 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
33 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
76 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
40 views

literature to learn more on ergodic harris recurrent chains with an atom

I'm trying to learn more on the topic mentioned in the title. Namely I'd like to get more information on the behavior of the boundary terms. ie if I decompose sum of my chain (suppose it's ...