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

3
votes
1answer
128 views

Joint density function Poisson Process

We did an example in class that I'm not sure how we came up with the answer. The problem is: If I let X(t) be a Poisson process of rate $\lambda$. I'm supposed to validate the identity ...
3
votes
1answer
118 views

Stochastic matrices with orthogonal eigenvectors

I stumbled across an odd fact while thinking about Markov chains, and I have an odd proof for it. Claim: Let $P$ be the transition matrix of a finite irreducible aperiodic Markov chain, and assume ...
3
votes
1answer
29 views

Show that $p_{ii}^{(k+l)}\geqslant p_{ij}^{(k)}\cdot p_{ji}^{(\ell)}$

Let $(X_n)_{n\in\mathbb{N}_0}$ be an irreducible Markov chain with state space $E$ and Transition Matrix $P=(p_{ij})_{i,j\in E}$. Set $$ ...
3
votes
1answer
67 views

Prove matrix is positive semi-definite

$P$ is a stochastic matrix (square, non-negative, rows sum to 1). $\Xi$ is a diagonal matrix with a left principal eigenvector of $P$ on the diagonal and zeros elsewhere (stationary distribution if ...
3
votes
1answer
122 views

Gambler's ruin: Distribution of the maximum fortune along the game conditioned to lose

I having troubles with this problem: Let $(X_n)$ a gambler's ruin Markov chain on $\{0,\dots,N\}$ i.e. a Markov chain with state set $E=\{0,\dots,N\}$ and probability transitions $$p(k,k+1)= ...
3
votes
1answer
181 views

Mean exit time / first passage time for a general symmetric Markov chain

Suppose I have a Markov chain as depicted in the following figure: where $N$ is even. State 0 and $N$ are the two sinks of the chain. The transition probabilities have the following property: ...
3
votes
1answer
117 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{ customers in the system when ...
3
votes
1answer
170 views

Proving that Markov Chain Monte Carlo converges

I am trying to understand how the very basic Markov Chain Monte Carlo approach works: We try to approximately calculate the expected value $E_{\pi(x)}[X]$ by drawing sequential samples from a Markov ...
3
votes
1answer
904 views

Sum of two Markov processes another Markov process?

Let $dX_{t} = m_1(l_1-X_{t})dt+\sigma_1 dW_{t}$ and $dY_{t} = m_2(l_2-Y_{t})dt+\sigma_2(\rho dW_{t}+\sqrt{1-\rho^2}dW_{t}^{1})$ where the $m_i$'s, $l_i$'s and $\sigma_i$'s are constants, $\rho \in ...
3
votes
1answer
28 views

The expectation of total number of different states in N time points

[Conditions] (1) An object has K possible states. (2) This object can have only one state at a single time point. (3) The probability of each state at any single time point is 1/K, and each time ...
3
votes
1answer
382 views

A basic question on irreducible periodic markov chain

For an irreducible periodic (period $2$) Markov Chain I know that both of the following two quantities are same and equal to $\pi(i)$: $$ \lim_{n\to \infty} \frac{1}{2}(p_n(j,i) + p_{n+1}(j,i))$$ $$ ...
3
votes
1answer
214 views

If $P$ is an invertible transition probability matrix, does $P^{-1}[i,j]$ have any interesting meaning?

Suppose we have a Markov chain transition probability matrix $P$ that is invertible, i.e., $P^{-1}$ exists. Question: Does there exist a meaningful interpretation of the $(i,j)$ entry in $P^{-1}$? ...
3
votes
1answer
881 views

Proof about Steady-State distribution of a Markov chain

Consider $A$ as a matrix, that when normalized represents an finite-state time-homogeneous Markov chain $M$ with entries $0\leq p_{i,j}\leq 1$, where each row sums up to $1$. We can also assume that ...
3
votes
1answer
2k views

Acceptance probability of Metropolis-Hastings

I am an IT guy writing my masters thesis on MCMC methods for use in predicting the outcome of football(soccer) matches. Right now I am trying to wrap my head around MCMC and Metropolis-Hastings in ...
3
votes
1answer
172 views

what's the generalized approach to this infinite state markov chain problem

Say, a bag has 10 balls, in which 9 are red, 1 is black. Each red ball is worth 1 point, each black is worth 4 points. I have 8 picks from the bag to start with (the bag refills itself after each ...
3
votes
1answer
789 views

Countable state Markov chain: detailed balance consequences

Let $S$ be a countable set and $\pi$ a probability distribution on $S$. A discrete-time Markov chain $(X_n)$ with state space $S$ is said to be in detailed balance with respect to $\pi$ (or simply in ...
3
votes
1answer
1k views

Probability distribution of markov chain

I have a Markov chain with state space $E = \{1,2,3,4,5\}$ and transition matrix below: $$ \begin{bmatrix} 1/2 & 0 & 1/2 & 0 & 0 \\ 1/3 & 2/3 & 0 ...
3
votes
1answer
108 views

What happens to a regular Markov matrix that has more than one steady state/stationary distribution?

It is known that for a regular Markov matrix $M,$ $M^{n}$ has the steady-state vector as all of its columns as $n \to \infty.$ I learned this in class, but what if there is more than one steady-state ...
3
votes
1answer
341 views

Identifying states in Markov chains

I just started learning about Markov processes and got the following homework question. Classify all the states as recurrent or transient for the Markov chain below $$\begin{matrix} ...
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
1answer
33 views

Random walk on the positive integers with reflecting boundary

Consider a Markov chain $X$ on the positive integers where for each $n$: $$n\longrightarrow 1,\;2,\;3\;\dots \;n,\;n+1$$ with equal probability, and $n\longrightarrow m$ with zero probability if ...
3
votes
1answer
53 views

Need some help with proving the Erdos-Feller-Pollard theorem

I am working on an analytic proof of Erdos-Feller-Pollard theorem. The exercise basically tells me to prove some steps in order to prove the theorem. First, a few definitions: Let $\{X_n\}$ be a ...
3
votes
0answers
42 views

Randomized Chess [duplicate]

In chess, a rook can move either horizontally within its row (left or right) or vertically within its column (up or down) any number of squares. In an $8\times 8$ chess board, imagine a rook that ...
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
1answer
74 views

Using Strong Markov Property

Let $X_n$ be a DTMC, with transition matrix P and state-space I. Let $Y_m=X_{T_m}$ for $m \in \mathbb{N}$. Define $T_0=\inf\{n\geq0:X_n\in J\subset I\}$ and $T_{m+1}=\inf\{n> T_{m}:X_n\in J\subset ...
3
votes
1answer
189 views

Show $S_N = \sum\limits_{n=1}^{N} \text{sign}(Y-X_n)$ is Markov, $(X_n),Y $ iid Uniform(0,1)

Let $(X_n)$ and Y be i.i.d. Uniform$(0,1)$ random variables and let $$S_N = \sum\limits_{n=1}^{N} \text{sign}(Y-X_n)$$ Show that $S_n$ is a Markov Chain and find its transition probabilities. Any ...
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
1answer
171 views

Frog on infinitely many lily pads (Markov chain)

A frog on pad $i$ hops to one of the pads $(1,2,...,i,i+1)$ with equal probability. I know that if the frog starts on pad $k$ the expected number of times the frog jumps, before returning for the ...
3
votes
2answers
104 views

Markov chains diagram - what are the numbers above arrows?

Most if not all articles describe the numbers above arrows as probabilities of a transition in that direction, such as this one, or this one. But here, for example, something really weird is ...
3
votes
0answers
49 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
175 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
1answer
115 views

Markov Property Confusion

I feel like I'm being very dense/employing some sort of circular reasoning, but I'm having trouble understanding the Markov Property. According to Durrett (ISBN-10:1461436141), $X_n$ is a Markov chain ...
3
votes
1answer
90 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
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
1answer
267 views

2D random walk variation

If a point on a 2D lattice is allowed to take a random walk by taking a unit step either up, down, left or right, there is probability $1$ of reaching any point (including the starting point) as the ...
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
1answer
131 views

Dice probability of a winning more than $X\%$ of the time over $Y$ Throws

I have a die with three possible outcomes. The three outcomes are win (+1), draw (0) and lose (-1). $P(w) + P(d) + P(l) = 1$. (1) If I throw the die Y times, what is the probability I will win $X$ ...
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
1answer
112 views

expected hitting time with two absorbing states

Consider a Markov chain in a finite space and with two absorbing states, each of which is accessible from the other, transient states. Is the expected number of transitions to reach any single ...
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
1answer
268 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
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} ...