wu :: forums - Print Page


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

        riddles >> medium >> Robot & Coins II
        
(Message started by: James Fingas on Oct 21^st, 2003, 12:08pm)

Title: Robot & Coins II
Post by James Fingas on Oct 21^st, 2003, 12:08pm

Inspired by BNC's Robot and Coins (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1066753050) 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?

Title: Re: Robot & Coins II
Post by towr on Oct 21^st, 2003, 2:29pm

::[hide]I tried a simulation, p_h goes to roughly 0.24 +- 0.1[/hide]::
But of course that doesn't tell me why..

Title: Re: Robot & Coins II
Post by towr on Oct 21^st, 2003, 2:51pm

::[hide]I tried the same method I used for the other problem, ending up with the equation:
5(1 - p_h)p_h⁴ + 5(1 - p_h)⁵ = 30(1 - p_h)²p_h³ + 20(1 - p_h)³p_h² + 5(1 - p_h)⁴p_h

solving the equation numerically, there are three possibly stable points, p_h ~= 0.8688, p_h ~= 0.25125 and p_h = 1, but looking at the graphs (lhs and rhs of the equation) only the second one can be stable.. [/hide]::

Title: Re: Robot & Coins II
Post by aero_guy on Oct 21^st, 2003, 3:01pm

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.

Title: Re: Robot & Coins II
Post by aero_guy on Oct 21^st, 2003, 3:02pm

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.

Title: Re: Robot & Coins II
Post by towr on Oct 21^st, 2003, 3:12pm

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

Title: Re: Robot & Coins II
Post by Barukh on Oct 23^rd, 2003, 2:44am

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? ::)

Title: Re: Robot & Coins II
Post by towr on Oct 23^rd, 2003, 3:30am

I think that goes without saying..
Unless James wanted to be evil..

Title: Re: Robot & Coins II
Post by James Fingas on Oct 23^rd, 2003, 9:36am

on 10/21/03 at 15:12:09, 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.

Title: Re: Robot & Coins II
Post by aero_guy on Oct 23^rd, 2003, 12:12pm

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?

Title: Re: Robot & Coins II
Post by towr on Oct 23^rd, 2003, 1:06pm

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..

Title: Re: Robot & Coins II
Post by TimMann on Oct 23^rd, 2003, 10:57pm

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.

Title: Re: Robot & Coins II
Post by aero_guy on Oct 23^rd, 2003, 11:17pm

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).

Title: Re: Robot & Coins II
Post by towr on Oct 23^rd, 2003, 11:45pm

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..

Title: Re: Robot & Coins II
Post by aero_guy on Oct 24^th, 2003, 4:11am

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.

Title: Re: Robot & Coins II
Post by Barukh on Oct 24^th, 2003, 7:24am

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)ⁱC₄ / ⁿC_i.

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).

Title: Re: Robot & Coins II
Post by TimMann on Oct 24^th, 2003, 8:53pm

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.

Title: Re: Robot & Coins II
Post by Barukh on Oct 25^th, 2003, 8:06am

TimMannn, thanks for the reference. Seems to have many interesting topics in it. :D