wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Exploratoreum Exhibit
        
(Message started by: 1337b4k4 on Jul 23^rd, 2008, 4:03pm)

Title: Exploratoreum Exhibit
Post by 1337b4k4 on Jul 23^rd, 2008, 4:03pm

A friend of mine told me about an exhibit at the Exploratoreum in SF that he saw recently, and I became curious about the math behind it.

There are 63 wheel-like things in a row, each with the numbers from 1-9 printed on it in. You spin all the wheels to randomize the numbers. You pick a number from 1-9, and go to that index among the array of wheels (say you go to wheel #7). Then, after observing the number on that wheel (say 5), you then look at wheel number (5 + 7 = 12), and repeat the process (if wheel #12 has a 4 on it, you now go to wheel #16, etc.), until you run out of wheels once the index becomes larger than 63. You make a note of this index that you would have landed on.

The Exploratoreum sign says: if two people choose two random starting points from 1-9, then with high probability both of them will end up at the same place after performing this experiment.

I thought about this and I thought the probability behind it was pretty neat, so I thought I'd share.

Some questions that I've thought of and have been able to answer about this experiment:

Why does this happen?

Will all 9 possible starting points usually get to the same number in the end?

What is a good way to simulate this experiment on a computer, for general k and runways (in the above example what I call the runway is 63) as long as you need them to be? (You would need to be able to do many trails quickly to get good approximate means, since the variance is pretty high)

What is the expected runway needed until all 9 possible starting points converge to the same number? What about for general wheels with k numbers per wheel? - note: my expected runway calculation uses some slightly shady heuristics, but my final answer is pretty close to the simulated value for k>7 or so, and the percent error gets better for larger k, which was better than I'd hoped.

Some questions I have not been able to answer due to lack of time, intuition, and/or excess complexity:

What is the probability that for a given wheel-number k and runway n that all k starting points converge by n?

What is the variance of the runway needed to see convergence? This got too complicated for me to figure out by hand without laziness kicking in, but the simulation I ran told me that the runway n=63 for the case k=9 was about two standard deviations above the mean runway needed for all 9 starting positions to converge, which is why the exploratoreum exhibit usually works.

I'd like to know other people's answers to some of these questions to see what other cool methods of analysis and simulation you guys can think of.

This model seems like a rich source of questions so if you guys think of any cool problems, please share :)

Title: Re: Exploratoreum Exhibit
Post by Eigenray on Jul 23^rd, 2008, 6:26pm

The probability can be computed in O(n*k^k) time. So it's linear in n, at least, but for k=9 the memory requirements make it impractical, at least with this algorithm:

Let's reverse the wheels, so that we end up at a wheel with number http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif k. For each sequence A=(a₁,...,a_k), 1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif a_i http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif k, let N_n(A) be the number of ways to arrange wheels 1 through n so that a_i is the wheel we end up with if we start at wheel n-k+i.

First compute N_k(A) for each A. Then
N_n+1(A) = N_n(a_k,a₁,...,a_k-1) + C*http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_x=1^k N_n(x,a₁,...,a_k-1),
where C is the number of i < k such that a_i=a_k.

The probability that the last k wheels all lead to the same wheel is then
p(k,n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_x=1^k N_n(x,x,...,x)/kⁿ.

We can easily show p(2,n) = 1 - 1/2^n-1. For k=3, we have
3ⁿ(1 - p(3,n)) = { 21, 51, 111, 237, 513, 1095, 2331, 4977, 10605, 22587, ... }.

For any fixed k, N_n is given by a linear recurrence, so can be computed by taking the n-th power of the k^k x k^k transition matrix. So it can actually be found in O(log n) matrix multiplications.

But it's easy to see that 1-p(k,n) converges exponentially to 0, for k fixed. The first person must take at least n/k steps to get to the end, and the probability that another person misses all of these is < (1 - 1/k)^n/k.

Anyone have a better algorithm for finding p(k,n)?