[Guest]

I've decided that rolling cube-shaped dice is too old-fashioned, and have instead painted the numbers 1 to 6 evenly around a wheel. Every time a dice roll is required I toss a coin. If it lands on heads, I turn the wheel one-sixth of a turn clockwise, if it lands on tails, I turn the wheel one-sixth of a turn anticlockwise. I then call out the number at the top. This gives me a fun and useful random number generator. Before commencing I will give the wheel a good spin so the number I start from will be random.

What is the average number of turns it will take to produce a 6?

EDIT (for clarity): Each turn consists of a coin toss followed by 1/6 rotation depending on the coin toss. The spin happens only once, before we start making turns, to give us a random starting point. The result of the spin doesn't count as a turn in itself, so if the spin lands on 6 we haven't done a 6 in zero turns.

[Guest]

This is a very challenging puzzle, but as a mathematician with a love for probability, I'd like to point out that the average number of rolls of a die needed to get six is not six.

[Prime]

Ok, so this is kind of cheating and by no means eloquent, but it's been to long since I took Probability and Stats... so I brute forced this one by simulating it in an excel spreadsheet. Here's how I basically did it:

1) Random number generator 1-6 to represent the first spin

2)Random number generator 1-2 to represent heads or tails for each toss

3) (this was the fun part) Series of IF statements to either add or subtract from the number,to keep the numbers within 1-6 and lastly to recognize when six has been rolled and record how many times it took

4) average across 40,000 trials

A seperate sample size calculation showed me that roughly 16,000 trials would get me within +- 1% of the answer, with a 99% confidence interval.

From all this, the average I consistently get to the nearest hundreth is 3.5

I'm going to work on trying to get a more detailed description of my excel formulas so anyone can replicate it, since unfortunately it seems like I can't upload an excel file. Any ideas on how to share this info?

Let me know what you think!

That result looks suspect to me, since 3.5 is exactly the average score between 1 and 6. Whereas the OP asks to find average number of steps to produce "6".

I ran a simulation in spreadsheet -- several 1000-experiment runs. They all came up within +- 0.05 of 6.83 found theoretically by EventHorizon. The average between 10 separate trials came within 0.01 of the theoretical 6.83333

For a random coin toss simulation I used a random long binary number parsing it from right to left and regarding 0's as heads and 1's as tails.

[Guest]

Given the symmetry of the problem, all numbers are equally likely to occur in any nth turn. Hence, any calculations done to calculate the average number of rolls to achieve "6" will remain the same calculations to achieve "one", or for that matter for "2,3,4,5" as well. I can not see any logic why a particular number is more likely to occur than any other number. The answer, in such a case without getting into calculations

should be 6

[Guest]

In response to Brucker:

just happenned to stumble on: http://discuss.fogcreek.com/techInterview/...amp;ixPost=1642 - copied here for easy reference: The rule for reciprocating probabillities in order to get the average: If a event has a chance "x" of occuring each time you make a pick, it has " 1-x " chance of not happening. In order to know the average number of picks necessary on average before the event occurs, calculate the following sum: for convenience, let (1-x) = y; x*Sum(1*1+y*2+y^2*3+....y^n*(n+1)+......)= x*Sum(y^n*(n+1),n=0..infinity)=x*(y/(1-y)^2 +1/(1-y))=x*(1/(1-y)^2); but since (1-y)=x...sum=x*1/x^2=1/x--the reciprical.

Given this, for a fair dice where each number has equal chances of occuring - i feel that it should take an average of 6 rolls to get a six.

Edited October 8, 2008 by pam

[Guest]

I agree with EventHorizon's solution,

6⁵/₆

That's the same method and result as I got, and since brute force methods also confirm it I'll confidently declare that the right answer! Very clearly explained too, I thought.

Incidentally, there's another method to verify the result which is maybe a bit simpler than random testing:

If you set up a spreadsheet with 6 columns representing current position of wheel, and quite a few rows (say 100) for turns of the experiment, you can simply fill in a grid of probabilities of the wheel being in that position on that turn. 1st row, all columns=1/6. On subsequent rows, columns 2,3,4 and 6 are the sum of the previous probabilities of the column to either side * 1/2, column 1 = previous column 2 * 1/2, column 5 = previous column 4 * 1/2.

The total in each row decreases by the probability in the previous row's column 6, because if a 6 was obtained it stops there. Sum all the column 6 probabilities multiplied by the turn number and hey presto there's your answer (the more rows you use the more accurate you get)

