Two Is Enough

Time for the solution to the hat problem from last time. Not really much to the solution, as Mark pointed out in the commentary its just about parity.

To start, we will number the people from 1 to 100, with the person at the back on the line numbered 1, so N can see the hats of people N+1 and N+2. First thing we need to do is have the two people at the back of the line know their hat colours:

First, person 1 volunteers to guess, and guesses the hat colour of person 3. Next, person 2 volunteers to guess and guesses the hat colour of person 4.

The adversary will ensure that both of those guesses were wrong, so now we have a new problem where the back two people know their own hat colour and we cannot afford anybody to guess wrong. Fortunately, they can now see the hat colour of person 5. They use that to decide who guesses next:

If person 5 has a white hat, person 3 guesses what he knows his own hat to be. If person 5 has a black hat, person 4 guesses what he knows his own hat colour to be.

They are no longer transmitting information by what they guess, it is instead done by who makes the guess. Naturally, whatever happens, the line will shift back and you have the two people at the back of the line with full knowledge of their own hat colour. The person at the very back guesses if the next "unknown" hat is white, and the second person from the back guesses if it is black. The solution works by induction, until only two people are left in the line, when they both know their own hat colour and both of them volunteer to guess (letting the adversary helplessly decide how it ends).

If one states the problem differently, so that instead of a "win-loss" scenario there was some sort of bet based on how many you got wrong, this solution also has the advantage that a mistake by one of the players only results in one extra person being wrong, rather than an entire chain.

Actually come to think of it, that would be a better way to word the problem, to minimize the number of people who guess wrong rather than saying outright how many you can afford. When I post the harder version of this problem I might word it that way.

Myopic Hats In A Line

That counter thing on the right for my blog posts seems to suggest that its been some time since I've had more than one post in a given month... I guess its time to do something about that. Anyway, this puzzle is one I found on the forums at xkcd:

One hundred people are standing in a line, each of them wearing either a black hat or a white hat. They all can see the hats on the two people directly in front of them, no hats behind them and not their own hat. Each round, a man in a black suit will ask each person in the line if they would like to guess their own hat colour now, the answer they give is secret, nobody else in the line can hear. The man will then select one of the people who volunteered and ask their hat colour. That person is then removed from the line and the line is shifted back a step to fill the hole. Everybody in the line is made aware of who was selected to guess their hat colour and what they guessed. The people may only guess "black" or "white". Then a new round starts with the man asking who would like to guess their hat colour now.

The players lose the game if ever more than two people get their hat colour wrong, or if during any round nobody volunteers to guess. The players win if everybody has finished guessing their hat colour and no more than two people are wrong. Before the hats are assigned the players may strategize, find a strategy that is certain to win assuming the man in black (who also assigned the hat colours) is an adversary.

Its some sort of variation on "standard line hat rules", the people are also short-sighted.

Math Is Hard

Apparently, blogging is also hard, given how often I actually do it. Anyway, time to finish off the second part of the tying strings problem.

First of all, its interesting to wonder why the method of calculating the average was worded the way it was. It was "Specifically, consider one were to select an initial piece of string and ask "what is the expected value of the length of the loop this piece of string will end up in?"". This is different than if it had been "Specifically, consider one were to randomly select a final loop from all of the loops and ask "what is the expected length of this loop?"". The first wording basically gives a heavier weighting to longer loops, and will have a larger answer. Also, it gives an answer with an actual clean mathematical form, rather than the second one which gives a total mess (feel free to work it out sometime, maybe somebody smarter than me can point out a nice form of it that I just missed).

Anyway, lets start by figuring out a few simple cases. Suppose we have N strings, and G(N) is the answer we seek. It is pretty easy to see that G(1)=1. For N=2, consider where the first end of one of the strings ends up. With 1/3 chance, it loops to itself, and we have two loops of length 1, with 2/3 chance it does not loop to itself and we have 1 loop of length 2. So,

G(2)=1/3 1+2/3 2
=1+2/3
=5/3

The 1+2/3 line is going to turn into an attempt to establish the overall pattern, the final loop the first string is in (which is as good as any other string) is at least length 1, and 2/3 of the time it is an extra length.

Next, N=3: the first end of the first string (which is the random string we are going to choose at the end) has a 1/5 chance of looping to itself. It has a 4/5 chance of not looping to itself and then a 1/3 chance of closing with length 2 and a 2/3 chance of closing with length 3. So we have

G(3)=1/5+4/5 1/3+4/5 2/3
=1+4/5+4/5 2/3
=7/3

