2.5. Hidden Markov Models 21Figure 2.6 Markov chain with a(0, 1, 2) transition model. The choice of the futurestate depends only on the present state.For a new RSSI vector observation x the Bayes Decision Rule is used to decide for themost probable location s that explains the observation. This means evaluating theposteriors p( s| x) for all all locations, and selecting the location s with max( p( s| x)).Due to the unavailability of a direct form of p( s| x), the maximization is carried outover the known prior p( s) and the state-conditional p( x| s).If the prior p( s) is assumed to be constant for all s, then this will lead to the LMSEbased localization approach that will be described in section 2.7.2.5 Hidden Markov Models The Hidden Markov Model approach to the localization problem leads to the firstalgorithm that is based on the principles of Bayesian inference. But before thenature of the state-conditional is discussed, the formalism of the Markov Chain isintroduced to derive the source for the prior probability.The process of movement through space can be modelled as a Markov chain . Eachpossible discrete position in space, their number depends on the rasterization res-olution, translates to a state in the Markov chain. A Markov chain is a sequenceof states in a stochastic process where the Markov property holds. The Markovproperty refers to the memorylessnes of the process, that is given by the constraintthat a future state depends only on the present state and ignores all other precedinghistory.Such a Markov chain is parametrized by transition probabilities. The transitionprobabilities form a discrete probability distribution. A transition is the pair s s.The conditional probability for a transition, the probability that the future state sfollows after the present state s is given by p( s| s). The normalization constraint ofa PDF holds:p( s| s)= 1, ssA special transition model, allowing only three predecessor states, is the(0, 1, 2)-model(see figure 2.6) that is defined by:2p( s+ i| s)= 1i=0with s+ i representing a state index as the notation stis used for indexing overtime frames. The(0, 1, 2)-model is used for time alignment, that has the goal for