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

Does the measurability of $x\mapsto\operatorname P_x[A]$ imply the measurability of $x\mapsto\operatorname E_x[X]$?

Let $(\Omega,\mathcal A)$ and $(E,\mathcal E)$ be measurable spaces $(\operatorname P_x)_{x\in E}$ be a family of probability measures on $(\Omega,\mathcal A)$ such that $$E\ni x\mapsto\operatorname ...
3
votes
1answer
115 views

Irreducible Markov chain and invariant measure

We consider a Markov chain $\left(X,P\right)$ on a finite state space $X$. We denote $P:=\left(p_{x,y}\right)_{x,y\in X}$ and for $n\in\mathbb{N}$ $P^{n}:=\left(p_{x,y}^{(n)}\right)_{x,y\in X}$....
3
votes
1answer
106 views

Application of diagonalization of matrix - Markov chains

Problem: Suppose the employment situation in a country evolves in the following manner: from all the people that are unemployed in some year, $1/16$ of them finds a job next year. Furthermore, from ...
3
votes
2answers
128 views

Markov Chains - Strong Markov Property

I'm struck with an exercise. I tried, but the results don't seem to fit to those proposed. Exercise: Two players play the following game. The one who begins draws two cards from a deck of 40 cards (...
3
votes
1answer
39 views

Generating Constrained Random Distributions

I am trying to help another StackExchange user. We are attempting to fill a 6x6 matrix with 12 A's, 12 B's, and 12 C's subject to the constraint that each row contains 2 A, 2B and 2 C and each column ...
3
votes
1answer
38 views

non-stationary Markov chain n-step

When I search for the long term behaviour of a stationary markov chain I just multiply the transition matrix with itself for the number of steps: P(n) = P(0)^n. But how do you go about doing it ...
3
votes
1answer
133 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 {$W_1>...
3
votes
1answer
149 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 $$ p_{ii}^{(n)}=\mathbb{P}(X_n=i|X_0=i)=:\mathbb{P}_i(X_n=i). $...
3
votes
1answer
68 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 $P$...
3
votes
1answer
125 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)= \frac{1}...
3
votes
1answer
196 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: $g_{N/...
3
votes
1answer
223 views

Green's function of a Markov Chain, and maybe of a Feller Process?

How are the Green's functions of a Markov chain related to the notion from PDE theory? For instance, if the Markov chain (i.e. discrete state space) is continuous time, then the Green's function I'm ...
3
votes
1answer
118 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
184 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
942 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
29 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
60 views

I cannot see what happens to $P_{ij}(s)=p_{ij}^0+\sum^\infty_{n=1}\sum^{n-1}_{k=0}s^{n-k}f_{ij}^{n-k}s^kp_{jj}^k$ to get result

This is self learning and it is stats. $P_{ij}(s)=\sum^\infty_{n=0}p_{ij}^ns^n$ (which you'll probably recognise is a generating function) and $F_{ij}(s)=\sum^\infty_{n=1}f_{ij}^ns^n$ (note n=1 ...
3
votes
1answer
391 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
224 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
947 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
825 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
352 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} {}&s_1&...
3
votes
0answers
32 views

Distribution on number of revisits in past $k$ steps of Markov chain

Consider a finite-state Markov chain with transition matrix $P$. The chain starts in a state chosen uniformly over all the states and runs indefinitely from there. We're going to examine only the $k ...
3
votes
0answers
28 views

How to handle Finite-state-machine with correlated inputs?

My system can be represented by the following state-diagram. where each arch represents Input/Output when a transition is made from one state to the other. The inputs to this FSM are correlated. ...
3
votes
0answers
48 views

Hitting probabilities in a random walk on a graph

Consider a random walk $(X_n)$ on the graph below, where we jump from a given vertex to one of its adjacent vertices with equal probability. I want to find: the probability that we hit $A$ before ...
3
votes
1answer
40 views

Probability that two random walks on $\mathbb{Z}^2$ meet at the origin

Suppose $X,Y$ are symmetric, independent random walks on the lattice $\mathbb{Z}^2$. I am trying to find the probability: $$\mathbb{P}\big(X_n=Y_n=(0,0)\;\text{for some}\;n\,\big|\,X_0=Y_0=(0,N)\big)$$...
3
votes
0answers
64 views

Strong Markov property proof

Let $X$ be a Markov chain with state space $\mathcal{S}$ and denote $\mathbb{N} := \{0,1, \cdots\}$. I need to show that for any stopping time $\tau < \infty$ and any bounded measurable function $\...
3
votes
0answers
54 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
39 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 $m>...
3
votes
1answer
54 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
43 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
52 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
106 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
44 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 ...
3
votes
1answer
76 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
138 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
198 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
113 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 happening....
3
votes
0answers
52 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
215 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
119 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
0answers
57 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
143 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 harmonic ...
3
votes
0answers
72 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 $$ \lim_{n\rightarrow\...