The 1+4/5+4/5 2/3 is again an attempt at the overall pattern, the final loop of the first string starts at length 1, is 4/5 chance to be length +1 and is 4/5 2/3 chance to be another length +1.

We can already guess the overall formula, G(N)=1 + 2/3 (N-1), and if you check the next few terms you will find this still works. To prove it in general is quite the trick though. First, we can see the general formula for G(N):

G(N)=1+Σ Π (2N-2m)/(2N-2m+1)

where the sum has k from 1 to N-1 and the product has m from 1 to k. You can fiddle with this a bit using the formula:

Π (m-N)=Γ (k+1-N)/ Γ (1-N)

(product over m going from 1 to k) (Γ being the Gamma function), or you can just shove it all into Maple at once. Basically you get a bunch of garbage whatever you do.

After spending some time simplifying that garbage, you can find

G(N) = 1+2/3 (N-1)-1/(3 √π ) Γ (1/2-N)/Γ (1-N)

So, we see the term we want, and them some Gamma function garbage. This extra term shows up for a few reasons. First of all, in the first formula Π (m-N)=Γ (k+1-N)/ Γ (1-N), the math doesn't "know" if k is greater than N (in which case you need to get zero), or even if the things you are using are integers at all.

Anyway, in our case everything is an integer, so Γ (1/2-N) is simply a number one can find using the analytic continuation of the Gamma function, and Γ (1-N) is infinitely large, as Gamma has simple poles at every nonpositive integer. So the extra garbage term is just zero.

If one can find a way to solve this problem that doesn't involve the Gamma function, I would love to hear it.

And Then I Blogged Again

So, where did that month go anyway? Well, whatever, I hope the one or two people who still read this have had more than enough time to solve the tying strings problem.

The solution isn't particularly hard:

Consider we have N strings, let f(N) be the solution we seek. Select an end of one of the strings at random (it does not matter which one), and select another end. With 1/(2N-1) probability, they second end is on the same string as the first end, when you tie them together you get 1 loop, plus the problem for f(N-1). With (2N-2)/(2N-1) probability, the second end is on a different string, and when you tie them together you simply have made one string longer and have the f(N-1) case.

So, from this argument, we get the recursion relation for f:

f(N)=1/(2N-1)(f(N-1)+1)+(2N-2)/(2N-1)f(N)
f(N)=f(N-1)+1/(2N-1)

f(1) is 1, of course. f(2) is 1+1/3, f(3) is 1+1/3+1/5. It is a pretty easy thing to prove that:

f(N)=Σ 1/(2k-1)

where k goes from 1 to N.

I guess I'll post the next part of the problem now, in case I forget to blog for the next year:

How long is a loop on average? Specifically, consider one were to select an initial piece of string and ask "what is the expected value of the length of the loop this piece of string will end up in?".

Tying Strings

Man, I still blog, right? I think I had some feeling there was more to write about my last post, but I couldn't come up with anything so I just put it off. Now it seems apparent that that one is just plain done so its time to move on to something more interesting. So, new puzzle, I first learned this one on the forums at xkcd:

You have a bowl of N strings, each the same length. A string is a line segment with two indistinguishable ends, and all the strings are indistinguishable. You randomly select two ends of the strings from the bowl (they might be on the same string, they might not) and tie them together (fuse them, if you prefer). You repeat this process until there are no more ends left and you just have loops of string. On average, how many loops of string do you have?

There are other questions you can ask in this scenario, but to save myself blogging material I'll hold onto them for later.

Keep The Right One

Alright, time to finish off the stuff I've been writing about the two envelope paradox. The analysis last time showed that we had best assume that the smaller cheque is coming from a normalized distribution function P(x) with a finite expectation value (∫ xP(x)dx converges). Now, we must come up with a strategy on wether to keep the cheque or not, and this strategy can only be based on the value of the cheque that we see (known as A). Let us choose to accept the switch when cheque A has a value x with probability S(x). S(x) must be a function from the positive reals to [0,1], but is otherwise arbitrary. Now, we know that the expected gain from switching is E(B|A=x)-x (from last time), times Q(x)=(P(x)+P(x/2)/2)/2 (the distribution function on the cheque A), times S(x) (the chance we actually take the switch). So, the expected gain is

∫(E(B|A=x)-x) Q(x) S(x) dx
=1/2 ∫(xP(x)-x/4P(x/2))S(x) dx
=1/2 ∫xP(x)S(x)dx-1/2∫x/2P(x/2)S(x)d(x/2)

