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
62 views

Can Continuous Time Markov Chains be used as a reasonable voting system?

I just compared a couple of example elections, as given on Wikipedia to show how Condorcet-methods differ from non-Condorcet ones, to what happens if you just interpret the underlying preference ...
7
votes
0answers
517 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
324 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
41 views

Poisson: Conditional Probability on Pizza order

I am not sure about my answer. In particular, part b of the following question. Pizza orders arrive according to a Poisson process of rate 20 per hour. Orders are independently for a vegetarian ...
5
votes
0answers
58 views

markov chain: 2 state chain

I have a machine. It has two states, broken or working. If it is working, then it will be broken with probability $q=0.1$. If the machine is working, I will make \$1000 dollar a day. If it is broken, ...
5
votes
0answers
37 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 ...
5
votes
0answers
84 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
152 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 ...
5
votes
0answers
107 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 ...
5
votes
0answers
93 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
70 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
85 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
228 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
74 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
110 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
157 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
117 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}$ ...
4
votes
0answers
268 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
41 views

This is a Markov Chain?

Consider two irreducible ergodic Markov chains with the same state space $\{0, 1, . . . , N\}$, with transition matrices $P$ and $Q$ and respective stationary distributions $\pi$ and $\rho$. We ...
3
votes
0answers
46 views

Markov Chain: Steady State Distribution.

A total of $M$ balls are divided between two urns A and B. A ball is chosen uniformly at random. If it is chosen from urn A then it is placed in urn B with probability $b$ and otherwise it is returned ...
3
votes
0answers
92 views

Norris exercise: Showing $P_0[\text{no return to}\ 0]=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 ...
3
votes
0answers
127 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 ...
3
votes
0answers
50 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
182 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 ...
3
votes
0answers
53 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
142 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
69 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
45 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
238 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
81 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
116 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
145 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
33 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
157 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
35 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
67 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
52 views

Limiting products of realizations of an integer-valued Markov chain

Let $(X_m)$ be a finite space discrete time irreducible and aperiodic Markov chain with stationary distribution $\pi$. The state space is a finite set of positive integers $\{x_1, x_2, \dots, x_l\}$. ...
2
votes
0answers
33 views

Irreducible and positive recurrent CTMC: $\sum_{i \in S} \pi(i) c(i) < \infty$?

Suppose we have a continuous-time Markov chain $X$ on the countably infinite state space $S$. The Markov chain is irreducible and all states are positive recurrent. The transition rates are given by ...
2
votes
0answers
62 views

Proof of the existence of a reversible stationary distribution

$p$ is a finite Markov chain where $p(i,j)>0$ for all $i,j$. Prove a reversible stationary distribution exists for $p$ if $p(i,j)p(j,k)p(k,i)=p(i,k)p(k,j)p(j,i)$ for all $i,j,k$ This question is ...
2
votes
0answers
109 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
57 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
51 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
38 views

Quasistationary distribution for the Moran model

The Moran model is a model for genetic drift. Basically, it is a finite Markov chain (more precisely, a birth-death chain) with state space $S:=\{0,...,N\}$ and the following transition probabilites: ...
2
votes
0answers
59 views

Gambler's ruin problem - expected time

I have troubles seeing the following. Consider the classical gambler's ruin problem, betting 1 at each time $t\in \mathbb{N}$, and losing or winning -1 respectively +1 at each time till the fortune of ...
2
votes
0answers
39 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
40 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
37 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
25 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
47 views

A time reversible Markov chain problem on urns

Question: (Ross Probability Models, Ch. 4, Ex. 70) A total of $m$ white balls and $m$ black balls are distributed into two urns such that each urn contains $m$ balls. At each stage, a ball is selected ...
2
votes
0answers
48 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 ...