Sebastian says we can post our code to the forum and discuss, but not many people have done it so far. Well, I think someone has to start.. and I love code reviews! :)

#!/usr/bin/env python

def sense(cols, sensor_prob, pr, z):
    return norm([[i * (sensor_prob if c == z else (1. - sensor_prob))
                  for (c, i) in zip(*lines)]
                 for lines in zip(cols, pr)])

def norm(pr):
    s = sum(sum(ln) for ln in pr)
    return [[i / s for i in ln] for ln in pr]

def shift_one(pr, U):
    U %= len(pr)
    return pr[-U:] + pr[:-U]

def shift(pr, U):
    (v, h) = U
    return [shift_one(ln, h) for ln in shift_one(pr, v)]

def mul(pr, c):
    return [[i * c for i in ln] for ln in pr]

def add(*ps):
    return [[sum(val) for val in zip(*lines)] for lines in zip(*ps)]

def move(move_prob, pr, U):
    return add(mul(shift(pr, U), move_prob),
               mul(shift(pr, [0, 0]), 1 - move_prob))

def move_and_sense(cols, sensor_prob, move_prob):
    def move_and_sense_impl(pr, zu):
        (z, U) = zu
        return sense(cols, sensor_prob, move(move_prob, pr, U), z)
    return move_and_sense_impl

def show(pr, prec=6):
    for ln in pr:
        print '[' + ', '.join('%.*f' % (prec, x) for x in ln) + ']'

################################################################

def main(colors, measurements, motions, sensor_right, p_move):
    show(reduce(move_and_sense(colors, sensor_right, p_move),
                zip(measurements, motions),
                norm([[1.] * len(ln) for ln in colors])))

## main(colors = [['green', 'green', 'green'],
##                ['green', 'red',   'red'  ],
##                ['green', 'green', 'green']],
##      measurements = ['red', 'red'],
##      motions = [[0, 0], [0, 1]],
##      sensor_right = 0.8,
##      p_move = 1.0)

## -------------------------------------------------------------

main(colors = [['red', 'green', 'green', 'red',   'red'],
               ['red', 'red',   'green', 'red',   'red'],
               ['red', 'red',   'green', 'green', 'red'],
               ['red', 'red',   'red',   'red',   'red']],
     measurements = ['green', 'green', 'green', 'green', 'green'],
     motions = [[0, 0], [0, 1], [1, 0], [1, 0], [0, 1]],
     sensor_right = 0.7,
     p_move = 0.8)

P.S. This is not exactly the code I've submitted, but it's pretty close (modulo the show() and main() functions)