Google question: In a country in which people only want boys

Question

Hi all!

Google published recently questions that are asked to candidates on interviews. One of them caused very very hot debates in our company and we're unsure where the truth is. The question is:

In a country in which people only want boys every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

Despite that the official answer is 50/50 I feel that something wrong with it. Starting to solve the problem for myself I got that part of girls can be calculated with following series:

$$\sum_{n=1}^{\infty}\frac{1}{2^n}\left (1-\frac{1}{n+1}\right )$$

This leads to an answer: there will be ~61% of girls.

The official solution is:

This one caused quite the debate, but we figured it out following these steps:

• Imagine you have 10 couples who have 10 babies. 5 will be girls. 5 will be boys. (Total babies made: 10, with 5 boys and 5 girls)
• The 5 couples who had girls will have 5 babies. Half (2.5) will be girls. Half (2.5) will be boys. Add 2.5 boys to the 5 already born and 2.5 girls to the 5 already born. (Total babies made: 15, with 7.5 boys and 7.5 girls.)
• The 2.5 couples that had girls will have 2.5 babies. Half (1.25) will be boys and half (1.25) will be girls. Add 1.25 boys to the 7.5 boys already born and 1.25 girls to the 7.5 already born. (Total babies: 17.5 with 8.75 boys and 8.75 girls).
• And so on, maintianing a 50/50 population.

Where the truth is?

Answer 1

The proportion of girls in one family is a biased estimator of the proportion of girls in a population consisting of many families because you are underweighting the families with a large number of children.

If there were just 1 family, then your formula would be wrong, but the average of the percentage of girls you would observe would be

$$\sum_{n=0}^\infty \frac{1}{2^{n+1}} \bigg(\frac{n}{n+1}\bigg) = 1-\log2 = 30.69\%.$$

Half of the time, you would observe $0\%$ girls.

If you have multiple families, the average of the observed percentage of girls in the population will increase.

For 2 families, the average percentage of girls would be

$$\sum_{n=0}^\infty \frac{n+1}{2^{n+2}} \bigg(\frac{n}{n+2}\bigg) = \log 4 - 1 = 38.63\%.$$

More generally, the average percentage for $k$ families is

$$\sum_{n=0}^\infty \frac{n+k-1 \choose k-1}{2^{n+k}} \bigg(\frac{n}{n+k}\bigg) = \frac{k}{2}\bigg(\psi\left(\frac{k+2}2\right)-\psi\left(\frac{k+1}2\right)\bigg)$$

where $\psi$ is the digamma function which satisfies

$$ \psi(m) = -\gamma + \sum_{i=1}^{m-1} \frac1i = -\gamma + H_{m-1}$$ $$ \psi\left(m+\frac12\right) = -\gamma -2\log 2 + \sum_{i=1}^m \frac{2}{2i-1}.$$

With a little work, one can verify that this goes to $1/2$ as $k\to \infty$. So, for a large population such as a country, the official answer of $1/2$ is approximately correct, although the explanation is misleading. In particular, for $10$ couples, the expected percentage of girls is $10 \log 2 - 1627/252 = 47.51\%$ contrary to what the official answer suggests. With $k$ families, the expected proportion is about $1/2 - 1/(4k)$.

It is not enough to argue that the expected number of boys equals the expected number of girls, since we want $E[G/(G+B)] \ne E[G]/E[G+B].$ Expectation is linear, but not multiplicative for dependent variables, and $G$ and $G+B$ are not independent even though $G$ and $B$ are.

Answer 2

There is a closely related puzzle about cards. I was told it by Vin de Silva, who said he was told it by Imre Leader, but I have no idea what the original source is.

An ordinary deck of cards, face down, is placed in front of you in a stack. A dealer turns the top card of the stack face up and puts it on a separate pile, and does this repeatedly until you say "now". At that point he turns over the next card and stops. You can say "now" at any time from the very beginning (before the first card is turned over) until almost the very end (just before the last card is turned over). You win if the last card turned over --- the one turned over just after you say "now" --- is red. What is the winning strategy?

You can get yourself into all sorts of convolutions trying to solve this. For example, you might think that it's good to wait until lots of the cards revealed so far are black, because then the probability that the next card will be red is relatively high.

But the solution is that it makes no difference at all what you do. Your probability of winning is always 0.5. To see this easily, imagine that after you say "now", the dealer turns over not the top card of the stack, but the bottom one. Clearly this game is equivalent to the original one, and clearly your probability of winning is 0.5 no matter what you do.

