# Tag Info

## Hot answers tagged markov-chains

3

Are you sure you wrote this correctly? It didn't take me long to find a counterexample. Take $$P = \pmatrix{0 & 1\cr 1/2 & 1/2\cr},\ \Xi = \pmatrix{1/2 & 0\cr 0 & 1\cr},\ \Xi^2 - P^T \Xi^2 P = \pmatrix{0 & -1/4\cr -1/4 & 1/2\cr}$$

3

Hint: Define the random variable with $Y_n \in \{0,1\}$ (indicator variable with $2$ states) as follows $$Y_n=\begin{cases}1,& X_n=6\\0,&X_n\neq6\end{cases}$$ with transition matrix $$\mathbf P_{(1)}=\begin{array}{r|cc|r}&0&1&\\\hline0&\frac{4}{5}&\frac{1}{5}\\1&1&0 \end{array}$$ Initially $Y_0=1$. You want to find the ...

3

What about using the $\infty$-norm? That is $$\|A\|_\infty = \sup_{x: \|x\|_\infty=1} \|Ax\|_\infty.$$ Take a vector $x$. Then $$\|Px\|_\infty \le \max_{i}\left|\sum_j p_{ij} x_j\right| \le \max_{i}\sum_j p_{ij} (\max_k |x_k|) \le\|x\|_\infty.$$ Denote $z:=Px$. Then $$\|P^T\Xi^2 z\|_\infty = \max_i \left|\sum_j p_{ji}\xi_j^2 z_j\right| \le\max_i ... 3 These are not problems on a circle but on the linear interval of integers$$L=\{0,1,2,\ldots,12\},$$where the hand 12 is represented by both states 0 and 12, and every other hand by the state with its number. Starting from k in L, the mean number of steps t_k that the symmetric simple random walk needs to hit 0 or 12 is$$t_k=k(12-k),$$... 2 Sure. You just need to compute the eigenvalues that are not 1. In this case your eigenvalues are the solutions to \lambda^2-1.4\lambda+0.4=0, which are 1 and 0.4. This means that p A^n = \pi + 0.4^n v_p for some distribution v_p depending on p, and where \pi is the equilibrium distribution. Specifically v_p is the component of p in the ... 2 It's true. See for example Theorem 5.3 of this reference. The idea is that you can indeed apply the strong law of large numbers by splitting N_T(x)/T into excursion times: considering how long it takes to come back to state x when one has just reached state x. These excursion times are all independent of each other and hence the strong law applies. 2 The Markov chain of the residues mod 13 is irreducible and aperiodic on the finite state space \mathbb Z/13\mathbb Z and its transitions are invariant by translation hence the unique stationary distribution is uniform. Thus, for every i, P(X_n=i\pmod{13})\to\frac1{13} when n\to\infty. In particular, P(13\ \text{divides}\ X_n)\to\frac1{13} when ... 2 Consider a "renewal time" as a time when the number of customers goes from 1 to 0. After a renewal time, we wait Exponential(\lambda) time in each of the states 0, 1_u, \ldots, (n-1)_u: a total expected time n/ \lambda of which an expected time 1/\lambda is spent in state 0. Then the server becomes active, and we are in a "normal" M/M/1 queue ... 2 A finite Markov chain always has at least one steady-state distribution. If the transition matrix is A, each column of A-I sums to 0, so A-I doesn't have full rank, and there is at least one nontrivial solution to Ax=x. On the other hand a Markov chain with an infinite state space doesn't have to have a steady-state distribution. For example, ... 2 The question asks to compute P^n for every n, where$$2P=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}=3J-I,\qquad 3J=\begin{pmatrix}1&1&1\\1&1&1\\1&1&1\end{pmatrix}.$$This is pure algebra, only, playing with 3\times3 matrices in the ring \mathbb R[J]. Note (and this will be the only matrix ... 1 Let Y_k be a random variable which is 1 if X_k = j and 0 otherwise. Observe that V_n = \sum_{k=1}^n Y_k. Then use linearity of expectation. 1 You should exploit the symmetry of the Markov chain and of the state space. Try to work out the case with 4 points on a circle, then 6 points and then you should have understood how to solve the case of 2n points on circle. 1 Denote with 1 it's starting position. Let h(i) be the expected number of steps to return to the position 1 starting from position i for i=1,2,\ldots 12. To avoid confusion it can be helpful to denote state 1 (the initial state) as state 13 when you visit it the second time. With this notation you have that ... 1 In my opinion, the tricky bit is to figure out a way of sampling the space of walks that you are interested in. Luckily, the problem is a classic one in polymer physics (e.g. modelling a 2d ideal polymer on a square lattice between fixed points), with an added constraint. Well, actually the constraints are two: the lengths of the segments in both ... 1 Let X_t be the number of busy servers in a M/M/\infty queuing system. You want to compute E(X_t|X_0=n). This can be done by considering the sum$$X_t=Y_t+Z_t,where \{Y_t|X_0=n\}\sim Binomial(n,e^{-\mu t}) is the number of servers that did not complete service in the interval (0,t] (out of the n that were busy), and Z_t\sim ... 1 Are we allowed to note that this is the dynamics of a population such that every living individual gives birth to one new individual at rate \lambda and dies at rate \mu, independently of the other living individuals? Because this is what rates proportional to the population are modelling, actually... Then one sees that a population of i\geqslant1 ... 1 I think you are struggling because you are misunderstanding what we are intending to describe with the term steady state. You are correct, a Markov Chain is completely determined once it is defined. That means, no matter what step (or time) you are interested in, I can find the distributions for that step. This property is known as uniqueness. Though, that ... 1 0\to1\to0\to1\to0\to1\to0\to1\to0\to1\to0\to1\to0\to1\to0\to1\to\ldots -- Did From state 0 you go to state 1 with probability 1 and from state 1 you go to state 0 with probability 1. -- Ritz 1 An elementary argument we can make is as follows: Define by d_n the expected number of deaths occurring before we reach state n+1 given that we start in state n. We clearly have d_0=0. Further we can write an expression for d_n noting that, with, probability \lambda_n, we will have no deaths before reaching state n+1, and with probability ... 1 I was able to figure it out eventually... 1. \begin{align*} &\sum_{i \in J} \left|\frac{V_i(n)}{n}-\pi_i\right| + \sum_{i \notin J} \left(\frac{V_i(n)}{n}+\pi_i\right)\\ &= \sum_{i \in J} \left|\frac{V_i(n)}{n}-\pi_i\right| + \left(1-\sum_{i \in J} \frac{V_i(n)}{n}\right)+\sum_{i \notin J}\pi_i & \sum_{i \in I} V_i(n)=n\\ &= \sum_{i \in J} ... 1 By the Gershgorin's theorem , for every eigenvalue \lambda of \Xi(Id-P) exists j such that |\Xi_{jj}(1-P_{jj})-\lambda|\leq\Xi_{jj}(\sum_{i\neq j }|-P_{ji}|) Now, notice that for every j, \Xi_{jj}(1-P_{jj})=\Xi_{jj}(\sum_{i\neq j }P_{ji})=\Xi_{jj}(\sum_{i\neq j }|-P_{ji}|)\geq 0. Thus, |\Xi_{jj}(\sum_{i\neq j ... 1 Your approach is certainly right: superharmonic functions form a convex cone, that is if f and g are superharmonic, then \alpha f + \beta g is superharmonic for non-negative \alpha and \beta. Moreover, if f and -f are superharmonic then f is harmonic, so the whole question is to construct an example when there are superharmonic functions that ... 1 As often, it is difficult to answer this question because the OP says nothing about their background. Anyway, a standard approach to determine the recurrence/transience of a Markov chain (its type) is to compute P_1(T_0\,\text{infinite}) as the limit of P_1(T_n\lt T_0) when n\to\infty, since each P_1(T_n\lt T_0) involves only a finite Markov chain. ... 1 Consider some nonnegative integers i and j. To reach i+j starting from 0, one must first reach i starting from 0 then reach i+j starting from i. The probability of the first event is d_i. By the Markov property and the invariance of the dynamics by the translations of \mathbb Z, the property of the second event conditionally on the ... 1 The relatively high number of states is only there to force you to understand the structure of the paths the Markov chains can follow to reach state 20 starting from state 11. Thus, a mandatory prologue to the proof is to draw a picture of the states and the transitions of the Markov chain... Once this is done (and if you did not do it, the proof below ... 1 What you're confusing is the idea of the existance invariant measure and convergence to the invariant distribution. A lot of Markov chains have invariant measures (in fact, on a finite state space you always have at least one, and in general for irreducibility a null recurrent chain will have an invariant measure and positive recurrent will have invariant ... 1 Let u=(1,\ldots,1). Notice that P^t\Xi u=\Xi u and Pu=u. Therefore, P^t\Xi Pu=P^t\Xi u=\Xi u . So, \Xi_{ii}=\sum_{j=1}^n\Xi_{ij}=\sum_{j=1}^n(P^t\Xi P)_{ij}. Next, \Xi_{ii}-(P^t\Xi P)_{ii}=\sum_{j\neq i}(P^t\Xi P)_{ij}=\sum_{j\neq i}|-(P^t\Xi P)_{ij}|\geq 0. Therefore, \Xi-P^t\Xi P is diagonally dominant symmetrix matrix with non ... 1 Let Y=X_{T_S} andC=\left[\lim\limits_{\alpha\to\infty}X_\alpha=Y\right]. For every fixed $\alpha$, on the event $[T_S\leqslant\alpha]$, $X_\beta=Y$ for every $\beta\geqslant\alpha$ hence $X_\beta\to Y$ when $\beta\to\infty$. This proves that $[T_S\leqslant\alpha]\subseteq C$. This inclusion holds for every $\alpha$ and ...

1

In addition to your comment: Let $P$ be a stochastic, irreducible matrix. Since $P$ is irreducible it will be either aperiodic or periodic. $P$ aperiodic$\iff\displaystyle\lim_{k\to\infty}P^k$ exists. $P$ periodic matrix with period $d>1$ $\iff \displaystyle\lim_{k\to\infty}P^k$ does not exist. We can prove the latter using cyclic subclasses.

1

I think so... Here's my thought. Let $M$ be an irreducible, symmetric and positive-definite $n\times n$ stochastic matrix, with spectrum $\sigma(M)=\{\lambda_1, \lambda_2,\ldots, \lambda_n\}$. Since $M$ is stochastic, we have that $\lambda_1=1$. Since $M$ is symmetric we have that $M$ is diagonalizable. Since $M$ is positive definite, we have that all ...

Only top voted, non community-wiki answers of a minimum length are eligible