Discover where Bob is sleeping using hidden Markov chains

Question

Bob lives in four different houses $A, B, C$ and $D$ that are connected like the following graph shows:

Bob likes to sleep in any of his houses, but they are far apart so he only sleeps in a house adjacent to the one in which he slept the previous night. To clarify, this means that if Bob slept in house $A$ on night $1$, he may sleep in house $A$, $B$ or $C$ on night $2$ (not house $D$). The probability of each case is the same (one third); on each day, Bob takes a random walk from where stayed the previous night (and he might stay put).

Now Bob is a wanted criminal so on a given night the FBI would like to estimate where Bob is sleeping. Data from a satellite gives us the following probabilities of where Bob is sleeping on night $1$ and night $2$ (and any subsequent nights):

         Night 1   Night 2   ...
House A  0.8       0.05      ...
House B  0.1       0.4       ...
House C  0.05      0.05      ...
House D  0.05      0.5       ...

How can we use this data to calculate the probability of where Bob was sleeping on night $2$, for example calculating the probability Bob slept in house A? Could we use that method iteratively to calculate where Bob was sleeping on night $n$ if we continue to receive satellite data for each night?

Note: I made up this problem to understand better how hidden Markov chains work because I am interested in seeing the calculations on a concrete example. Many thanks for any input.

Answer 1

So far no one has given an answer to the problem containing a solution, so I will post what I believe to be the solution.

We assume a uniform distribution initially, so the actual probabilities at night $1$ equal exactly the value in the table for the first night. Next step is to calculate for each house $k = \{A, B, C, D \} $ the following value:

$ S_2(i) \cdot \sum_{i \in N(k)} \frac{S_{1}(i)}{n(i)+1}$

where $N(k)$ is the set of neighbours of $k$ in addition to $k$ itself, $S_x(i)$ is the satellite probability of Bob sleeping at location $i$ on day $x$, and $n(i)$ is the number of neighbours of $i$. The reason this formula is relatively simple is because Bob takes a random walk at every night with each of his options equally likely - if he had a preference for one house over another, the above formula would be more complicated.

We begin by calculating the formula for $k=A$ and get $0.05 \cdot (0.05/(2+1) + 0.1/(2+1) + 0.8/(2+1)) = 0.0158$. The values for $k=B, k=C$ and $k=D$ can be found likewise to be $0.1267, 0.0158, 0.0333$. Normalizing, we find that the sum of all four values is $0.1917$, so the true probability that Bob is sleeping in house A on night $2$ is $0.0158/0.1917 = 8.2 \%$, and likewise the other probabilities for $B$, $C$ and $D$ are $66.1 \%$, $8.2 \%$ and $17.4\%$ respectively.

We perform a short sanity check and see that the probabilities correspond roughly with what we would expect; it seems most likely that Bob was indeed sleeping in house $B$, with $D$ being the next-most likely candidate, and $A$ and $C$ should be equally unlikely.

Answer 2

If $K \in \{ A, B, C, D \}$, I write $K_n$ for the event 'Bob is in K on night n'.
Then what you have is:

\begin{align*} P[A_{n+1}] &= P[A_{n+1} \cap A_n] + P[A_{n+1} \cap B_n] + P[A_{n+1} \cap C_n] + P[A_{n+1} \cap D_n] \\ &= P[A_{n+1} \mid A_n] P[A_n] + P[A_{n+1} \mid B_n] P[B_n] + P[A_{n+1} \mid C_n] P[C_n] + P[A_{n+1} \mid D_n] P[D_n] \\ &= P[A_n]/3 + P[B_n]/3 + P[C_n]/3 + 0. \end{align*}

Answer 3

You may want to look at this. http://en.wikipedia.org/wiki/Viterbi_algorithm

Answer 4

The goal is to update probability of Bob given satellite measurements.

The state of Bob at time $k$ is given by $x_{k}$. The measurement of a satellite is $y_{k}$. Since no prior information is given, we initialize with a uniform distribution $$ \text{for } i={A,B,C,D},\,\, p(x_{0}=i|y_{0})=1/4.$$

Now that we have initialized, let's use Baye's rule to get $p(x_{1}=i|y_{0},y_{1})$. I'm only going to do this for i=A. Baye's rule yields

$$ p(x_{1}=A|y_{0},y_{1}) = \frac{p(x_{1}=A \cap y_{1}|y_{0})}{p(y_{1}/y_{0})}. $$ Now we just fill in the blanks. First, I like to calculate my "prediction", which is

$$ p(x_{1}=A | y_{0}) = \sum_{x_{0}\in{A,B,C,D}} P(x_{1}=A|x_{0})P(x_{0}|y_{0}).$$

Assuming bob is equally likely to stay in the house, or go to an adjacent house, this value is 3*(1/3)*1/4 = 1/4, and for this iteration at least, the prediction for other states is the same value. Now let's take a look at the Baye's Rule equation we outlined earlier

$$ p(x_{1}=A \cap y_{1}|y_{0}) = p(y_{1}|x_{1}=A)p(x_{1}=A|y_{0})=1/5$$

Finally,

$$ p(y_{1}/y_{0}) = \sum_{x_{1}\in{A,B,C,D}} p(y_{1}/x_{1})p(x_{1}/y_{0}). $$

This comes out to be 1/4. Finally,

$$ p(x_{1}=A|y_{0},y_{1}) = \frac{1/5}{1/4} = 4/5. $$