New answers tagged

1

$M/M/1$ and its relatives are the queues which are markov chains. This is since these queues have exponentially distributed interarrival times and service times. $M/D/1$ is not a markov chain but there exists an imbedded discrete time markov chain whose properties provide information about the process. $M/G/1, G/G/1$ etc are not markov chains. But if ...


0

amd's answer gives some intuition for why this is true but I want to point out that it's not really a geometric distribution since it isn't memoryless. Consider a very simple Markov chain with states 1 and 2 and transition probabilities of 0.99 for 1$\to$2 and 2$\to$1. By symmetry, the particle will spend 50% of its time in each state, and indeed it ...


1

This isn't an answer per se, rather some thoughts to consider. If $\{X_n:n=1,2,\ldots\}$ is a Markov chain and we define the holding times $\{T_n:n=1,2,\ldots\}$ by $T_n\sim\mathsf{Exp}(\lambda_{X_n})$, then the sequence $\{T_n\}$ only defines a Poisson process if $\lambda_{X_n}$ is equal for all $n$. Otherwise, the intensity would be a stochastic process ...


0

Some functions of Markov chains are Markov chains. For example, if you're working on a finite state space and $Y$ simply is a permutation of the states, then the result is still a Markov chain. In general, a function of a Markov chain as described forms a Hidden Markov Model. To see if the function is not a Markov chain, simply check the Markov property: ...


1

Just take any non-irreducible Markov chain with two communicating classes, both of which satisfy the hypotheses of the ergodic theorem. Then the limit distribution will depend on which communicating class one starts in (even though any convex combination of those two limiting distributions satisfies the requirement of stationarity). EDIT: basically look at ...


3

The "main theorem" of this subject says that an aperiodic irreducible Markov chain on a finite state space converges to a unique stationary distribution regardless of the initial distribution. If you drop the aperiodic assumption, then you still have a unique stationary distribution but you might not observe convergence to it. If you drop the irreducible ...


3

The simplest one: transition matrix $\pmatrix{0 & 1\cr 0 & 1\cr}$.


0

The most straightforward approach is to compare the calculated distribution to your empirical distribution via a chi-square goodness of fit test. Since its a markov chain, you could test each conditional distribution (e.g., $p_{11},p_{12},p_{13},p_{14}$) separately. You'd need to verify that you have enough data so that the expected number of transition ...


1

