# Tag Info

## New answers tagged markov-chains

1

Set $\DeclareMathOperator \gcd{gcd}$ $$N_x := \{n \in \mathbb{N}; p^n(x,x)>0\} \qquad \quad d_x := \gcd(N_x).$$ state 4: Since $p(4,4) = \frac{1}{2}>0$, it follows that $p^n(4,4)>0$ for all $n \in \mathbb{N}$; hence, $N_4 = \mathbb{N}$ and $d_4 = \gcd(\mathbb{N})=1$, i.e. state $4$ is aperiodic. state 3: We have $$p^2(3,3) = \mathbb{P}^3(X_2 = ... 0 For the update equations, they treat alpha, beta, and bj as independent of aij. If you see it this way I am sure you will see how they get the partials. I think their derivation could have been better myself. For example, they could have arrived at (27) from (26) by moving lambda to the other side without multiplying by aij and summing over j. Maybe I'm ... 1 Model: Set A:=0, B:=50. Let \xi_j \sim \frac{1}{6} \delta_{-1} + \frac{1}{3} \delta_0 + \frac{1}{2} \delta_1, j \geq 1, be independent identically distributed random variables. Then$$X_n := k + \sum_{j=1}^n \xi_j$$is the position of the person after n steps if the person starts at X_0=k. We would like to calculate the probability that the ... -1 When we calculate eigen values and eigen vectors: Given an eigenvalue Y, and eigenvector associated with Y is a non zero vector x such that: (A-YI)x=0 Now in markov chain a steady state vector ( when effect multiplying or any kind of linear transformation on prob state matrix yield same vector) : qp=q where p is prob state transition matrix this means Y ... 1 Firstly, the reason why exchanging rows and columns still maintains the condition we desire is because the condition does not care for where the letters are, only the number of occurrences of each letter. Swapping rows and columns clearly does not change that, so any row or column exchanges are okay. However, no matter how you switch the rows and the ... 0 The Markov chain is irreducible, since for any pair of states i,j, there exists n>0 such that P_{ij}^n>0. Since the expected return time to a state is finite, each state is positive recurrent. It follows that each state is visited infinitely often. To argue a bit more rigorously, let F_n = \mathbb I_{\{X_n=k\mid X_0=k\}} and$$N_k = ...

1

Time homogeneity is not a requirement of Markov Chains. All that is needed is that the Markov Chain be memoryless. The conditional probability distribution of future values of the stochastic process given the current and past states, must be equal to the conditional probability distribution of future values of the stochastic process given the current ...

0

I assume from the solution that $T_i$ is the time to go from state $i$ to $i+1$. So the expected time to go from state $0$ to $2$ is $E(T_0+T_1)=E(T_0)+E(T_1)$. Conditioning on the result of the next step, we have, \begin{eqnarray*} E(T_i) &=& E(T_i\mid \text{birth})P(\text{birth}) + E(T_i\mid \text{death})P(\text{death}) + E(T_i\mid ...

0

Part(a) Condition on $X_n = x$: $$E[X_{n+1}|X_n = x] = \sum yP(x, y) = Ax + B$$ Taking expectation of both sides leads to the result. Part(b) Write $EX_n + \frac{B}{A-1} = A\left(EX_{n-1} + \frac{B}{A-1}\right)$ given $A\neq 1$. The rest is easy.

1

In order to make the entire process be Markov, you can raise the dimension, and consider a four state chain: the states are $(A,1),(A,0),(B,1),(B,0)$. (This is a common theme: you can increase the dimension to take away memory effects, or reduce the dimension at the cost of adding memory effects.) The first component represents "Alice will come in next/Bob ...

0

Let $x_t$ be the probability that the light is on, and $y_t$ be the probability that the light is off, before step $t$. If Alice enters the room: $$x_{t+1} = \frac 12 x_t + \frac 14 y_t$$ $$y_{t+1} = \frac 12 x_t + \frac 34 y_t$$ If Bob enters the room: $$x_{t+1} = \frac 12 y_t + x_t$$ $$y_{t+1} = \frac 12 y_t$$ When Alice enters the room, $[x_{t+1} ~~ ... 0 Everything is based around an application of the definition of conditional probability and the additive rule for probabilities of disjoint events, plus a few additional steps. The solution for Part (b), for instance, also includes the use of distribution and the assertion that all$(C_i\cap D)$are all mutually exclusive (disjoint), if all$C_i$are such. 0 In the dynamic linear models literature, a distinction is often made between filtering, smoothing and predicting. At a given time$t$, filtering refers to the estimation of an unobserved state$x_t$given an observed measurement$y_t$. Smoothing is the retroactive estimation of states$x_{t-k}, k \gt 0$at past times, and predicting is the estimation of ... 0 We begin with the Chapman-Kolmogorov equations. For small$h$, we have \begin{eqnarray*} P_{i,j}(t+h) &=& \sum_{k=0}^{\infty} P_{i,k}(h) P_{k,j}(t) \\ && \\ &=& P_{i,i-1}(h) P_{i-1,j}(t) + P_{i,i}(h) P_{i,j}(t) + P_{i,i+1}(h) P_{i+1,j}(t) + o(h) \\ && \qquad\text{since the probability of transition in time$h$from$i$to} \\ ... 0 I agree with you that$(2)$is equivalent to$\psi$-irreducibility and that it is not clear how the authors derive$(2)$from the given assumptions. In the proof, the key point is that$\varphi(\bar{A}(k))>0$for$k$sufficiently large where $$\bar{A}(k) := \left\{y; \sum_{n=1}^k P^n(y,A) >k^{-1} \right\}.$$ Here is possibility to prove this ... 0 Conditioning on the value of$X_{t+1}$, we have, for any$i,j$, \begin{eqnarray*} P(X_{t+2}=j\mid X_t=i) &=& \sum_{k=1}^{n} P(X_{t+2}=j\mid X_{t+1}=k,X_t=i) P(X_{t+1}=k\mid X_t=i) \\ &=& \sum_{k=1}^{n} P(X_{t+2}=j\mid X_{t+1}=k) P(X_{t+1}=k\mid X_t=i) \qquad\text{by the Markov property} \\ &=& \sum_{k=1}^{n} p_{kj}p_{ik} \\ ... 0 This may be a helpful way of thinking of it. Suppose you have$n$independent "exponential alarm clocks", i.e. the time until clock #$j$rings is an exponential random variable with a given rate$r_j > 0$(and thus expected value$1/r_j$). You wait until the first clock rings, and if it is clock$j$that rings you go into state #$j$. This will be a ... 0 As Robert Israel and Ian suggested, this is a continuous-time Markov chain, and those are rates, not probabilities. It should be emphasized that "rate" here has a specific technical meaning that is not necessarily equivalent to the usual everyday meaning. For instance, suppose we had a continuous-time Markov chain with two states,$0$and$1$, a single ... 2 A condition: If$N$is nilpotent matrix, then there exists$(I - N)^{-1}$. A nilpotent matrix, for example: an upper triangle matrix with entries on diagonal are$0$. 1 To your first question, the answer is generally no. The matrix $$N= \frac 23 \pmatrix{1&1\\1&-1}$$ will have (Euclidean) operator norm$4/3 > 1$.$(I - N)^{-1}$will exists if$\rho(N)<1$($\rho(N)$denotes the spectral radius of$N$). This in turn is true if and only if$\|N\| < 1$for some multiplicative matrix norm$\|\cdot \|$. 0 Let us start with one particle moving randomly at each time step with probability$\frac12$to the left or to the right. The probability of having the particule at position$x$at time$t$follows the finite difference equation $$p(x,t+1)=\frac12 p(x+1,t)+\frac12 p(x-1,t).\tag{1}$$ Let us solve this equation with initial condition$p(x,0)=1$if$x=0$and ... 5 Of course$I-N$is not always invertible. Clearly, if$A$is a non-invertible function, then$N=I-A$causes$I-N=I - (I-A) = A$to be non-invertible. The thing is that the expression $$(I+N+N^2+\cdots)$$ makes no sense if$N$is not some special matrix. For example, if$N=I$, what is$I+N+N^2+\dots$? It equals an infinite sum of identity matrices and it ... 1 The Markov chain is not ergodic. Consider a (more general) matrix of the form $$P = \begin{pmatrix} p_{11} & 0 & 0 & p_{14} \\ p_{21} & p_{22} & p_{23} & p_{24} \\ p_{31} & p_{32} & p_{33} & p_{34} \\ p_{41} & 0 & 0 & p_{44} \end{pmatrix}.$$ We are interested in$Q := P^2$. By definition (of matrix ... 1 Fix$n \in \mathbb{N}$and measurable sets$B_1,\ldots,B_n. Using the tower property, we get \begin{align*} \mathbb{P}(Y_1 \in B_1,\ldots,Y_n \in B_n) &= \mathbb{E} \left[ \mathbb{E} \left( \prod_{j=1}^n 1_{B_j}(Y_j) \mid \mathcal{F}_{n-1} \right) \right] \\ &= \mathbb{E} \left[ \prod_{j=1}^{n-1} 1_{B_j}(Y_j) \mathbb{E}(1_{B_n}(Y_n) \mid ... 0 First of all: Yes, the summation is over all k \neq j; so in particular, we have to consider k=i (whenever i \neq j). For simplicity of notation, let's identifyA \longleftrightarrow 1 \qquad B \longleftrightarrow 2 \qquad C \longleftrightarrow 3.$$Then the mentioned formula gives$$m_{21} = 1+ p_{22} m_{21} + p_{23} m_{31} = 1+ \frac{3}{4} ... 0 So, as @Arkamis pointed out, what I had wrong is that (I-Q)^{-1} $shouldn't be a$ 2 \times 2 $matrix. I started with a mistake in$ I - Q $like this, which is wrong: $$I - Q= \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) - \left( \begin{array}{cc} 0.5 & 0 \\ 0 & 0 \end{array} \right)$$ One isn't to "expand"$ Q $to ... 0 Suppose that the matrix squaring is done. So, $$\left(\begin{array} \ P_2(A)&P_2(B)&P_2(C) \end{array}\right)=$$ $$=\left( \begin{array}{ccc}0.4 & b & (0.6-b)\end{array} \right) \left( \begin{array}{ccc} 0.8 & 0.1 & 0.1 \\ 0.2 & 0.75 & 0.05 \\ 0.1 & 0.1 & 0.8 \end{array} \right)^2=$$ $$=\left( \begin{array}{ccc}0.4 ... 1 That equality is justified by the following: \begin{eqnarray*} p(c\mid a) &=& \sum_b p(c\mid b,a)p(b\mid a) \qquad\qquad\qquad\text{(conditioning on b)} \\ &=& \sum_b p(c\mid b)p(b\mid a) \\ && \text{(Markov property: given b we know a,c are conditionally independent)} \\ && \\ \therefore\quad p(a)p(c\mid a) &=& ... 0 Let X, Y be random variable, then the condition expectation is given by$$ E(Y|X=x)=\int_{Y}yf_{Y|X=x}(x,y)dy=\int_{Y}y\frac{f_{X,Y}(x,y)}{f_{X}(x)}dy=\int_{y\in Y}y\frac{f_{X,Y}(x,y)}{\int_{t\in Y}f_{X,Y}(x,t)dt}dy $$where x is any element in X. Therefore E(Y|X=x) is function of x. Here the inner term f_{Y|X}(x,y) is precisely coming from ... 0 It is true that if X is an indicator of A, then the expected value happens of X is the probability of Z \in A (and this is true regardless of whether one conditions on Y). But that is not equivalent to saying that the definition of (conditional) expected value is equal to the definition of (conditional) probability. You have simply demonstrated ... 0 Here are some ideas: first it has to be true for a_i=1+r/i, and in this case we can explicitely compute the product b_n, which is equal to \prod_{i=1}^r(1+n/i). Taking K :=1/r!, we obtain that \prod_{i=1}^r(1+n/i)-Kn^r is of order n^{r-1}. For the general case, we have to control the quantity$$c_n :=\left|b_n-\prod_{i=1}^n \left(1+\frac ... 0 If$0<a,b\leqslant1$then$P_{ij}+P^2_{ij}>0$for all$i,j$so the Markov chain is (positive) recurrent. You can verify this by computing$\mathbb E_i[\tau_i]$where $$\tau_i = \inf\{n>0 : X_n=0\},$$ and$\mathbb E_i[\cdot]$denotes conditioning on$X_0=i$. If$a=0$(resp.$b=0$) then state$1$(resp. state$2$) is absorbing, and therefore ... 0 Intuition. This must be Markovian because you get from the value of$X_{n-1}$to the value of$X_n$by observing the new value$\xi_n$, which is independent of$X_{n-1}.$Thus only the 'position of the chain' at step$n-1$and the new value$\xi_n$determine the position at step$n,$and no prior values (from steps$n-2$and before) are relevant. "One-step ... 1 Since$V(\tau) \in \{0,1\}$, we have: $$S(t) = \int_0^t V(\tau)d\tau = \int_0^t 1\{V(\tau)=1\}d\tau$$ where$1\{V(\tau)=1\}$is an indicator function that is 1 if$V(\tau)=1$, and 0 else. Then$\lim_{t\rightarrow\infty} S(t)/t$is the limiting fraction of time being in state$1$, which you can work out via basic steady state theory (and the answer is ... 0 The recurrent classes do not affect each other. Once we get into one recurrent class, we never leave, and the structure of the other recurrent class is irrelevant. Just take an example, say with 4 states and transition probability matrix$(P_{ij})$given by: $$(P_{ij}) = \left[ \begin{array}{cccc} 0 & 1/2 & 1/2 & ... 0 Upon reflection, Matrix Z cannot be irreducible -- the upper left 3x3 matrix is an irreducible set in itself. Furthermore, if we have an irreducible set, all states within the set must be recurrent (i.e. the probability of revisiting that state is 1). This cannot happen if we have an absorbing state in the matrix. 0 The short answer is yes, because we account for the possibility of moving from any state to any state (and write a zero if this transition is not possible). This gives us n \times n elements, which is a square matrix. 2 Determining the stable (long term) state probabilities The solutions of the following system of equations are the stationary state probabilities:$$\begin{matrix}[\pi_A\ \pi_B \ \pi_C]\\ \\ \\ \end{matrix} \begin{bmatrix} 0.2 & 0.4 & 0.4 \\ 0.4 & 0.3 & 0.3 \\ 0.6 & 0.2 & 0.2 \\ \end{bmatrix} ... 2 The transition matrix must take into account not just the current position (that is to say, whether she is at$a$or$b$right now), but also the position she was at immediately before. This is because in order to know what the probability of switching positions is going to be, we must know both her current position and the position immediately preceding ... 1 The answer you provided can't obey the condition that being in a state for two consecutive steps requires a different probability from when you are only in a state for one step. To describe this situation, you need to set conditional probabilities which depend on the two previous states. If the last two states were$[\dots aa]$you transfer to$[\dots aab]$... 1 I believe this approach will work for your problem: Modify the state transition matrix as follows. Since both states$0$and$6$are absorbing states, and you start every new run at state$1$, identify states$0$and$6$as state$0$, and have state$0$go to state$1$with probability$1$. That is, the new matrix will look like this: $$A = \left[ ... 0 Since the process is irreducible, we can assume without loss of generality that X_0=0, and it suffices to show that \mathbb P(N_0<\infty)<1, where$$N_0=\inf\{n>0: X_n=0\}$$is the time until the first return to 0. Let$$F(s) = \mathbb E\left[s^{N_0}\right]$$be the generating function of N_0. It can be shown through some computation that ... 0 pi P = pi , and pi_0+pi_1+ ... +pi_n=1 where P is your matrix and pi=(pi_0 pi_1 ... pi_n) Here's what I started off with pi_0=kM(pi_1) pi_1=nL(pi_0)+kM(pi_2) pi_2=(n-1)L(pi_1)+kM(pi_3) ... pi_0+pi_1+ ... +pi_n=(pi_0)(1+1/kM{1+(n-1)/kM-(n-1)nL-(n-2)(n-1)L-...2*3L-1*2L})=1 Hopefully I didn't make any mistakes there with the simplification. Sorry ... 1 With respect to the game, this is exactly the St. Petersburg paradox. reference: http://en.wikipedia.org/wiki/St._Petersburg_paradox The game has infinite expected value but is worth only a finite amount in practice if that makes sense? 1 For a fixed A\in B_\infty, consider \mathcal L_A:=\{B: m(A\cap B)=m(A)m(B)\}. It suffices to show that each \mathcal L_A is a \lambda system, that is, L\in\mathcal L_A implies that L^c\in\mathcal L_A and if L_n\in \mathcal L_A for each n, and L_n\subset L_{n+1} (which is missing in the OP), then \bigcup_{n\geqslant 1}L_n\in \mathcal ... 0 If p and q are positive, you can conclude that all the states can be reached from all other states. So the chain is irreducible. However, it is not aperiodic. Because starting from state i you can come back to this state only in even number of steps. So period of state i is 2 for all i=0, \dots, n. For equilibrium mass function, you should solve ... 1 Look at P(N(t)-N(s)>0) \sim \mathrm{Poisson}(\lambda(t-s)) which is related to the independent increments property. if M \sim \mathrm{Poisson}(\lambda(t-s)), P(M>0) = 1-P(M=0) = 1-e^{\lambda(t-s)} 1 Regular Markov chain means that all the entries of the transition matrix P are positive. Let Markov chain have n states. If \pi _i is the equilibrium probability for state i, you can say:$$ \pi _i = \sum _{j=1}^n\pi _j P_{ji}$$Assume by contradition that$\pi _i=0$. Since all the entries of$P$are positive, from equation above you can conclude ... 0 The answers for (b) should be$E = 2n^2$I just wrote the detailed solution in my post in Multiple Anihilating Random Walks in a Ring. Look for "simple case". Please ask me if you have any questions. Also, the simple case deals with any initial distance between your cat and mouse. 1 It is easier to calculate the expectation directly than it is to write down the distribution. This is usually the case. Since you haven't said that much about what you've tried yet, let me start with a hint. Try to calculate the expected time to hit$\{ 0,n \}$starting from$x$with$0<x<n$. Then send$n \to \infty\$. You can set up a system of ...

Top 50 recent answers are included