# Tag Info

## Hot answers tagged markov-chains

2

Have you really looked at a hidden markov model in graphical form? I'm guessing a lot of things would become clearer if you did so. For (1) Yes, you need to have the Markov property to show that $p(\mathbf{O_t}|q_1, q_2,\ldots, q_T) = \prod_t p(o_t|q_t)$. Otherwise, you would have the more general expression. Let me just demonstrate with a simple example. ...

2

Assume that the random walk is defined as $$X_n = \sum_{k = 1} ^ n \xi_k$$where $(\xi_a)_{a\ge 1}$ are iid and such as $P(\xi_1 = \pm 1) = 1/2$. $$1_{T_0 = m,X_0=0} = 1_{T_0 = m,X_0=0, X_1 = 1}+ 1_{T_0 = m,X_0=0, X_1 = -1}$$ Now using the Markov property, and as $T_0$ depends in a deterministic way on $(X_a)_{a\ge 1}$, you get $$T_0 |(X_0=a, X_1 = ... 2 Here is an interpretation of the original question. Assume the states are S_i, each representing the event that there are exactly i non-empty boxes. Clearly, we have$$p_{ij} = \begin{cases}i/k & \text{if }i = j \\ 1-i/k & \text{if } j = i + 1 \\ 0 & \text{otherwise}.\end{cases},$$where i,j\in\{0,1,\dots, k\}. This gives us a Markov chain ... 1 To compute P(j\cap i), the probability of reaching i having reached j as minimum, consider playing two games after each other: G Is the game that is won by starting from zero, ending at j without having reached i H is the game that is won by starting from j, ending at i without having reached j-1 For the first one we have$$ ...

1

Obviously, $$P(W_1 > w_1, W_2 > w_2 ) = \int_{0}^{1}\int_{0}^{1}f(x, y)\ \text dx\text dy$$ cannot be correct because the lhs is a function of $w_1$ and $w_2$ while the rhs, being a real number, isn't. Furthermore, recall that by the definition of probability density functions, if $f(w_1, w_2) = \lambda^2e^{-\lambda w_2}{\bf ... 1 For intuition, think about a recurrence relation, say$a_n = a_{n-1} + a_{n-2}$. You can turn this into a first order recurrence in two variables by writing$a_n = a_{n-1} + b_{n-1},b_n = a_{n-1}$. We do the same thing to turn higher order differential equations into first order differential equations. Do the same thing for your Markov chain: given the ... 1 Assume discrete time$t \in \{0, 1, 2, \ldots\}$. Let$Z(t)$be the value of your Markov chain, so$Z(t) \in \{s_1, s_2\}$. Let$R(t)$be the observation on slot$t$(assume$R(t) \in \{a,b\}$). Assume that$Pr[R(t)=a|Z(t)=s_1] = 0.25$,$Pr[R(t)=a|Z(t)=s_2]=0.5$. Let$H(t)$be the history of observations up to time$t: $$H(t) = [R(0), R(1), \ldots, ... 1 Note that unless you're distinguishing between the players in some way (e.g., modeling their different skill levels), then their identities don't matter, and you can work with a much smaller number of states. To see how this works, imagine that each live player is "stuck" to all the players that he has frozen. So if a live player has frozen n other ... 1 The classical example of the first case is b = a + c where a and c are independent fair Bernoulli variables, P(a=1)=P(a=0)=1/2, and the sum is modulo 2 (XOR). Then I(a;b)=0 (knowing one of the inputs tells you nothing about the output) and I(a;b|c)=1 (given that one of the inputs is know, to know the other is to know the output). For the ... 1 The idea is this, you start with a vector x and write it out in the eigenvalue basis of the PageRank matrix. Suppose that 1=\lambda_{1}> |\lambda_2|\geq ...\geq |\lambda_{n}|. We write$$x=a_1 v_{1} + a_2 v_{2} +... + a_{n}v_{n}Now multiplying by A (both sides k times) we have: \begin{align*} A^{k}x &= \lambda_{1}^{k} a_{1}v_{1} + ... 1 Assume we have a state space S = \{1,2, \ldots, k\}. Then the sum of the elements lying on m- row of the transition matrix is:\sum_{i=1}^k p_{mi}\begin{array}[t]{l}=p_{m1}+p_{m2}+\cdots+p_{mk} \\ =prob\{X_n=1\, \mid X_{n-1}=m\}+\cdots+prob\{X_n=k\, \mid X_{n-1}=m\} \\ =prob\left\{(X_n=1)\cup (X_n=2) \cup \cdots \cup (X_n=k)\, \mid ... 1 First of all, any right-stochastic matrixA$has an eigenvalue of$1$. This is easiest to see because$A^T$has$\begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix}$as an eigenvector. So$A$also has an eigenvalue of$1$. Provided all entries of the corresponding eigenvector have the same sign, the eigenvector can be normalized to obtain a stationary ... 1 Starting with the definition,$\newcommand{\prob}{\mathbb{P}}$$$\prob(X_n = x_n | X_{n-1} = x_{n-1},…,X_0 = x_0 ) = \prob(X_n = x_n | X_{n-1} = x_{n-1})$$ Then let$j_1...j_N$be a labelling of$\{0,1,2,3,...,t_n\}\setminus \{t_1,t_2,...,t_n\}. You just need to sum over the values you don't specify in the conditioning: \begin{align} &\prob(X_{t_n ... 1 Double check the definition of the period. First off, a period always refers to a particular statei$. Specifically it's the GCD of all times$k$for which a return is possible. So figuring out the "shortest time of return" is not sufficient. Next, a state$i$is aperiodic if its period is 1. A Markov Chain is aperiodic if all states have period 1. In ... 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 ...

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