Boxes with disks.

Fruityloop · 2016-01-23 16:26:22

You have two boxes. We will call them box #1 and box #2. Box #1 has 20 wooden disks inside that are numbered 1 to 20. Box #2 is empty.
You have a 20 sided die. You roll the die and whichever number comes up on the die, the disk with that number gets moved to the other box.
So, if it is in box #1 it gets moved to box #2, if it is in box #2 it gets moved to box #1.
Starting with all 20 disks in box #1, on average how many rolls are required for box #2 to contain all of the disks and box #1 is empty?

Last edited by Fruityloop (2016-01-23 16:32:17)

phrontister · 2016-01-24 03:10:58

Hi Fruityloop,

Here are the results from an Excel simulation for 200,000 rolls of the 20-sided die:

                      # of rolls after which Box2 held exactly  
# of disks in Box2    the # of disks listed in the first column
                0         0
                1         3
                2        35
                3       252
                4       951
                5      2951
                6      7355
                7     14735
                8     24017
                9     31966
               10     35327
               11     32247
               12     24076
               13     14674
               14      7220
               15      2919
               16       977
               17       245
               18        43
               19         5
               20         2
                     ------
       Total throws: 200000
                     ======

So, in 200,000 rolls, there were 2 occasions when Box2 contained all of the disks and Box1 was empty.

Unfortunately, I didn't think to code the program to note the rolls at which Box2 was full, but I do know that both occurred during the 70,000 rolls between 130,000 and 200,000.

EDIT: I ran another simulation for 1,000,000 rolls, resulting in similar ratios as before, but this time there was 1 occasion when Box2 was full and 1 when it was empty (not being the empty starting position).

Last edited by phrontister (2016-01-24 11:29:47)

Fruityloop · 2016-01-24 12:09:23

That's interesting. I hope I have the correct answer. I will wait for some more people to attempt to answer the problem.

phrontister · 2016-01-25 03:32:00

Some more results, this time in Mathematica:

10,000,000 rolls: 6 occasions when Box2 was full and Box1 empty.
100,000,000 rolls: 117 occasions when Box2 was full and Box1 empty.
1,000,000,000 rolls: 965 occasions when Box2 was full and Box1 empty.

This is the full results list for 1 billion rolls:

                      # of rolls after which Box2 held exactly  
# of disks in Box2    the # of disks listed in the first column
                0            960
                1          19184
                2         180955
                3        1087879
                4        4623556
                5       14795300
                6       36979285
                7       73946508
                8      120155510
                9      160186747
               10      176186717
               11      160170444
               12      120119252
               13       73905084
               14       36949683
               15       14783309
               16        4622139
               17        1086434
               18         180978
               19          19111
               20            965
                   -------------
      Total rolls: 1,000,000,000
                   =============

Edit 14 June 2016: I ran another sim for 1 billion rolls today, yielding 989 occasions when Box2 was full and Box1 empty.

Last edited by phrontister (2016-06-14 00:23:26)

Relentless · 2016-01-25 04:16:43

So we can conjecture that the number of rolls required is 1,000,000? Despite your 2 results in Excel.

It will be interesting to see a proof (unfortunately, I think it is beyond me).

phrontister · 2016-01-25 05:22:26

Likewise me!

bobbym · 2016-01-26 12:32:42

Hi Fruityloop;

Fruityloop · 2016-01-26 16:25:14

Hi Bobbym,
I have the same answer as you but I used a 20 x 20 Markov chain. The way you got the answer involves some math that is way beyond me.
I'm glad I got the right answer.

bobbym · 2016-01-26 17:53:37

I used the same idea.

phrontister · 2016-01-26 17:57:59

So that's a difference of about 6.76% from my last M simulation.

Maybe I should have let M keep rolling the die till now, and I might have got closer to the right answer!

bobbym · 2016-01-26 18:00:03

There was a very quick way using M.

phrontister · 2016-01-26 18:05:33

My code for 1 billion rolls took M 4.75 hours. I know a maths way is quicker than a sim, but I couldn't think of one...and I've never heard of a Markov chain.

What's the quick M way?

bobbym · 2016-01-26 19:00:33

Hi;

n = 20;
A = DiagonalMatrix[Table[k/n, {k, 1, n}], -1] + 
   DiagonalMatrix[Table[k/n, {k, n, 1, -1}], 1];