[Guest]

Actually, on that one point I agree with Bonanova.

If an event occurs on average n times out of T, then you can say that the average number of trials for an event to occur first time is T/n.

The disagreement that I had with Bonanova in another third topic (his "dicey" problem) was about the assertion that if the average number of trials for an event to occur is n, then the probability for an event to occur sometime during the first n trials is 50%.

My disagreement with Bonanova in the average number of trials to roll "6" topic is essentially, that I believe Bonanova's proof to be recursive (circlular). It first assumes what the average is then calculates it based on the same assumption.

Your problem here is more interesting. It is a variation on a random walk problem. I agree with EventHorizon's solution (above), which is economical and precise.

Looking at your comments on Bonanova's reasoning, I see we were attacking it from slightly different angles. In both cases the problem was that it quietly relies on the principle you stated here:

If an event occurs on average n times out of T, then you can say that the average number of trials for an event to occur first time is T/n

In your case, you felt that to be circular reasoning since proving that principle was really the point of the topic.

In my case, I felt it was incorrect reasoning since the principle itself is far from self-evident, and indeed not always true.

My number wheel (running continuously), will produce a 6 on average 1 time out of 6. But at any given time the average number of trials to produce the next 6 is 41/6!

I'd say the reason why that principle fails to hold up in this case is because the current state of the wheel is not independent of its previous state. I can't think of a counterexample where that would not be the case. Nevertheless, it shows that the principle stated is not universal and therefore open to question. In order to show that it holds up in the case of dice rolling (or other random process where each state is created independently), you really need to use the kind of infinite series calculations that Yoruichi-San used.

[Prime]

...

My number wheel (running continuously), will produce a 6 on average 1 time out of 6. But at any given time the average number of trials to produce the next 6 is 41/6!

...

You'd have to define what constitutes a trial. If it is one spin + 1 toss, then "6" comes up on average after 6 trials. If a trial is a toss of a coin, then "6" will not be produced 1 time out of 6, but will depend on where you started.

[Guest]

You'd have to define what constitutes a trial. If it is one spin + 1 toss, then "6" comes up on average after 6 trials. If a trial is a toss of a coin, then "6" will not be produced 1 time out of 6, but will depend on where you started.

The initial spin is not part of the trial process, it just allows us to start the process at a random point. This could be done in other ways. If your computer had a random number generator that worked this way (using some kind of truly random quantum coin-toss), it could sit there quietly working its way back and forth around the wheel at a rate of say, 1000 trials per second.

If at any moment you wanted to perform a test, you hit a key and the computer displays all trials from that moment until it hits a 6 (the fact of entering the process at a random stage does away with the need for a spin). Since you don't know the position of the "wheel" when you start the test, all numbers are equally likely, and the expected frequency of 6's must then be 1 in 6. But the expected number of trials to get the first 6 would be 41/6.

[Guest]

Prime -

You're right that it doesn't seem right. I thought about it more, and realized I made a mistake in my logic and used the same random set of coin tosses for every iteration. I corrected this by making a seperate sheet of corressponding coin tosses for every trial, so it is truly random every step of the way.

My new results are limited by excel and my processing power (I wish I had something better than excel to do this in!) So I could only manage 2000 trials before my system consistently crashed.

My new results consistently hover between ~ 6.7-6.9, so I'm inclined to believe that your result of 6.8333 is correct.

I'm going to work on posting a basic template of my new excel version since some people have asked. Maybe someone can expand it further than I can.

Thanks for input.

That result looks suspect to me, since 3.5 is exactly the average score between 1 and 6. Whereas the OP asks to find average number of steps to produce "6".

I ran a simulation in spreadsheet -- several 1000-experiment runs. They all came up within +- 0.05 of 6.83 found theoretically by EventHorizon. The average between 10 separate trials came within 0.01 of the theoretical 6.83333

For a random coin toss simulation I used a random long binary number parsing it from right to left and regarding 0's as heads and 1's as tails.

[Prime]

The initial spin is not part of the trial process, it just allows us to start the process at a random point. This could be done in other ways. If your computer had a random number generator that worked this way (using some kind of truly random quantum coin-toss), it could sit there quietly working its way back and forth around the wheel at a rate of say, 1000 trials per second.

