Author |
Topic: Robot & Coins II (Read 1337 times) |
|
James Fingas
Uberpuzzler
Gender: 
Posts: 949
|
 |
Robot & Coins II
« on: Oct 21st, 2003, 12:08pm » |
 Quote  Modify
|
Inspired by BNC's Robot and Coins riddle, here is another riddle of the same sort:
An automaton (likely of Canadian manufacture) enters a chamber, upon the floor of which lie a vast number of bi-stable currency devices. Each currency device initially rests in a condition taken randomly from the set {heads, tails}. The automaton then begins to follow its programming. It picks up five randomly-chosen currency devices from the chamber floor and performs one of the following actions, conditioned upon the state of the devices it has picked up:
1) If all five were in the "tails" condition, they are all inverted so as to be in the "heads" condition.
2) If at least four were in the "heads" condition, the currency devices in the "tails" position are inverted. The devices are now all in the "heads" condition.
3) Otherwise, all five currency devices are placed in the "tails" position.
After this operation, the five currency devices are placed on the chamber floor.
Does the ratio of tails to heads converge? If so, what does it converge to?
|
| « Last Edit: Oct 21st, 2003, 12:09pm by James Fingas » |
 IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Robot & Coins II
« Reply #1 on: Oct 21st, 2003, 2:29pm » |
Quote Modify
|
::I tried a simulation, ph goes to roughly 0.24 +- 0.1::
But of course that doesn't tell me why..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Robot & Coins II
« Reply #2 on: Oct 21st, 2003, 2:51pm » |
Quote Modify
|
::I tried the same method I used for the other problem, ending up with the equation:
5(1 - ph)ph4 + 5(1 - ph)5 = 30(1 - ph)2ph3 + 20(1 - ph)3ph2 + 5(1 - ph)4ph
solving the equation numerically, there are three possibly stable points, ph ~= 0.8688, ph ~= 0.25125 and ph = 1, but looking at the graphs (lhs and rhs of the equation) only the second one can be stable.. ::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Robot & Coins II
« Reply #3 on: Oct 21st, 2003, 3:01pm » |
Quote Modify
|
Your third is stable as well, in fact if you reached that date you would never flip another coin. It will also converge to that value if ph is sufficiently large.
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Robot & Coins II
« Reply #4 on: Oct 21st, 2003, 3:02pm » |
Quote Modify
|
It also seems that you made the assumption that the number of coins was large enough that that the act of picking four from the set did not change the probabilities on the fifth.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Robot & Coins II
« Reply #5 on: Oct 21st, 2003, 3:12pm » |
Quote Modify
|
Euhm, well, yes.. apparantly the last one is stable..
it's just not as good an attractoras the second one.
As for the assumption of a large number of 'coins', it is stated that there are a vast number of them in the problem statement.. So it's not really an assumption
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Robot & Coins II
« Reply #6 on: Oct 23rd, 2003, 2:44am » |
Quote Modify
|
It seems the question should include "converge with probability 1?", since there will always be sequences of actions when the ratio never converges.
Does it make sense? 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Robot & Coins II
« Reply #7 on: Oct 23rd, 2003, 3:30am » |
Quote Modify
|
I think that goes without saying..
Unless James wanted to be evil..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Robot & Coins II
« Reply #8 on: Oct 23rd, 2003, 9:36am » |
Quote Modify
|
on Oct 21st, 2003, 3:12pm, towr wrote:As for the assumption of a large number of 'coins', it is stated that there are a vast number of them in the problem statement.. So it's not really an assumption
|
|
The number of coins is important in this question. And not just because removing coins can change the probabilities of heads or tails. Try a simulation with a small number of coins to see.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Robot & Coins II
« Reply #9 on: Oct 23rd, 2003, 12:12pm » |
Quote Modify
|
Analyzing the problem with small numbers of coins we see that for 5 coins it will go to all heads in 2 iterations. With six we see that it will take a little bit longer, but will eventually reach all heads as well.
This gets me thinking. There is a finite probability that for no matter what the number of coins they will reach an all heads state. No matter what the condition of the coins it never becomes impossible to reach this state. Once it reaches this state it will never change again. Thus, considering an infinite amount of iterations the coins will achieve all states that have a probability greaer than 0, and thus will eventually fall into the all heads state.
Does this make sense?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Robot & Coins II
« Reply #10 on: Oct 23rd, 2003, 1:06pm » |
Quote Modify
|
I don't think so..
Despite there being a finite chance of it, it goes down so quickly I don't think it will accumulate to probability one..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Robot & Coins II
« Reply #11 on: Oct 23rd, 2003, 10:57pm » |
Quote Modify
|
Hmm. I tried modeling this one as a Markov process too, but didn't see a way to do that without making an overly strong assumption. If we had a number of sets of 5 coins and the robot never mixed coins between sets, we'd have a Markov process with transition matrix:
0 1 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
1 0 0 0 1 1
The only steady state vector for this process is the all-heads state.
However, I don't have any confidence that this solution is correct for the real problem, where the robot is free to choose any five coins.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Robot & Coins II
« Reply #12 on: Oct 23rd, 2003, 11:17pm » |
Quote Modify
|
towr, now we are getting into how infinities affect probability, an area I admit I know little of.
Consider, though, the state we had determined to be the stable state. From here there is a finite, if extremely small, chance that it will migrate to all heads. Any time it does anything else it will eventually reach this stable state again. Thus if we allow the process to continue indefinitely, the probability that it ever reaches the all heads state should reach 1. It doesn't matter how low the initial probability is, the infinite number of iterations takes care of it. I suppose one could calculate the number of iterations before the likelihood of it reaching this state approaches any given probability... but I'm not going to.
Thus, the 2nd root you came up with is only a temporary state. Also, it seems to me that your first root is an unstable equilibrium point. In other words, it is the proportion of coins where there is equal likelihood that it will migrate to either of the other roots. I didn't do the math, but it seems likely (there would have to be such a point in between the other two stable states).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Robot & Coins II
« Reply #13 on: Oct 23rd, 2003, 11:45pm » |
Quote Modify
|
The second point is one where a state get's pushed to by a tail-tendancy when it's on the heady side, and by a head-tendancy when it's on the taily side.. which I thought was pretty stable..
As n get's larger it get's increasingly unlikely it can still go to the all head state.. But you're right that for a fixed n it's allways a positive finite chance.. I find it hard to accept, but I guess that really is the only real stable state.. I wouldn't want to wait till it get's there though..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Robot & Coins II
« Reply #14 on: Oct 24th, 2003, 4:11am » |
Quote Modify
|
The second state you describe is actually just like the answer to the first robot coin riddle. It is likely to hold in that position by probability, though it could very well swing to one extreme or the other for a bit. In this case there is just the added difficulty that if it swings far enough it might never come back.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Robot & Coins II
« Reply #15 on: Oct 24th, 2003, 7:24am » |
Quote Modify
|
Let me try to introduce some numbers. At any time of the process, the state of the coins on the floor will be described by the integer 0 [le] i [le] n, according to the number of “heads”. It is clear that the only stable state is n, and so if the process converges, it converges to this state.
Denote by p(i) the probability to go from the state i to state i+1 by a single action. p(i) is positive for every i [ge] 4; in fact, it’s the probability to pick 4 heads out of 5, that is, (n-i)iC4 / nCi.
Now, let P(i) to be the probability to go from state i to state n eventually. It is easy to see that P(i) >= p(i)p(i+1)…p(n-1).
As for i < 4, in the same way, the probability to go from state i to state i-1 is positive, and so is the probability to eventually arrive at state 0. But P(0) = P(5).
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Robot & Coins II
« Reply #16 on: Oct 24th, 2003, 8:53pm » |
Quote Modify
|
The full problem is a Markov chain, just a more complex one than my 6x6 transition matrix reflects. With N coins, there are N+1 distinct states, ranging from 0-heads to N-heads. From any given state, the probability of reaching any other given state on the next step is well-defined and depends only on the two states, not on any other history. So we could (with sufficient patience) write out the (N+1) x (N+1) transition matrix of this chain.
Without actually writing out the matrix, we still can see that the N-heads state is an absorbing state (i.e., once you get into that state, you can't get out), that it's possible to eventually get from any of the non-absorbing states to this state, and that there are no other absorbing states. A Markov chain in which it's possible to eventually get from any state to an absorbing state is called an absorbing Markov chain. It's known that any absorbing Markov chain has probability 1 of eventually reaching an absorbing state. For a reference, see Theorem 11.3 (p. 417) in http://books.pdox.net/Math/Intro%20to%20Probability/chapters1-12.pdf. The proof of this theorem is essentially just a more rigorous and general version of the arguments that aero_guy and Barukh advanced in this thread.
So the answer to the puzzle definitely is that the ratio of tails to heads converges to 0.
--
Edit: corrected an error in stating the theorem -- I forgot to say that it has to be possible to get from any state to an absorbing state.
|
| « Last Edit: Oct 25th, 2003, 11:32am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Robot & Coins II
« Reply #17 on: Oct 25th, 2003, 8:06am » |
Quote Modify
|
TimMannn, thanks for the reference. Seems to have many interesting topics in it. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print