A[[1, 1]] = 1;
A[[1, 2]] = 0;
A[[n + 1, n]] = 1;
(*A//MatrixForm*)
v = ConstantArray[0, n + 1];
v[[n + 1]] = 1;
A = DiscreteMarkovProcess[v, A];
Mean[FirstPassageTimeDistribution[A, 1]]

phrontister · 2016-01-26 19:21:03

Wow - hardly gave me time to blink!! I don't understand it, of course. Waaay over my head!

Oh, well...coding up a working sim was satisfying enough for me. It didn't take me long to sack Excel and let M take over.

M rolled the die at about 58000rps compared to Excel's 4000rpm, but Excel had to wade through updating spreadsheet cells, whereas M just counted under the table.

bobbym · 2016-01-26 19:23:50

If you want and feel you are ready I will teach you Absorbing Markov chains. You will absorb them easily ( no pun intended.) But not tonight, I am sleepy.

phrontister · 2016-01-26 19:32:15

Thanks for the offer, but I think I'll pass...for a while at least.

I have so many unfinished projects at home that I should be doing at a quicker rate than I have. As is the case with many owner-built houses - which mine is - I've left a lot of jobs till later. And now it's later!

bobbym · 2016-01-27 04:30:41

Hi;

Okay, when you are ready. I just moved, so I have much maintenance to do.

javanaut · 2016-02-09 11:21:52

Thanks. I looked up the "absorbing" Markov chains. It turns out that it does not matter how many absorbing states there are. The answer only depends on the fundamental matrix Q.
Fascinating that matrices (n-by-n ones anyway) obey the rules of algebra, like:

I - Q (to the n+1)
I + Q + Q² + Q³ + ... + Q (to the n) = -------------------------
I - Q

Is that correct?

bobbym · 2016-02-09 13:56:54

Hi;

Remember that Matrix division is undefined and they use the inverse instead. As such I know of the formula

thickhead · 2016-06-13 17:34:53

Very interesting problem.Let us consider the fate of only one disk. on 1st roll its possibility of going to box 2 is 19/20 and that of remaining in box 1 is 19/20. On 2nd roll if we get same number it is shifted back to box1. so the probability of remaining in box 2 is 1/20x19/20 and that of remaing in box1 is 19/20 (of first roll)x 1/20 (of second roll.) This way we can continue in excel sheet for further rolls.

Roll	box1         	box2
1	0.95          	0.05
2	0.905	        0.095
3	0.8645	        0.1355
4	0.82805	        0.17195
5	0.795245        0.204755
6	0.7657205	0.2342795
7	0.73914845	0.26085155
8	0.715233605	0.284766395
9	0.693710245	0.306289756
10	0.67433922	0.32566078
. 
.
.
61	0.500808655	0.499191345
62	0.500727789	0.499272211
63	0.50065501	0.49934499
64	0.500589509	0.499410491
65	0.500530558	0.499469442

This compelled me to accept the long term probability of disk being in box2 as 0.5.
Now for 20 disks to be in box2

So we can expect all 20 disks to be in box 2 by 1/0.5^20=2^20=

Last edited by thickhead (2016-06-13 19:57:10)

thickhead · 2016-06-13 21:59:54

Last edited by thickhead (2016-06-15 01:47:24)

Math Is Fun Forum

#1 2016-01-23 16:26:22

Boxes with disks.

#2 2016-01-24 03:10:58

Re: Boxes with disks.

#3 2016-01-24 12:09:23

Re: Boxes with disks.

#4 2016-01-25 03:32:00

Re: Boxes with disks.

#5 2016-01-25 04:16:43

Re: Boxes with disks.

#6 2016-01-25 05:22:26

Re: Boxes with disks.

#7 2016-01-26 12:32:42

Re: Boxes with disks.

#8 2016-01-26 16:25:14

Re: Boxes with disks.

#9 2016-01-26 17:53:37

Re: Boxes with disks.

#10 2016-01-26 17:57:59

Re: Boxes with disks.

#11 2016-01-26 18:00:03

Re: Boxes with disks.

#12 2016-01-26 18:05:33

Re: Boxes with disks.

#13 2016-01-26 19:00:33

Re: Boxes with disks.

#14 2016-01-26 19:21:03

Re: Boxes with disks.

#15 2016-01-26 19:23:50

Re: Boxes with disks.

#16 2016-01-26 19:32:15

Re: Boxes with disks.

#17 2016-01-27 04:30:41

Re: Boxes with disks.

#18 2016-02-09 11:21:52

Re: Boxes with disks.

#19 2016-02-09 13:56:54

Re: Boxes with disks.

#20 2016-06-13 17:34:53

Re: Boxes with disks.

#21 2016-06-13 21:59:54

Re: Boxes with disks.

Board footer