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
38 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
33 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
132 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
128 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
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)= ...
3
votes
1answer
187 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
177 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
917 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
387 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
218 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
911 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
800 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
345 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
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 ...
3
votes
0answers
60 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
47 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
36 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
50 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
94 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
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
132 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
192 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
108 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
51 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
194 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
118 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
93 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
54 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
272 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
242 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
117 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
113 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
147 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
278 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 ...