There are many questions here, and some of them should perhaps be split into their own posts. But to address the title question, consider the Ornstein–Uhlenbeck process, which can be defined by the SDE $dX_t = dB_t - X_t \,dt$, or in various other equivalent ways. (In Wikipedia's notation, I am using the parameters $\mu = 0$ and $\theta = \sigma = ...


0

The full defintion is : "$C$ is closed iff for all $i,j ∈ E$, if $i∈C$ and $i→j$, then $j∈C$". The negation of $P ⇒ Q$ is $P ∧ ¬Q$. Thus, we have: "$C$ is not closed iff there are $i,j ∈ E$ such that: $i∈C$ and $i→j$ and $j∉C$".


2

A nonnegative random variable $X$ is exponentially distributed with parameter $\lambda$ if $$P[X\geq t]=e^{-\lambda t}\qquad(t\geq0)\ .$$ It has a probability density $$f_X(t):=\lim_{h\to0+}{P[t\leq X\leq t+h]\over h}=\lim_{h\to0+}{e^{-\lambda t}-e^{-\lambda(t+h)}\over h}=\lambda\>e^{-\lambda t}\ .$$ Your last displayed formula then should read ...


1

This is not true. For instance, you have different options for the future whether you're at $(3,4)$ or $(5,0)$, and you can tell which one you're at by looking at the past, so the process is not memoryless.


5

You need all row sums to be $<0$, else you can do the following: $$\begin{pmatrix}-1&1&0\\1&-1&0\\0&0&-1\end{pmatrix}$$ If you assume all row sums to be $<0$, the statement is true. After multiplying by $-1$, the matrix will be a Diagonally dominant matrix.


0

Perhaps I misunderstand your question but it seems to me that you are asking about two different things. One is the set where we take measurable sets and another the measure that we attribute to each measurable set. The first exists independently of the latter, the relation being that the support of any Markov measure (assuming that the Markov chain is ...


1

You’re on the right track, I think. First, back up a step and label the states so that $P$ takes the form of a block cyclic permutation matrix $$P=\begin{bmatrix} 0 & P_1 & \ddots & \ddots & 0 \\ 0 & 0 & P_2 & \ddots & \ddots \\ \ddots & \ddots & \ddots & \ddots & \ddots \\ 0 & 0 & \ddots & \ddots ...


1

This is a the transition matrix. You have $\text{Current State} \times \text{Transition Matrix} = \text{Next State}$ $ \begin{matrix} \text{Coke} & \text{Pepsi} \\ A & B \\ \\ \end{matrix} $ $ \:\:\:\:\: \times\:\:\:\:\: \begin{matrix} & \text{Coke} & \text{Pepsi} \\ ...


0

You are taking $1$ step and then you see where you are. Let $\tau(i)$ be the expected time to reach the absorbing state $2$ from state $i$, where $i =\{0,1,2\}$. $\tau(0) = 1 +\frac{1}{3}\tau(0)+\frac{1}{3}\tau(1)+\frac{1}{3}\tau(2)$ $\tau(1) = 1 + \frac{1}{2}\tau(1)+\frac{1}{2}\tau(2)$ $\tau(2) =0$ Solve the system to find $\tau(0)$.


1

A Markov chain with a finite state space has a unique stationary distribution if and only if it has exactly one closed communicating class; see e.g. these notes and Wikipedia.


2

A Markov decision process involves computing some quantity of the form $$ v^N(i)\equiv\sup_{\pi}\mathbb{E}^{(i)}\left[\sum_{n=0}^{N}\underbrace{\frac{1}{\left(1+\rho\right)^{n}}}_{\text{discount}}u(X_{n}^{\pi})\right] $$ where $(X_{n}^{\pi})_{n\geq0}$ is a controlled, time-homogeneous, Markov chain taking values in a finite state space ...


3

Dan Uznanski has already sketched the solution in a comment; I'll work it out in more detail. Regard one cell as stationary and let the other cell make two steps at a time. Turn the grid by $\frac\pi4$. Then the walk can be decomposed into two independent simple symmetric one-dimensional random walks. We want the probability that these walks end up at ...


0

I think I figured this out: If you are considering the states as CpG+ or CpG-, then the emission probabilities will not always be 0 or 1. However, if you are considering them to be A+, C+, G+, T+, A-, C-, G-, or T-, then the probablity of emitting an "A" in an "A+" or "A-" state is always 1. Conversely, the probability of emitting any other character (C, ...


3

You're right that the result doesn't depend on how the pair is selected. In each step, the difference between red and blue marbles in one of the jars is incremented or decremented with equal probability. It starts at $0$ and ends at $\pm n$. The expected number of steps for a simple symmetric one-dimensional random walk to reach $\pm n$ from $0$ is $n^2$. ...


1

Yes.   We could also use the definition of Conditional Probability, and the fact that the count of Poisson events occurring in disjoint intervals are independent. $$\begin{align} \mathsf P(N(4)-N(2)=3\mid N(4)=8) ~=~& \dfrac{\mathsf P(N(2)=5)~\mathsf P(N(4)-N(2)=3)}{\mathsf P(N(4)=8)} \\ =~& \dfrac{((2\lambda)^5\mathsf ...


1

Use the first displayed equation to find $p_1$ in terms of $p_0$. Substitute for $p_1$ in the second equation. Then you can find $p_2$ in terms of $p_0$. Do a few more and you can see the pattern, and show it to your audience at the presentation.


0

Hints for part 1: it should be clear that $\pi_1=\pi_2$ by considering how to get to states $1$ and $2$ similarly $\pi_3 = \pi_2 - \frac12 \pi_1$ and more generally $\pi_{n+1} = \pi_n - \frac1{n} \pi_{n-1}$ solving this and scaling using $\sum_i \pi_i = 1$ will give you the solution


0

In very simple words, you start a walk from 0 and have probability $p$ to take a step forward and $1-p$ to take a step backward. It means you take an average step of $2p-1$ in the forward direction, and in $n$ steps your average position will be at $n(2p-1)$. Then ${\rm P}\left( {{{X_{\,n} } \over n} \to \left( {2p - 1} \right)\;{\rm as}\;n \to \infty } ...


0

Here’s one way to understand this: Think of “outside observer finds the system in state $i$” as a Bernoulli trial with probability $\mathbf\pi_i$ of success. It’s easy to show that the expected number of trials required to produce a success is $1/\mathbf\pi_i$.


2

"Firstly I wanted to check if they have a mistake in the solution. So for the transition matrix, the element p11 should be 0 and p12 should be 1, but they have it the other way round so I just wanted to check whether this was a mistake or not." You are correct. $p_{1,1}$ should be $0$ and $p_{1,2}$ should be $1$. "Secondly If a set is a communication ...


2

The first entry in the matrix is $p_{1,1}=1/2$. It means that with $50$% probability you stay in state $1$ for one time step. To the right of $p_{1,1}$ you have $p_{1,2}$ which is the probability that you go from state $1$ to state $2$. Each entry $p_{i,j}$ means that you go from state $i$ to state $j$ where the $i$ is the row and the $j$ is the column. ...


1

The $p_{11}(0)=1$ comes from definition $$p_{11}(0) = \Pr\left(X_0 = 1 \mid X_0 =1\right) = 1$$ and so does the second equation $$p_{11}(1) = \Pr\left(X_1 = 1 \mid X_0 =1\right) = \mathbb{P}_{11} = 1-\alpha$$ You can get the third step by setting $\beta = -\alpha+\epsilon$ and considering the limit $\epsilon \to 0$


1

$1.$ $\textbf{Probability and Random Processes}$ by Grimmet and Stirzaker and if you also want a book with solved exercises there is a companion book that has solutions to every exercise: $2.$ $\textbf{One Thousand Exercises in Probability}$


1

Assmussen, Applied Probability and Queues is a good place to start. Having Meyn and Tweedie's "Markov Chains and Stochastic Stability" can be useful at times as well for discrete time theory on fairly general state spaces. Norris' Markov chains and Stroock's Introduction to Markov Processes may also be handy, though they are both somewhat basic.


1

An irreductible aperiodic chain on a finite nomber of states $0, 1, \dots , N-1$ it's positive recurrent and is transition matrix is $$\lim_{n \to \infty} P^{(n)}= \begin{bmatrix} \pi_0 & \pi_1 & \dots & \pi_{N-1}\\ \vdots & \vdots & \ddots & \vdots \\ \pi_0 & \pi_1 & \dots & \pi_{N-1} \\ \end{bmatrix},$$ where ...


1

Yes, the states all have the same probabilities in the stationary distribution. This is easy to see once you notice that the process is reversible: given two states $s_1$ and $s_2$ such that a transition from $s_1$ to $s_2$ is possible (by moving one frog), the rate of jumps from $s_1$ to $s_2$ when in state $s_1$ is the same as the rate of jumps from $s_2$ ...


0

The term "steady state vector" usually refers to a stationary distribution for $P$; that is, a row vector $\pi$ with entries that add to $1$, such that $\pi P=\pi$. Because $P$ is regular, $\lim_nP^n =\Pi$. ($\Pi$ is the $n\times n$ matrix whose every row is $\pi$.) Consequently, if $q$ is any column vector then $\lim_nP^nq$ is a column vector whose every ...


4

Notice that we never observe $X_{n-1}$ explicitly, only $X_{n-2}X_{n-1}$ - some sort of "incomplete information" about the most recent realization $X_{n-1}$. You can construct a counterexample where $X_k\in\{-1,1\}$, i.e. knowing that $X_{n-1}=1$ gives a different probability for $Y_n=1$ than when $X_{n-1}=-1$, but in both cases, $Y_{n-1}=1$. So knowing the ...


2

Since all rows sum to $1$, the vector $$ \frac1n\pmatrix{1\\\vdots\\1} $$ (with $n$ $1$s) is an eigenvector of the transition matrix with eigenvalue $1$. Since the chain is regular, it has a unique stationary distribution, so this is the stationary distribution.


0

"Does this not mean that equilibrium distributions are the same as stationary distributions, in practice?" Stationary Distributions: Let $\mathbf{P}$ be the transition probability matrix of a homogeneous Markov chain $\{X_n, n \geq 0\}$. If there exists a probability vector $\mathbf{\pi}$ such that $$\mathbf{\pi} \mathbf{P} = \mathbf{\pi} \:\:\:\:\:\:\: ...


1

Note that for all $t>0$, $P(t)=e^{tG}$ satisfies the differential equations \begin{align}P'(t)&=P(t)G\\ P'(t) &= GP(t) \end{align} (known as Kolmogorov's forward and backward equations.) If $\pi$ is a stationary distribution, then $\pi P=\pi$. Differentiating and setting $t=0$ yields $\pi G=0$. Conversely, if $\pi G=0$, multiplying by $P(t)$ ...


2

First of all, it should be noted that there are simpler ways to compute the stationary distribution $\pi$. Your matrix $G$ is diagonalisable. This fact may be useful when computing matrix powers directly, but there is another reason this is useful. You are computing a matrix exponential. $$ P_t = e^{t G} = \sum_{n=0}^\infty \frac{t^n G^n}{n!} $$ In the ...


1

Define the function $f(x,y)=x+\left({\bf 1}_{(-\infty,0]}(x)-{{\bf 1}_{(0,\infty)}(x)}\right)y.$ Then $X_n=f(X_{n-1},Y_n)$ for $n>0$, and if $({\cal F}_n)_{n\geq 0}$ is the filtration generated by $(X_n)_{n\geq 0}$, then $$\mathbb{P}(X_n\in B\mid {\cal F}_{n-1})= \mathbb{P}(f(X_{n-1},Y_n)\in B\mid {\cal F}_{n-1})=\mu(X_{n-1},B),$$ where we define the ...


2

Note that the following must hold for a recurrent state: If $x$ is a recurrent state and $\rho_{xy}>0$, then $\rho_{yx}=1$. That is to say, if there is a nonzero probability that the state $x$ could go to another state $y$, then the probability that the state $y$ would in some time reach $x$ is 1. Whenever we have closed, irreducible sets, the states ...



Top 50 recent answers are included