I'd like to take this easy solution and translate it into an equally compelling solution to the boy/girl puzzle, but right now I can't see how.

Answer 3

For those who still don't get it, it might help to consider this ultrasimplified example:

A certain family has a 3/4 chance of having 1 girl and a 1/4 chance of having 3 boys.

What is the expected number of girls in this family? 3/4. What is the expected number of boys? 3/4. What is the expected difference between the number of girls and the number of boys? Zero.

But what is the expected fraction of girl-births? There's a 3/4 chance that it's 100%, and a 1/4 chance that it's 0%. Therefore the expected fraction is 75%. Which, notably, is not 50%.

Moral: Just because the expected difference is zero, you can't conclude that the expected ratio is one.

(There is of course nothing new here beyond what Douglas Zare has already made crystal clear, but I'm thinking the starkness of the example might help.)

Answer 4

Let $X$ be the number of daughters of a certain couple. The probability that the first son of this couple is the $n$-th kid is $\frac{1}{2^{n}}$ and so $\mathbb E (X)=\sum_{n=0}^{\infty}\frac{n}{2^{n+1}}=1$. On the other hand the couple will have exactly one son so the expected proportion is 50-50.

Answer 5

I think this is already implicit in the heavily up-voted answer, but it may be worth clarifying: there are two kinds of expectations that we can talk about.

The first is the distribution of G/B, G/(G + B), B/G, B/(B + G), values for the entire population (along with its expected value, standard deviation, etc.). Here, the distribution is over all possible "runs of history", so to speak, in the sense that we average over all possible ways history could turn out. If the population is large enough (thousands? millions?), then the expected values of all these quantities are what you would expect from a 50:50 split, and the standard deviations are near zero. Thus, as far as demographic estimations of the overall population are concerned, 50:50 is the way to go. In fact, at the population level, the ratio of girls to boys cannot be influenced by stopping strategies; any influence must either (i) affect the relative probability of conception of male versus female fetus (ii) adopt a post-conception filtering mechanism, such as induced abortion or infanticide).

The second is the expected G/B, G/(G + B), B/G, B/(B + G), etc., values over families. More generally, we may be interested in the distribution of different (G,B) values for different families. If we are interested in understanding family dynamics more thoroughly, we may also be interested in the birth orders, i.e., in what order girls and boys arise. Here, family stopping strategies could affect the distribution of (G,B) values and also of the birth orders. In particular, the strategy here ("stop as soon as you have a boy") gives 50% of the families with a single boy, 25% with one (older) girl and one (younger) boy, 12.5% with two older girls and one younger boy, and so on (assuming the complication of twins and triplets does not arise). This could have important demographic implications in the long term, when mating is done for the next generation (since birth order and the age gaps between children and their parents all play a role in mating and the creation of chlidren). However, that is getting beyond the current question.

For this second sense, it is not just the expected value per family that matters, but rather, the specific distribution of families. As already pointed out, since the variables are not independent, E[G/B] is not the same thing as E[G]/E[B], so what variable we choose to average over affects what answer we get. Looking at the whole distribution conveys more information.

When demographers are making short-term population estimates, it is the first sense (expected values for the population over runs of history) that is relevant, so stopping strategies can be discounted unless they are accompanied by post-conception selective strategies or strategies that affect conception probabilities. A deeper understanding of society would require knowing things in both the first and the second sense.

Answer 6

Another way to look at the "official" solution is to notice that for statistical purposes it does not matter which couple gets the next child. You "request" children from the couples in whatever manner you want, you always get a 1:1 expected ratio in boys and girls, regardless of the pattern in which you choose the next couple to produce another child.

Answer 7

It doesn't make much sense to compute the expected proportion of girls per family. Take two families, one with just a single boy, and another with eight girls and a boy. The average number of girls (resp. boys) per family is four (resp. one); and indeed, four times as many girls as boys were born. But the average proportion, which is what you are calculating, is (0 + 8/9) / 2 = 4/9, which is less than 1/2! So although your calculation may be correct, the answer doesn't really mean very much.

Answer 8

When I posted this problem on my blog, one commenter (who prefers to remain anonymous but gave me permission to repost here) noted a cool way to estimate the expected value of $B/(B+G)$.

Write $f(G)=B/(B+G)$ and expand in a Taylor series around $B$:

