MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

closed as off topic by Gerry Myerson, Douglas Zare, Bruce Westbury, Gerald Edgar, Qiaochu Yuan Jul 16 '11 at 4:47

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

So... on black cards his distance from 0 is multiplied by $\frac 12$, and on red cards it's multiplied by $\frac 32$. There are 5 of each, so after 10 steps his distance from 0 has been multiplied by $\frac {3^5}{2^{10}}$, regardless of order. There doesn't seem to be much more to it than that, or am I missing something? If you take logs, it turns back into a regular random walk, and you know how many total steps are taken each way. – Vaughn Climenhaga Jul 13 '11 at 23:05
The name I'd give it is "multiplication is commutative". – Robert Israel Jul 13 '11 at 23:42
The question seems to presuppose that such puzzles have official names. Rather few have names at all, and I know of no way for a name to become "official". – Andreas Blass Jul 13 '11 at 23:51
I don't see much of a future in Robert Israel's becoming a puzzle writer. (If he shouts spoilers out in theatres. I don't think I'll go to the movies with him either.) Gerhard "Multiplication Can Also Be Associative" Paseman, 2011.07.13 – Gerhard Paseman Jul 14 '11 at 1:02
I don't think Gerhard is objecting to the presence of Robert's comment here but to the idea of using "multiplication is commutative" as the name of the puzzle. Standard practice is that the name of a puzzle should not give away the answer. – Andreas Blass Jul 14 '11 at 1:22
up vote 1 down vote accepted

Sure, multiplication is commutative, but there is more to it than that. While being reasonably easy, this puzzle suggests variations in ways that the equation $x\cdot y = y\cdot x$ doesn't.

In his wonderful paper Games People Don't Play,, Peter Winkler describes essentially the same game as ``Next card color betting'' (a bit of googling also turns up and But there the player, Victor, wants to end up as far to the right as possible (increasing his bankroll). It turns out that there is a strategy that guarantees him to end up with $2^{10}/\binom{10}{5} = 256/63$ times his initial bankroll, or about 406 steps to the right of the origin.

This is a game that children can understand, but if we pursue the analysis, it doesn't stop until we have developed, besides insights into hedging strategies, a good deal of nontrivial mathematics including information theory (the amount of information Victor has about the red-black sequence dictates exactly how much money he will ideally make by betting), the Wallis product formula (showing that his final bankroll is asymptotically $\sqrt{\pi n}$ for a deck of $n$ red and $n$ black cards), and even the central limit theorem.

share|cite|improve this answer
Thanks a lot. Do you know variation of this problem when the exact number of cards is unknown? – columbus Jul 14 '11 at 19:06

Here's another expression of the same trivial puzzle. I buy some shares for $1000. In five of the next ten weeks (I'm not saying which five), their price rises by 50%; in the other five, it falls by 50%. What are my shares now worth?

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.