There is a robot on the checkered plane. On each move, the robot randomly decides with equal probability to move one square in one of four directions (forward, back, left or right) and implements the decision made.

It is necessary to determine how many bits of information carry the message that, as a result of the fourth move, the robot was two cells to the right of its original position.

My reasoning:

There are a total of 25 different positions where the robot may end up after 4 equally probable moves; there is one requested position -> the amount of information is log (25) = 5 bits. Where am I mistaken in reasoning? Thanks in advance, I will be very grateful.

    1 answer 1

    You should consider not the final positions (they are not equiprobable), but the ways (they are equiprobable).

    There are 4 total paths to the 4th degree, i.e. 256. The paths leading to the end point are: EEEW and various permutations (4 pcs.), And EENS and various permutations (4! / 2 = 12 pcs.), in the amount of 16 ways.

    Total your information says that there were 16 options out of 256 possible. Calculate the logarithm yourself.