$$f(G)=f(B)+f'(B)(G-B)+(1/2)f''(B)(G-B)^2+...$$

Now take expected values: We have $E(G-B)=0$ and $E(G-B)^2=2B$, so

$$E[f(G)]=f(B)+(1/2)f''(B)(2B)+...$$ $$=(1/2)+1/(4B)+...$$

Now the number of boys is equal to the number of families, so for $k$ families, the proportion of boys is well estimated by

$$(1/2)+(1/4k)$$

and of course it's easy to get better estimates by going to higher terms in the Taylor series.

My commenter also adds the following (in my opinion, quite insightful) remarks:

Independence (or, more precisely, correlation) isn’t the only issue. Even for independent variables, the expected value of a ratio is not equal to the ratio of the expected values. (The expected value of a product of uncorrelated variables is the product of the expected values, though.) This is one of the most important keys to understanding this problem, I believe. And this is why I suggested the Taylor series to expand the ratio about its mean. I also think it is a little easier to find the expected proportion of boys because the random part (G) only appears in the denominator. Also, B is equal to the number of mothers, so I don’t believe B and G are independent because I don’t believe the number of girls is independent of the number of mothers.

Answer 9

Of course, in the real world the sex ratio of a couple's offspring is a random variable with mean near 0.5. If a couple contains to product offspring until a boy is produced, the couples who tend to produce more girls will have larger families, and the proportion of girls will be higher than 50%.

Answer 10

Caveat: This is not an entirely serious answer.

There has been some (heated?) discussion as to the sensitivity of the various answer to the particular model. I thought, for my own amusement, that I would do some Monte-Carlo experiments with a "plausible" model involving Pilgrims traveling to the New World. However, in thinking about possible models, I came up with the following issue. Suppose we assume that:

1. Once Pilgrims marry, they stay married, and do not re-marry if their spouse dies.
2. No living Pilgrim has a direct living ancestor older than their grandparents.

Under these assumptions, it follows that if there were N male Pilgrims in the first settlement, then, at any given time, there are at most 3N male Pilgrims. Moreover, the probability of the settlement dying out over several generations (because all the children are girls) is non-zero. By Kolmogorov's zero-one law (overkill), it follows that almost surely the Settlement will die out, and not become the kick-ass country it may well have been.

Answer 11

A colleague, Eugene Salamin, came up with what I would consider the "Book" solution:

Phooey, this isn't at all a mathematical puzzle. A social convention cannot override biology, so the proportion of boys and girls is the biologically determined one, nominally 1/2, 1/2.

I didn't immediately understand his reasoning. But if all families are enumerated 1,2,3,... and you imagine each family's sequence of children placed in numerical order to make one infinite (or very long) sequence, then the resulting sequence of B's and G's is statistically identical to one you would get by repeatedly flipping a fair coin.

Viewed this way, the rule for stopping when the first B is reached is clearly a red herring! And clearly the proportion of boys and girls will be equal. (At least asymptotically, with probability 1, by the Strong Law of Large Numbers.)

(Likewise, if the original question is varied so that Prob(B) = p and Prob(G) = q, p+q=1, then by the same reasoning the ultimate proportions of boys and girls are p and q, respectively.)

P.S. On the other hand, this does not work for each possible stopping rule. Say we're back to the usual assumption of each birth having an equal chance of being a boy or girl. In an imaginary world, suppose each family stopped having children when the proportion of the girls in their family first exceeded 2/3. Then the ratio of girls to boys in the population will clearly be greater than 2.

Answer 12

Perhaps I am missing something here but it seems quite intuitive to me that it has to be 50-50.
Think of it as coin tosses: As the resulting distribution is completely independent of the stopping time the proportion will in the limit always converge to the original distribution which is supposed to be 50-50. That is because the resulting stochastic process is markovian and a martingale
Or put another way: It doesn't matter when you stop tossing, the outcome will always add up to 50-50 because the coin doesn't have a memory.

It is a little bit like trying to invest in the stock market and getting out every time you are in the plus (sitting out negative phases) and after that beginning all over again. This seems like a clever infallible strategy - alas it doesn't work and you will stay at zero in the long run (here minus transaction costs of course)

(BTW: This reminds me of some friends of ours who desperately wanted a boy - now they have three girls and stopped "trying"... ;-)

Answer 13

