What is the official name of this problem? Martin Gardner gives introduction in his book "Math circus". The problem belongs to 1D random walk. What can be read to gain deep insight into this problem? Or other useful resources.
We can complicate matters by allowing transition probabilities to vary from 1/2 and by allowing steps longer than one unit. Consider the following curious paradox first called to my attention (in betting terms) by Enn Norak, a Canadian mathematician. A walker starts 100 steps to the right of 0 on a line that has no barriers. Instead of a coin a packet of 10 playing cards-five red and five black-is used as a randomizer. The cards are shuffled and spread face down and any card is selected. After its color is noted it is discarded. If it is red, the walker steps to the right: if black, he steps to the left. This continues until all 10 cards have been taken. (The transition probability varies with each step. It is 1/2 only when there is an equal mixture of red and black cards before the draw.) The walk differs also from walks discussed above in that before each card is noted the walker chooses the length (which need not be integral) of his next step. Assume that the walker adopts the following halving strategy in choosing step lengths. After each card is noted he takes a step (left or right) equal to exactly half of his distance from 0. His first step is 100/2 = 50 units. If the card is red, he goes to the 150 mark. His next step will then be 150/2 = 75. If the first card drawn is black, he goes left to the 50 mark, and so his next step will be 50/2 = 25. He continues in this manner until the tenth card is noted. Will he then be to the right or to the left of the 100 mark where he began the walk? The answer is that he is sure to be to the left. This may not be very surprising, but it is surely astonishing that, regardless of the order in which the cards are drawn, he will end the walk at exactly the same spot.
