Robot Flipping Coins

[dibsy]

someone walks into your room and dumps a huge bag of quarters all over the floor. they spread them out so no quarters are on top of any other quarters. a robot then comes into the room and is programmed such that if it sees a head, it flips it to tails. if it sees a tail, it throws it in the air. the robot moves around randomly forever. will there be a convergence in distribution of heads vs. tails?

[bigpooch]

Yes. If p=probability("tail in the limit as the number of
flips approaches infinity"), p=(1-p)+p(1/2) or p=1-(p/2), so
p=2/3.

[imfatandugly]

[ QUOTE ]
someone walks into your room and dumps a huge bag of quarters all over the floor. they spread them out so no quarters are on top of any other quarters. a robot then comes into the room and is programmed such that if it sees a head, it flips it to tails. if it sees a tail, it throws it in the air. the robot moves around randomly forever. will there be a convergence in distribution of heads vs. tails?

[/ QUOTE ]
I would say with probability 1 there will be all heads in the room if the robot does this forever and there is a finite amount of coins.
I dont see how this could not be the case.
If there are infinately many coins.......

[neverforgetlol]

law of large numbers?

[dibsy]

That was what I came up with, but apparently it's not the right solution..

[BruceZ]

[ QUOTE ]
someone walks into your room and dumps a huge bag of quarters all over the floor. they spread them out so no quarters are on top of any other quarters. a robot then comes into the room and is programmed such that if it sees a head, it flips it to tails. if it sees a tail, it throws it in the air. the robot moves around randomly forever. will there be a convergence in distribution of heads vs. tails?

[/ QUOTE ]

Let h[n] denote the average fraction of heads after the nth flip, and t[n] denote the average fraction of tails after the nth flip, so that

h[n] + t[n] = 1.

Then note that all of the heads after the nth flip come from the tails remaining after flip n-1, so we have

h[n] = 0.5*t[n-1].

Combining these equations gives

h[n] = 0.5 - 0.5*h[n-1].

Setting h[n] = h[n-1] shows that if this converges, it must converge to h[n] = 1/3 and t[n] = 2/3.

To verify this, you can use Excel. Set A1 to the starting fraction of heads, and set B1 to the starting fraction of tails 1 - A1. Then set A2 = 0.5*B1, and B2 = 1 - A2. Copy these 2 formulas down the column, and you will see that for any starting fractions, column A converges to 1/3, and column B converges to 2/3. Note that we can also write the formula for tails explicitly as t[n] = h[n-1] + 0.5*t[n-1], or B2 = A1 + 0.5*B1.

[BruceZ]

[ QUOTE ]
That was what I came up with, but apparently it's not the right solution..

[/ QUOTE ]

There is an alternate "trick" solution depending on your reading of the problem. When the robot changes a head to a tail, if it then "sees" the resulting tail, it will flip that coin randomly. So it flips both heads AND tails randomly, so this results in an answer of an equal number of heads and tails. Note that this interpretation requires that the robot looks at the coin after changing it from heads to tails, but does not look at the coin after flipping it randomly, since otherwise it would only ever process a single coin.

[imfatandugly]

[ QUOTE ]
[ QUOTE ]
someone walks into your room and dumps a huge bag of quarters all over the floor. they spread them out so no quarters are on top of any other quarters. a robot then comes into the room and is programmed such that if it sees a head, it flips it to tails. if it sees a tail, it throws it in the air. the robot moves around randomly forever. will there be a convergence in distribution of heads vs. tails?

[/ QUOTE ]


I would say with probability 1 there will be all heads in the room if the robot does this forever and there is a finite amount of coins.
I dont see how this could not be the case.
If there are infinately many coins.......

[/ QUOTE ]

I misread the problem, thought that robot leaves heads alone if it picks it up and flips if he picks up tails. Anyways thought about it a bunch and came up with a very rigorous solution.


I have a thorough proof, that also say what h(n) is given h(0)=a, that is (# of heads on the floor starting off )/( # of coins ) =a

Let h(n)= # of heads / # of coins after n tosses.
t(n)= # of tails / # of coins after n tosses.

Also Let h(0)=a.

Now as noted t(n+1)= h(n) + (1-h(n))/2= (1+h(n) )/2
h(n) = ( 1- h(n) ) /2

notice since 0<h(n),t(n)<1 then 0<h(n+1),t(n+1)<1.

Now lets compute h(n), given h(0)=a.
h(1)= (1-a)/2
h(2)= (3+a)/4
h(3)= (5-a)/8
h(4)= (8+a)/16

we prove by induction that h(n)= 1-1/2+1/4+- 1/2^n + (-1)^n a/2^n=
2/3(1-(1/2)^(n+1) ) + (-1)^n a/2^n

for n=1 this is clear.
h(1)=1/2-a/2=(1-a)/2


suppose this is true for k=1,...,n
h(n+1)=(1-h(n))/2=(1-2/3(1-(1/2)^(n+1) ) + (-1)^n a/2^n)/2=
2/3(1-(1/2)^(n+2) ) + (-1)^n a/2^(n+1)

Using Ihop or whatever the hell that guys name is for limits we see that if h(0)=a then Lim n->infinity h(n) = 2/3.