The correct answer has nothing to do with the number of families. This is a very tricky problem, and many people fall into the trap of trying to average each possible fraction of girls, weighted only by the probability of that outcome. But in fact they would need to be weighted also by the size of the population, if that strategy is used to find the answer.

Google's reasoning is perfectly correct, but here is another route to the same result. We just find the expected number of boys and the expected number of girls for one family.

The number of boys is obviously 1 for any outcome (of the form GⁿB), and so its expectation is 1.

The expected number of girls is given by the summation of n·p(n) for n = 0 to ∞, where p(n) = the probability of the outcome GⁿB, which is 1/2ⁿ⁺¹. This sum is perhaps surprisingly also 1, which is easy to verify.

Thus each family's expected number of children is 1+1 = 2, and for N families, this just becomes N+N = 2N. And so on average, the population will have an equal number of children of each sex.

P.S. I will agree that Google's phrasing could have been more precise. But that is the case with virtually any math problem that is phrased as a problem in the real world, and I believe Google's intended problem is sufficiently clear that there is no real value in debating all its possible meanings.

Answer 14

My way to look it is a bit different. The possibile sequence and the respective probabilty of new born can be:

• B - 1/2
• GB - 1/2*1/2
• GGB - 1/2*1/2*1/2
• GGGB - 1/2*1/2*1/2*1/2
• ...
• ...

After Summing it up. Total Number of Boys is: 1/2 + 1/2*1/2 + 1/2*1/2*1/2 + ... = 1 On the same lines, Total number of Girls is: 0 + 1/2*1/2 + 2 * 1/2*1/2*1/2 + 3 * 1/2*1/2*1/2 + ... Which also, give 1 on summing up.

So the ratio remains equal.

Answer 15

I think we may summarize as follow:

We have infinite (countable) number of families. Each family stops to have children when the first boy appears.

We have a number of questions...

What is the expected: a) Ratio girls/boys in a given family?

b) Ratio boys/girls in a given family?

c) Ration boys/children in a given family?

d) Ratio girls/boys in the country?

e) Ratio boys/girls in the country?

f) Ration boys/children the country?

Some more: g) Number of children in a given family?

h) Probability of exactly one child in a given family?

And answers: Each family has exactly one boy. So:

a) $E(G1/B1)=E(G1)=1$ (one may do the sum $\sum_{i}0.5^{i}(i-1)=1$, or remark that $x=0.5\cdot 0+0.5\cdot(x+1)$ and obtain $x=1$)

b) Is not defined as $P(G1=0)=1/2$

c) $E(B1/(B1+G1))=E(B1/(B1+1))=E(1-\frac{1}{B1+1})=1-\sum_{i}0.5^{i}\frac{1}{i+1}=1-log(2)$

d) Let $R_{n}$ be the ratio for the first $n$ families, $R_{n}=\frac{G1+G2+...+Gn}{n}$. By the SLLN $R_{n}$ converges to $E(G1)$ a.s. So that (as) $lim R_{n}=1$

e) Honestly speaking, $1/R_{n}$ is not defined with probability $0.2^{n}$, so it is not correct to speak about $\lim 1/R_{n}$. But $1/lim R_{n}$ is defined a.s. and is equal to 1.

f) Let $Q_{n}$ be the ratio for the first $n$ families, $Q_{n}=\frac{n}{n+G_{1}+...+G_{n}}=\frac{1}{1+R_{n}}$. It is well defined and converges as. to 0.5

g) $E(G1+B1)=2$ (one may do the sum $\sum_{i}0.5^{i}(i+1)=1$, or remark that $x=0.5\cdot 1+0.5\cdot(x+1)$ and obtain $x=2$)

h) $0.5$

Answer 16

Maybe this is off topic (since it is applied statistics). But why not look at the problem as "What is the expected number of failure X till there is as success?" This corresponds to a negative binomial distribution which has an expected value of E[X] = r*(1-theta)/theta. r is the number of success, in this case it is r = 1. So, the expected number of failure (girls, sorry!) are 1*(1-0.5)/0.5= 1. The proportion girls/boys is 1:1.

Answer 17

The answer is simply the same as in the coin tossing experiment, and there is a one word proof of it, Martingale, which gives 50-50. The first time one stops giving birth is based on an event that is known at the time, hence the associated stopping rule is adapted to the natural filtration and by optional stopping theorem, E(X_tau) = E(X_0) for a stopping time tau and martingale X_t, which in this is the number of male children minus female children after each birth. This also shows why killing babies is wrong.