Walking In Puzzletown

Figure its about time to finish of the discussion of the follow-up puzzle for the puzzletown problem, and of course, by discussion I mean my typing and you reading.

The basic solution was posted in the comments last time, it has to do with infinite family sizes. Consider each family measuring the variable #girls-#boys, which I will call x. At any given time, x is performing a random walk on the integers, increasing by 1 with probability 1/2 and decreasing by 1 with probability 1/2. The random walk starts at 0 and stops if it ever hits -1, on average how many steps does the random walk run for?

Initially, I tried to let F(x) be the number of steps it takes to get from x to -1 on average, write down the recursion relation, and solve. This sort of fails, and it is related to the fact that F(x) is actually infinite everywhere in our problem, so you have started with something of a non-function.

In an attempt to make the function converge, let us consider a random walk on the integers between a and b, starting at some point and stopping when we ever hit either a or b. In effect, a=-1 and b is some large number where the family will "give up" if the girls outnumber the boys by at least b.

Let f(x) be the average number of steps it takes to get from x to either a or b (I initially defined this as f(a,x,b), but that was far too cumbersome). Clearly we have f(a)=0=f(b), and we also have the recursion relation:

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

That is, half the time f(x) is 1 more than f(x-1) and the other half the time it is 1 more than f(x+1). This can be written as:

f(x)-f(x-1)=f(x+1)-f(x)+2

So, defining d(x) as the derivative function, d(x)=f(x+1)-f(x), we have

d(x+1)-d(x)=-2

So, it appears that the second derivative of f is -2, giving the impression f is a quadratic with leading coefficient -1. Anyway, lets see what it actually is. Our last equation tells us:

d(x)=d(a)-2(x-a)

I didn't have to use 'a' for my constant in that equation, I could have used any value, but 'a' made the most sense.

Next, f is the "integral" of d:

f(x)=f(a)+Σ d(n)
=Σ (d(a)-2(n-a))

The sum over n runs from a to x-1. You might expect it to run to x (an intuition you get from integrals), but you can confirm that running to x-1 is the correct expression, from d(x)=f(x+1)-f(x). Naturally, f(a)=0 is one of our boundary conditions.

Performing the sum, we get:

f(x)=(x-a)(d(a)-2a)-2Σ n

The sum &Sigma n from a to x-1 can be broken into two sums, from 1 to x-1 and from 1 to a-1, giving x(x-1)/2-a(a-1)/2, so that

f(x)=(x-a)(d(a)-2a)-x(x-1)+a(a-1)

So, indeed f is a quadratic with leading coefficient -1. We know that f(b) must be 0, so that:

0=(b-a)(d(a)-2a)-b(b-1)+a(a-1)
(d(a)-2a)(b-a)=b²-a²-(b-a)=(b+a-1)(b-a)
d(a)-2a=b+a-1

Might be worth noting that I assumed (b-a) was nonzero there, so this whole thing collapses if we don't have that.

Anyway, new we can see that f is given by

f(x)=(x-a)(b+a-1)-x(x-1)+a(a-1)
=x(b+a)-x²-ab
=(b-x)(x-a)

Demonstrating the (well known) result that if you have a random walk between -a and b starting at 0, the average time it takes is ab.

Anyway, if we have a family that will stop having children when they have more boys than girls, or they will quit if the girls outnumber the boys by 100, the average family size is 100. If instead they will give up when the girls outnumber by a million, then the average family size is a million. If they will never give up, then the average family size diverges to infinity.

This means that the average family size in our puzzle scenario is infinite. Had we worked out that the average family was size n, it would have (n+1)/2 boys and (n-1)/2 girls (every family has exactly one more boy than girl). And the fraction of children that are boys would be (n+1)/(2n). As n tends to infinity, this is 1/2.
Some might say that it is absurd to believe that the average family size is infinity, you can run this experiment with as many families as you like, and never once will you find that the average family size is infinity. Whats more, you will never end the experiment with a town were the boys are exactly 1/2 of the children, they will always be more than 1/2 of them. This is quite correct, and actually raises an interesting point about probability.

When we say that something happens with probability 1/2, we do not mean it will happen exactly 1/2 the time. We really mean that if you were to perform the experiment n times, and you found that you got k occurrences of the event, in the limit as n goes to infinity, k/n would go to 1/2. For example, consider the first problem, when families stopped when they had 1 boy. If you ran this with some number of families, you probably would not get that exactly half the children were boys (they might be, but that would be a coincidence, really). You would get something reasonably close to 1/2, but probably not 1/2. All you can do is find the fraction of children that are boys when you have n families, and then take the limit as n goes to infinity. I will say with confidence that that will tend to 1/2 (subject to replicating the conditions of the problem, odds are that humans actually do not produce each gender equally likely).

In this problem you have something similar, if you run the experiment with any finite number of families, you will not get that boys are 1/2 the population, they will always be slightly greater than 1/2. But if you take more and more families for the experiment, you will find that the fraction of children that are boys gets closer and closer to 1/2. In the limit as the number of families goes to infinity, the fraction will tend to exactly 1/2. There is nothing wrong with a sequence of numbers that is strictly greater than 1/2 tending to 1/2, that happens all the time, and it is happening here.