If at any moment you wanted to perform a test, you hit a key and the computer displays all trials from that moment until it hits a 6 (the fact of entering the process at a random stage does away with the need for a spin). Since you don't know the position of the "wheel" when you start the test, all numbers are equally likely, and the expected frequency of 6's must then be 1 in 6. But the expected number of trials to get the first 6 would be 41/6.

If there was just one initial spin followed by infinite coin tosses, then all numbers would not be equally likely and "6" could occur more or less often than 1 in every 6 numbers, depending on where we started.

Also note that 41/6 average steps was calculated for the scenario where upon reaching "6" we stop. In that sense the experiment was geared toward "6" and all numbers were not equal. The average number of steps to reach "6" in general, not just for the first time would differ from 41/6.

[Guest]

...i feel that it should take an average of 6 rolls to get a six.

Dangit, you're right. What was I thinking of?

[Guest]

If there was just one initial spin followed by infinite coin tosses, then all numbers would not be equally likely and "6" could occur more or less often than 1 in every 6 numbers, depending on where we started.

If you had knowledge of the initial wheel position, you could re-evaluate the expected frequency of 6's (although over a long period of time it would still tend towards 1 in 6). The average trials to reach the first 6 would also be different (but still typically unequal to the inverse of the expected frequency, which, as I've mentioned depends on how many trials you want to do but tends toward 6). But since we don't know the starting position, none of this matters. Under the given circumstances the evaluation of both the expected frequency of 6's and expected trials to reach 6 is just as we've established.

Also note that 41/6 average steps was calculated for the scenario where upon reaching "6" we stop. In that sense the experiment was geared toward "6" and all numbers were not equal.

The experiment is not geared towards 6. Substitute "6" for "2" and see if it makes any difference. There are 6 numbers around the wheel and the wheel favours none of them. The expected trials to the first occurrence of any given number is 41/6.

The average number of steps to reach "6" in general, not just for the first time would differ from 41/6.

We are calculating the expected trials to its first occurrence. That's the question, and that's what this statement refers to:

If an event occurs on average n times out of T, then you can say that the average number of trials for an event to occur first time is T/n

What happens after that is irrelevant.

[Guest]

41 should be the sum of the individual average trials to reach 6 from each number using the coin toss method. Dividing it by 6 will give you the average of the the six averages, which is our 41/6.

Overall there is a set of 4 unique average trials for 6 numbers:

1 and 5 have the same average trials (the lowest) to reach 6

2 and 4 are the next highest

3 is the highest average

6 is a unique average

If you started looking for, say 3 instead of 6, it would just shift this set of average trials:

2 and 4 are the lowest

1 and 5 are the next highest;

6 is the highest average

3 is a unique average

The values of the averages would remain the same, since for any given number it's defined by the proximity (potential number of tosses) of that number to the number it is trying to become.

If you had knowledge of the initial wheel position, you could re-evaluate the expected frequency of 6's (although over a long period of time it would still tend towards 1 in 6). The average trials to reach the first 6 would also be different (but still typically unequal to the inverse of the expected frequency, which, as I've mentioned depends on how many trials you want to do but tends toward 6). But since we don't know the starting position, none of this matters. Under the given circumstances the evaluation of both the expected frequency of 6's and expected trials to reach 6 is just as we've established.

The experiment is not geared towards 6. Substitute "6" for "2" and see if it makes any difference. There are 6 numbers around the wheel and the wheel favours none of them. The expected trials to the first occurrence of any given number is 41/6.

We are calculating the expected trials to its first occurrence. That's the question, and that's what this statement refers to:

If an event occurs on average n times out of T, then you can say that the average number of trials for an event to occur first time is T/n

What happens after that is irrelevant.

[bonanova]

I'm late to the game, but I had a free evening last night so I simulated the problem.

All the results were near integers which suggested a direct calculation was in the works.

Reading back through the thread I found EventHorizon did the calculation.

Very nicely, btw, no infinite sums.

FWIW, 3000000 trials each, with the desired number 0 1 2 3 4 or 5 steps away,

gave average number of coin tosses as:

0 - 5.99899 / min = 2, max = 90

1 - 5.00305 / min = 1, max = 97

2 - 7.99791 / min = 2, max = 86

3 - 9.00089 / min = 3, max = 99

4 - 8.00015 / min = 2, max = 100

5 - 5.00985 / min = 1, max = 99

These sum to 41.0108 or average of 6.83514 coin tosses

to reach a desired number after an initial randomizing spin.

Differs by 0.0018 spins from 41/6.