Markov localization estimates the posterior distribution over 
conditioned on all available data, that is
Before deriving incremental update equations for this posterior, let
us briefly make explicit the key assumption underlying our derivation,
called the Markov assumption. The Markov assumption, sometimes
referred to as static world assumption, specifies that if one
knows the robot's location 
, future measurements are independent
of past ones (and vice versa):
In other words, we assume that the robot's location is the only state in the environment, and knowing it is all one needs to know about the past to predict future data. This assumption is clearly inaccurate if the environment contains moving (and measurable) objects other than the robot itself. Further below, in Section 3.3, we will extend the basic paradigm to non-Markovian environments, effectively devising a localization algorithm that works well in a broad range of dynamic environments. For now, however, we will adhere to the Markov assumption, to facilitate the derivation of the basic algorithm.
When computing 
, we distinguish two cases, depending
on whether the most recent data item 
is a sensor measurement
or an odometry reading.
Case 1: The most recent data item is a sensor measurement 
.
Here
Bayes rule suggests that this term can be transformed to
which, because of our Markov assumption, can be simplified to:
We also observe that the denominator can be replaced by a constant
, since it does not depend on . Thus, we have
The reader may notice the incremental nature of Equation (7): If we write
to denote the robot's belief Equation (7) becomes
In this equation we replaced the term 
by 
based on the assumption that it is independent of the time.
Case 2: The most recent data item is an odometry reading: 
.
Here we compute using the Theorem of Total
Probability:
Consider the first term on the right-hand side. Our Markov assumption suggests that
The second term on the right-hand side of Equation (10) can also be
simplified by observing that 
does not carry any information
about the position 
:
Substituting 12 and 14 back into Equation (10) gives us the desired result
Notice that Equation (15) is, too, of an incremental form. With our definition of belief above, we have
Please note that we used 
instead of 
since we assume that it does not change over time.
