wu :: forums - Print Page


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

        riddles >> easy >> The robot and the coins
        
(Message started by: BNC on Oct 21^st, 2003, 9:17am)

Title: The robot and the coins
Post by BNC on Oct 21^st, 2003, 9:17am

In a room there are many coins on the floor (assume a very large number). They display either "heads" or "tails" randomally.

A robot enters the room. It walks around randomaly, and is programed as follows:
- If it sees a coin diplaying "heads" it will turn it over to display "tails".
- If it sees a coin displaying "tails", it will flip the coin (all coins are fair).

After a long enough time, will the ratio of heads to tails converge? If no, why? And if yes, to what value?

Title: Re: The robot and the coins
Post by aero_guy on Oct 21^st, 2003, 9:36am

If we take an simplified version of the riddle and say there are C coins with t₀=.5*C where t is the number of tails and the subscript is a pass through all of the coins. Lets make this simplified version say that the robot goes through all coins once and then repeats himself.
[hide]
thus, t_n=C-t_n-1+.5*t_n-1

or

t_n=C-.5*t_n-1
[/hide]
Now to check to see the convergence of series.. man has that been a long time.

Title: Re: The robot and the coins
Post by James Fingas on Oct 21^st, 2003, 9:43am

Sounds like the robot will just get stuck on the first coin it finds ...

"A head, eh? Better turn 'er over ... okay, now it's a tail. Time to flip it ... still a tail; flip it again ..."

Title: Re: The robot and the coins
Post by towr on Oct 21^st, 2003, 9:46am

Well, it will converge.. But I don't know whereto.. something like 0.5 +-0.1

on 10/21/03 at 09:43:42, James Fingas wrote:

"A head, eh?

A canadian robot ? ;)

Title: Re: The robot and the coins
Post by aero_guy on Oct 21^st, 2003, 9:48am

With the idea of passing over all coins in series I finally figured out how to find the limit... and of course feel stupid I forgot how.

So, the series method converges to [hide]2/3 tails[/hide]. I am not sure how confiident we can be that this expands to the general solution.

Title: Re: The robot and the coins
Post by THUDandBLUNDER on Oct 21^st, 2003, 10:15am

on 10/21/03 at 09:43:42, James Fingas wrote:

"A head, eh? Better turn 'er over ... okay, now it's a tail. Time to flip it ... still a tail; flip it again ..."

Yeah right, assuming multiple operations on the same coin. However, the other interpretation is more interesting and must surely be the intended one. That is, we move from coin to coin.
:[hide]
We can model it as a differential equation:

Let the initial number of heads in the room be H
Let the initial number of tails in the room be T

Then
dH/dt = (T/2)/(T+H)
dT/dt = (T/2 + H)/(T+H)

Giving dT/dH = 2(H/T) + 1

I can't remember offhand how to solve this. :-[ Integrating factor perhaps?
Or am I using a sledgehammer to crack a nut?
[/hide]

on 10/21/03 at 09:46:41, towr wrote:

A canadian robot ? ;)

Title: Re: The robot and the coins
Post by towr on Oct 21^st, 2003, 10:16am

::[hide]If the series converges, then both processes that cause change will have to be in equilibrium, so
p_h (chance of loosing a head) must equal (1-p_h)/2 (chance of gaining a head)
so p_h = 1/3, and the ratio p_h/p_t =1/2
[/hide]::

Title: Re: The robot and the coins
Post by THUDandBLUNDER on Oct 21^st, 2003, 10:28am

Quote:

If the series converges,

All you have to do now is prove that it does converge. ;)

Title: Re: The robot and the coins
Post by towr on Oct 21^st, 2003, 10:58am

That's easy enough to show, since there are two processes that work against each other, and they get stronger as the result of the other grows..

More notably, for p_h < 1/3 the probability we gain a head (and loose a tail) is greater than the reverse
and for p_h > 1/3 vice versa.

Or you could just run a simulation and see that it converges :P

Title: Re: The robot and the coins
Post by aero_guy on Oct 21^st, 2003, 11:21am

Excellent, then the series method is indicitave of the larger problem. I guess it would be the discritized version.

It actually converges pretty quickly too.

Title: Re: The robot and the coins
Post by TimMann on Oct 23^rd, 2003, 10:37pm

I did this one by looking at the flipping of each coin as a Markov process, with transition matrix:

1/2 1
1/2 0

We then want the steady-state vector. The answer will be an eigenvector of this matrix with eigenvalue 1, normalized to have components summing to 1, i.e.:

1/3 //heads
2/3 //tails

The coins don't interact with each other at all, so the probability of any coin being a head in the long run is the same as the expected proportion of heads among all the coins. The number of coins doesn't matter.