Tag Info

New answers tagged

1

The transition probabilities from one node to the other nodes have to sum up to $1$. This is true even if there is only one path out of a certain state. In what follows let $A^n$ the $n^{th}$ state and let $A_{i}^{n+1}$ denote the $(n+1)^{st}$ state of the Markov chain. Also, suppose that $P(A^n)>0$. $(i=1,2, ... m)$ Then $$\sum_{1} ...


1

1) We can assume without loss of generality that $X$ starts in $C$, as otherwise we could consider the Markov chain $\{X_\tau, X_{\tau+1},\ldots\}$ where $\tau = \inf\{n\geqslant 0 : X_n\in C\}$. 2) If $X_0\in C$, then $X_n\in C$ for all $n$. Since $C$ is finite, if each state were visited only finitely many times, this would contradict the fact that $X_0, ...


0

If we define the limit distribution $\nu$ by $d(\mu P^n, \nu) \to 0$ with some distance $d$ in the distribution space and the initial distribution $\mu$, then what we want to prove is $d(\nu, \nu P) = 0$. This is true if $P$ reduces the distance, i.e. if $d(\mu_1 P , \mu_2 P) \le d(\mu_1, \mu_2)$, because $$d(\nu,\nu P) \le d(\nu, \mu P^n) + d(\mu P^n, \nu ...


1

Consider a Markov chain on the integers where it moves right with probability 1. The limit distribution is all zeros, but this doesn't qualify as an invariant distribution because it needs at least one positive entry.


0

I see no difference between the two expressions. One says something about $Z_0=i_0,Z_1=i_1,\cdots Z_n=i_n$ for all $i_k\in S$ and the other says $(Z_0,...Z_n)=\Sigma$ for all $\Sigma\subset S^{n+1}$ (assuming you have a typo). You're on a discrete set, so obviously the two imply each other by writing out $\Sigma$ as a union over all tuples in it and using ...


1

It isn't . See Renewal Theory. If you are talking about the time of the next event $T_{N+1}$ given the time of the last event $T_N$, then the Markov Property is that $P(T_{N+1}|T_N,T_{N-1}...)=P(T_{N+1}|T_{N})$. Nothing precludes the interarrival times from being any distribution, provided that inter-arriveal times are iid. Note also that the markov ...


1

Let's write out the transition matrix of $X$ when $a = 1$: $$\mathcal P = \frac{1}{10} \begin{bmatrix} 1 & 3 & 0 & 1 & 5 & 0 \\ 2 & 2 & 1 & 0 & 1 & 4 \\ 6 & 0 & 1 & 1 & 2 & 0 \\ 6 & 0 & 1 & 1 & 0 & 2 \\ 3 & 0 & 4 & 1 & 0 & 2 \\ 3 & 0 & 1 & 4 & ...


0

I also stumbled upon this problem. I did not solve (a) and (c) so far, but for you specific questions I have the answer. If drawing the flow diagram of the Markov chain up to 4 steps from $(1,2)$ (i.e., about $2^4$ states can be reached), one notices, that one step into the wrong direction (e.g., from $(1,2)$ to $(2,3)$ requires 2 steps back. An example: ...


0

Markov Chains are stochastic processes $\{X_n\}$ such that $X_n$ depends only on $X_{n-1}$, in the sense that $\mathbb{P}(X_n = a_n \mid X_{n-1} = a_{n-1}, \ldots, X_1 = a_1) = \mathbb{P}(X_n = a_n \mid X_{n-1} = a_{n-1})$. This still holds here, as both sides equal $1/3$, although the "dependence" is in this case is rather trivial.


0

Please look here: http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem. You should only to verify that your matrix P satisfies the conditions of this theorem but it shouldn't be so difficult.


0

Filtering is when you are only allowed to use past data to make an estimate. Smoothing is when you are allowed to use both past and future data to make an estimate. There are many filters for various types of HMM models. A Kalman Filter works on a linear-gaussian HMM model. A Markov process is one where all future states can be determined by only the ...


0

Please look my answer to this question. In a nutshell, the following theorem should help you. Theorem. (Gantmacher F.R. The Theory of Matrices, 1960, Vol. 2, P. 81, Theorem 9.) If $A \geqslant 0$ is an irreducible matrix and some power $A^q$ of $A$ is reducible, then $A^q$ is completely reducible, i.e., $A^q$ can be represented by means of a premutation in ...


0

I believe the answer is given by the theorem. Theorem. (Gantmacher F.R. The Theory of Matrices, 1960, Vol. 2, P. 80, Theorem 8.) A matrix $A \geq 0$ is primitive if and only if some power of $A$ is positive: $A^p > 0$ ($p \geq 1$). Proof of the theorem can be found in the book. Actually the answer depends if the statement should be understood like this ...


0

It means that all states make up a single subclass. In other words, it means that matrix $P$ is primitive (as also noted in comments by @Did it's aperiodic which I believe is another term for that). This can easily be seen from the following theorem: Theorem. (Gantmacher F.R. The Theory of Matrices, 1960, Vol. 2, P. 81, Theorem 9.) If $A \geqslant 0$ is an ...


0

Define $A_k = \{X_k \in S_k, X_{k-1} \in S_{k-1}, \ldots, X_1 \in S_1\}$. Assume that $Pr[X_1=j]$ is known for all $j \in S_1$. For $k>1$, note that $Pr[A_k|A_{k-1}] = \frac{Pr[A_k, A_{k-1}]}{Pr[A_{k-1}]} = \frac{Pr[A_k]}{Pr[A_{k-1}]}$. For $k>1$ define: \begin{align} q[k] &= Pr[A_k|A_{k-1}]\\ r_j[k] &= Pr[X_k=j|A_{k-1}] \: \: \forall j ...


1

Note that $P = P_1 \otimes P_2$ is the transition matrix of the process $(X^1,X^2)$ where $X^1$ is a Markov chain of transition matrix $P^1$, $X^2$ is a Markov chain of transition matrix $P^2$, and $X^1$ and $X^2$ are independent. Thus, if $\pi^1$ is stationary for $P^1$ and $\pi^2$ is stationary for $P^2$ then $\pi^1\otimes\pi^2$ is stationary for $P$. ...


0

If you haven't misquoted your professor's words, he/she was plainly wrong. The adjacency matrix $$ \left[\begin{array}{cc|cc|cc}0&1\\ 0&0\\ \hline&&0&1\\ &&1&0\\ \hline&&&&0&1&1\\ &&&&1&0&1\\ &&&&1&1&0\end{array}\right], $$ for instance, has not a complete ...


0

See maybe the article "Monotone matrices and monotone Markov processes" by Keilson and Kester (1977), and more precisely the discussion after Theorem 1.4.


0

For every $x\geqslant4$, $$\pi_x=p_{2,4}\pi_{x-2}+p_{2,3}\pi_{x-1}+p_{2,2}\pi_{x}+p_{2,1}\pi_{x+1}+p_{2,0}\pi_{x+2},$$ hence the generating function $$\Pi(s)=\sum_{x\geqslant0}\pi_xs^x,$$ solves the identity $$\Pi(s)=(p_{2,4}s^2+p_{2,3}s+p_{2,2}+p_{2,1}s^{-1}+p_{2,0}s^{-2})\Pi(s)+s^{-2}R(s),$$ for some polynomial $R(s)$ of degree at most $5$, in particular, ...



Top 50 recent answers are included