I would also like to mention that this "n goes to infinity" interpretation of probability is also important when we talk about something happening with probability zero or probability one. If a mathematician says an event in an experiment will happen with probability zero, they do not mean that it cannot happen (though it might mean that), they mean that if you were to try the experiment n times and measure k occurrences of the event, that k/n will get arbitrarily small as n goes to infinity. So, for example, if you were to spend $1 per experiment and won $X every time the event occurred, no matter how large you set $X to, you will wind up losing money in the long run. They also call this probability zero because they have nothing else to call it. There is no positive number that is small enough to correctly represent the situation, and for most anything that matters in probability, we always have to clarify things by saying "after a large number of trials" anyway, so zero is the most correct number we can use to describe the probability of such events.

The Children In Puzzletown

OK, time for the simple solution to the puzzletown problem. It was an interesting problem to pose to my officemate, who immediately thought that there would be more boys than girls (every family has at least one boy, after all), but then he realized that since the parents stop as soon as they have one boy, they will never have two boys, but sometimes they will have multiple girls before having a boy. Naturally this led him to conclude that there would be more girls than boys. Lets see what the math gives us.

First, since every family has exactly one boy, we need only ask how many girls a family has on average. We could similarly ask what is the average family size. A family is size 1 with probability 1/2 (they had a boy right away) size 2 with probability 1/4 (girl then boy) size 3 with probability 1/8 (GGB) and size N with probability 1/2^N. The average family size is therefore

Σ N/2^N

N summed 1 to infinity.
A sum of the form

Σ N/x^N+1

Is just

d/dx Σ -1/x^N
=d/dx Σ -(1/x)^N
=-d/dx 1/x*1/(1-1/x))
=d/dx 1/(1-x)
=1/(1-x)²

(If my sum confused you, remember the sum is running 1 to infinity, not 0 to infinity). So the average family size is

2 Σ N/2^N+1
=2

So, an average family has 1 girl and 1 boy. Thus the ratio is 1:1.
When this was posted on the xkcd forums, some people said that this answer is obvious, that since each child has expectation 1:1 value of boy:girl ratio, that no matter what criterion the parents use to decide to stop having children, the ratio will be 1:1, simply by linearity of expectation. This argument is quite correct, and is quite similar to the logic from the card flipping problem some time ago.

Some people on the forums then refuted this method of arriving at an answer by posing the following problem:

Each family will have children until they have had more male children than female children, then they will stop having children. On a given birth, it is equally likely that the child will be a boy or a girl. What is the ratio of boys to girls among the children in puzzletown?

This is a slight difference, as now every family will be guaranteed to have more boys than girls. Since it is true for each family, it must be true for the average of the families. One might ask the question of "what if they keep having children and they never have more boys than girls?" however this is not an issue, random walk theory will guarantee that given enough children, every family will at some point have more boys than girls.

The question here is, in this new problem, what happened to the linearity of expectation argument? Every family will have more boys than girls for certain. Therefore, the town will have more boys than girls, what went wrong?

The People In Puzzletown

Time for a new problem. This one is not very difficult, you should be able to solve it in a matter of minutes, but it has a pretty neat follow-up, so I want to post it. I first learned this on the forums at xkcd.

The parents in puzzletown all want to have boys. Each family will have children until they have had at least one male child, then they will stop having children. On a given birth, it is equally likely that the child will be a boy or a girl. Assuming a large number of families, what is the ratio of boys to girls among the children in puzzletown?

Forward Is Backward

Some time ago, I had presented Jon with the balls in a bag puzzle, and he had suggested the following reverse puzzle:

Consider a bag with N red balls. At each step, you select two balls from the bag and if they are the same colour, you repaint one of them a new unique colour. If they are different, then do nothing. Either way, place the two balls back in the bag and begin a new step. Given long enough, eventually all the balls in the bag will be of different colours, on average how many steps does it take?

Its clear that this is some sort of reverse of the original problem, however, it is not clear that this is actually the "best" reverse. One could also give the newly coloured balls "random colours from the list of N colours" instead of new unique ones, but it turns out this problem is much more awful.
Anyway, I'm going to just solve this reverse problem on the spot, it seems like the thing to do. Let F(k) be the average number of steps it takes to get from a state with k red balls to a state with one red ball. Note that knowing the number of red balls totally specifies a state, since all non-red balls are of unique colours. F(1)=0 trivially, and we seek F(N), the state with N red balls. The probability that we move from a state with k red balls to a state with k-1 red balls (I will call this P(k)) is the chance that we draw exactly two red balls from the bag, that is:

P(k)=k/N*(k-1)/(N-1)

Of course, if something happens with probability p, then on average we need 1/p tries to have it happen once (I proved this back in the post where I gave the solution to the prisoner problem). Naturally then, we have:

F(k)-F(k-1)=(N-1)N/(k-1)k

and since F(1)=0, we can just express F(m) as F(m)-F(m-1)+F(m-1)-F(m-2)+...+F(2)-F(1), to give

F(m)=Σ N(N-1)/k(k-1)

summing k from 2 to m.
Therefore, for F(N) we have:

N(N-1)Σ 1/k(k-1)
=N(N-1)Σ [1/(k-1)-1/k]

summed k from 2 to N. This series telescopes, the terms look like 1/1-1/2+1/2-1/3+1/3-1/4+...-1/(N-1)+1/(N-1)-1/N. The final result is then that:

F(N)=N(N-1)[1-1/N]
=N(N-1)[(N-1)/N]
=(N-1)^2

Weird.
Alright, so this (much easier) problem has the same answer as the "forward" ball problem. I guess in some sense it is the correct reversal of the initial problem, since it has the same answer. I would love to find a way to show that these two problems have the same answer (that does not rely on using the fact that they both give (N-1)^2), so that way we can solve the harder one just by doing the easier one. Anyway, thats all I got here, if you can find a way to show that these problems are equivalent, feel free to give it in the comments.