Author |
Topic: Exploratoreum Exhibit (Read 958 times) |
|
teekyman
Full Member
Gender: 
Posts: 199
|
 |
Exploratoreum Exhibit
« on: Jul 23rd, 2008, 4:03pm » |
 Quote  Modify
|
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 
|
|
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Exploratoreum Exhibit
« Reply #1 on: Jul 23rd, 2008, 6:26pm » |
Quote Modify
|
The probability can be computed in O(n*kk) 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  k. For each sequence A=(a1,...,ak), 1 ai k, let Nn(A) be the number of ways to arrange wheels 1 through n so that ai is the wheel we end up with if we start at wheel n-k+i.
First compute Nk(A) for each A. Then
Nn+1(A) = Nn(ak,a1,...,ak-1) + C* x=1k Nn(x,a1,...,ak-1),
where C is the number of i < k such that ai=ak.
The probability that the last k wheels all lead to the same wheel is then
p(k,n) = x=1k Nn(x,x,...,x)/kn.
We can easily show p(2,n) = 1 - 1/2n-1. For k=3, we have
3n(1 - p(3,n)) = { 21, 51, 111, 237, 513, 1095, 2331, 4977, 10605, 22587, ... }.
For any fixed k, Nn is given by a linear recurrence, so can be computed by taking the n-th power of the kk x kk 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)?
|
| « Last Edit: Jul 23rd, 2008, 6:31pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print