The split into two integrals is valid this time as ∫ xP(x)dx converges and the bounded function S(x) is not going to make that any worse. Now, change variables x/2 -> x in the second integral and recombine to get

=1/2∫xP(x)(S(x)-S(2x))dx

So we see that as long as S(x)-S(2x) is positive, we will have a positive expected gain for any distribution function P(x). Specifically you may choose any decreasing function to get this effect, like S(x)=1-tanh(x). In effect, this means that you are more likely to keep a larger valued cheque than a smaller cheque. This sort of solution also solves a similar game where I write down any two random numbers (from some probability distribution) on cheques and offer you a "keep or switch" scenario.

Anyway, one can also find that the optimal choice of S(x) is to set it to 1 whenever P(x)-1/4P(x/2)>0 and 0 whenever P(x)-1/4P(x/2)<0 (when P(x)-1/4P(x/2)=0, choose S(x) arbitrarily, it doesn't matter), however this assumes that you know the function P.

Wanting Too Much

Alright, time to go into a bit of detail about the two envelope paradox. Much of this analysis I actually originally read on a paper by David Chalmers. Anyway, the first thing to realize is that this paradox can show up even if the amount of money in the first envelope is taken from a well defined probability distribution. That is, suppose the smaller cheque has value between x and x+dx with probability P(x)dx, and the larger cheque is exactly twice the smaller one. Now, we have to ask the following thing: given that we have opened an envelope with value between y and y+dy, what are the odds that it is the smaller cheque? Well, if it is the smaller cheque, then there was a P(y)dy chance of it being written down, but if it is the larger cheque, then there was a P(y/2)d(y/2)=1/2 P(y/2)dy chance of it happening. Thus the ratio of probabilities is 2P(y):P(y/2), though one might naively have expected P(y):P(y/2). In particular, if the first cheque is randomly chosen from 0 to 10 with uniform distribution, and you see a cheque of value 2, then it is twice as likely that the other cheque has 4 than it has 1. This may seem nonintuitive, but this must occur in order to balance out the case that if you see a cheque with value over 10 and then the other cheque must be smaller. Note that this actually will make the initial paradox somewhat worse.
Now we can see that if the distribution function for the smaller cheque is P(x), then the distribution function for a random cheque will be Q(x)=(P(x)+P(x/2)/2)/2. The relative ratio between the two terms was derived last paragraph, and the overall factor of 1/2 comes from normalizing Q(x) assuming P(x) already was properly normalized. Let the first cheque be given a value A and the unknown cheque a value B (B=2A or B=A/2 always). Let E() be the expectation value operator, so that E(B) denotes the expectation value of B, and E(B|A=x) will denote the expectation value of B given that A is the specific value x. The paradox will be at its strongest if E(B|A=x) is greater than x for all values of x (and the paradox will still exist if that had been true on average). Now lets calculate how much money we expect to get by switching blindly without even looking at the value of the first cheque by integrating over the distribution function for the first cheque Q(A). The specific value of E(B|A=x) is (2xP(x)+x/2P(x/2)/2)/(P(x)+P(x/2)/2) being (value if B is larger)(chance B is larger)+(value if B is smaller)(chance B is smaller) divided by normalization, so E(B|A=x) = x/2(8P(x)+P(x/2))/(2P(x)+P(x/2)). Now, the expected gain for switching cheques blindly is:

∫ (E(B|A=x)-x) Q(x)dx
=∫ (x/2(8P(x)+P(x/2))/(2P(x)+P(x/2))-x)(2P(x)+P(x/2))/4 dx
=∫ (x(4P(x)+P(x/2)/2-2P(x)-P(x/2))/4) dx
=1/2 ∫ (xP(x)-x/4P(x/2)) dx

Next is the trick that I really appreciate about this entire thing, assuming that the integral ∫ xP(x) dx converges, we may break this up into two integrals to find

=1/2 ∫ xP(x)dx-1/2 ∫ x/2P(x/2)d(x/2)

Which is simply zero. Note that if P(x) was something like 1/x^2 from 1 to infinity, it will be a properly normalized distribution function, but the paradox will still arise. In order to avoid the paradox, the first cheque needs to have a finite expectation value, otherwise the paradox that E(B) is greater than E(A) isn't really a problem.
More simply put, given infinite expectations, any finite value is disappointing.
Anyway, back to the puzzle I posted last time, you may further assume that the distribution function that the cheques are chosen from have finite expectation value, there is still a strategy that works.