Consider a coin that lands on heads with probability p ∈ [0,1]. How many times on average do you have to flip the coin before it lands on heads?
Naively, one expects the answer to be 1/p (if the coin has 1/3 chance of landing on heads, you expect to need to flip it 3 times). Of course, there is a small chance that you will need 4 flips, or 5 flips, or a billion flips. There is some sort of concern that the infinite sum will ruin things, so lets actually perform the infinite sum. The chance of stopping on exactly the Nth flip is p(1-p)N-1, as (1-p)N-1 is the chance you failed the first N-1 flips, and p is the chance you stopped on the Nth one. Summing to find the expectation value of N, and we will denote 1-p=q and D as derivative with respect to q, so we have
< N > = Σ Np(1-p)N-1 = p Σ NqN-1
= p Σ D(qN) = p D Σ qN = p D(1/(1-q)) = p(1/(1-q)2)
= 1/p
So, we see that the naive expectation is actually correct, still, it is nice to prove it.
Now, moving on with our actual problem, for our strategy to work, we first must have one of the 99 non master prisoners to come in, then we need the master to come in, then one of the 98 remaining, then the master again, and so on down the line. the chance of each of these events is easy to figure out (remember, we are assuming that the warden selects a random prisoner each day). So, for the first few terms, the number of days it takes is 100/99+100+100/98+100+100/97+... since each time the master needs to enter the room, it takes about 100 days for that to happen. The full sum is
100*99+100* Σ 1/N
Where N is summed from 1 to 99. Approximating, that comes out to 9900+100Ln99 ≈ 10359, which is a little over 28 years. It would be nice to see if there is a solution with a smaller expectation number of days, especially since the average number of days it takes for every prisoner to enter the room once is 100Ln100 ≈ 460.
Now, for the real problem we have a bit more of a trick on our hands. For the solution when the prisoners do not know the initial position of the switches, they must have the master enter the room 198 times to count everybody. This means we have a flat out 19800 days on top of how long it takes the non masters to do their stuff. Each prisoner must enter the room twice and then gets ignored. This is equivalent to the following problem:
Consider a bag filled with N white balls. At each step, you select a ball from the bag. If the ball is white, paint it green and return it to the bag. If the ball is green, paint it black and return it to the bag. If the ball is black, return it to the bag. On average, how many steps will it take for the bag to have only black balls left in it?
If we let F(N) denote the solution to that problem, then our prisoners expect to get out in 19800+F(99) days. This problem is actually difficult to solve, and I doubt it has a nice solution, I will share my thoughts on it here to see what we can get.
First, let f(w,g,b) denote how many steps on average it takes to get from a position with w white balls, g green balls, and b black balls to the final position of w+g+b black balls. Now, suppose that half the bag has black balls in it, that means that it is the same as a position with no black balls in it but every step takes twice as long. In mathspeak, I claim that f(w,g,w+g)=2f(w,g,0), similarly, if 2/3 of the balls are black each step will take 3 times as long, and this can be extended into the claim that f(w,g,b)=(w+g+b)/(w+g) f(w,g,0). Its a bit of a trick to prove it, but I assure you that it is true. Now, we know that from the position represented as (w,g,b), we can take three possible paths, giving us the result that
f(w,g,b)=w/(w+g+b) [f(w-1,g+1,b)+1]
+g/(w+g+b) [f(w,g-1,b+1)+1]+b/(w+g+b) [f(w,g,b)+1]
The three terms represent the chance of drawing a white, green, and black ball, respectively. Now, let us denote f(w,g,0) as H(w,g), then by the earlier claim we have f(w,g,b)=(w+g+b)/(w+g)H(w,g), and so, setting b=0 in the previous equation, we find for H, the relation
H(w,g)=w/(w+g) [H(w-1,g+1)+1]+g/(w+g) [f(w,g-1,1)+1]
H(w,g)=w/(w+g)H(w-1,g+1)+g/(w+g-1)H(w,g-1)+1
Alright, now just to find the H that satisfies that recursion relation with the initial condition H(0,0)=0. First, we can try to find H(0,g). It must satisfy
H(0,g)=g/(g-1)H(0,g-1)+1
This turns out to be solved by our previous solution of H(0,g)=g Σ 1/i summing i from 1 to g. One can try a similar trick for H(1,g), but the solution gets ugly fast.
This is as much progress as I have made on the solution, I still doubt it has a clean solution at all, but if anybody can get a solution feel free to post it in the comments.
No comments:
Post a Comment