# What is the expected number of children until having the same number of girls and boys?

A couple decides to keep having children until they have the same number of boys and girls, and then stop. Assume they never have twins, that the "trials" are independent with probability 1/2 of a boy, and that they are fertile enough to keep producing children indefinitely. What is the expected number of children?

A similar question was posted at What is the expected number of children until having at least a girl and a boy?, but I cannot seem to apply the same approach here.

• Imo, for empirical (real world) samples, never. In thetheoretical infinite limit, immediately. Aug 5 at 9:58
• I asked a slightly more generalized version of exactly that question a while ago on the math stack exchange: math.stackexchange.com/questions/3073005/… (your question corresponds to k=2) and got some excellent answers. Aug 5 at 18:48
• As far as I can tell, this question is equivalent to asking how long it will take before someone returns to their starting spot in a 1-dimensional random walk, which has an infinite expected value. Aug 6 at 1:19
• This is related (not the same because it asks for the expected value) to a random walk with an absorbing boundary at zero. There is already a solution to that on this site. Aug 6 at 16:37
• I assume you're ruling out zero as the answer? Aug 7 at 1:41

This was a good problem to solve by calculating a few numbers (in this case 2, 2, 4, 10, 28), and checking the Online Encylcopedia of Integer Sequences, in this case A284016.

There are $$Binomial[2n,n]/(2n-1)$$ ways for the couple to achieve parity for the first time with $$n$$ boys and $$n$$ girls. These are twice the Catalan numbers.

So the expected value would be $$\sum \frac{Binomial[2n,n]}{(2n-1)2^{2n}}2n$$ but the sum is divergent: the expected number of children is infinite.

Update: Here is a simple argument for the divergence. Consider a family’s first $$n$$ children, including simulated results for families who stopped with fewer than $$n$$.

For about $$1/3$$ of those families, the difference after $$n$$ children between the number of boys and girls is at least $$\sqrt{n}$$, because the binomial probabilities for each gender approximately follow $$N(n/2,\sqrt{n}/2)$$.

In those families, the probability that the more numerous gender was ahead the whole time is at least $$\sqrt{n}/n$$, by Bertrand’s ballot theorem. So at least $$1/(3\sqrt{n})$$ of families will not achieve parity until they have more than $$n$$ children.

So the expected number of children is at least $$\sqrt{n}/3$$. Since this holds for all $$n$$, the expected number of children is infinite.

• Could you perhaps give an intuitive explanation as to why the answer is infinite, whereas the answer to the question that I linked in my original post was finite? Aug 5 at 12:20
• Dharok, it helps to graph the history of births: plot the number of boys minus the number of girls as a function of the number of births. (This is a Binomial Random Walk.) The referenced question asks about when this plot first changes direction, whereas the present question asks about when this plot reaches the x-axis.
– whuber
Aug 5 at 15:48
• Or: The expectation is infinite because even after having $n$ children, a family has probability of $\sqrt{2/(\pi n)}$ of having never achieved parity. This is a variant on the update, following from Bertrand's Ballot Theorem applied to all of the possibilities for the imbalance of genders, with a normal approximation to the binomial, and the fact that a standard normal variable has expected absolute value of $\sqrt{2/\pi}$. Aug 6 at 2:19
• Related is the Lévy distribution (hitting time for a Brownian motion) with infinite mean. Aug 6 at 23:38
• @yo' the chance of hitting zero is equal to one, or we can make it as close as we want given enough time. Therefore that intuition, the chance of hitting exact match is lower and lower, is not very accurate. Instead, the chance of hitting an exact match approaches one. Thus, the reason for the infinite expectation is not because there is a non-zero chance to escape the possibility to ever have an equal number of boys and girls. Aug 7 at 14:08

The answer by Matt F links to a sequence in the OEIS database, but provides no direct/clear motivation.

One can motivate the answer by considering a random walk with an absorbing boundary. You can consider starting from position 1 for the difference of boys/girls and move up and down randomly with 50% probability until reaching zero.

These type of walks have been described here: What is the distribution of time's to ruin in the gambler's ruin problem (random walk)? and based on the results in those answers we can see that the survival function is related to the binomial distribution.

Imagine, without loss of generality (the situations are symmetric), that the first kid was a boy. The odd rows from Pascal's triangle give the possible number of ways to reach a difference of boys-girls after $$t$$ kids.

$$\begin{array}{cccccccc|l} &&\llap{\text{difference}}\rlap{\text{ of boys - girls}}&&&&&&{\text{number of kids}}\\ -3&-2&-1&0&1&2&3&4 \\ \hline \color{red}{}&\color{red}{}&\color{red}{} &1 & \color{blue}{1}& \color{blue}{}& \color{blue}{}&\color{blue}{}&2\\ \color{red}{}&\color{red}{}&\color{red}{1} &3 & \color{blue}{3}& \color{blue}{1}& \color{blue}{}&\color{blue}{}&4\\ \color{red}{}&\color{red}{1}&\color{red}{5} &10 & \color{blue}{10}& \color{blue}{5}& \color{blue}{1}&\color{blue}{}&6\\ \color{red}{1}&\color{red}{7}&\color{red}{21} &35 & \color{blue}{35}& \color{blue}{21}& \color{blue}{7}&\color{blue}{1}&8\\ \end{array}$$

• The black column represents the number of ways that we can reach at a zero difference of boys - girls.
• There is also a possibility that we reached zero difference before, that is equal to the blue numbers minus the red numbers. Motivation: for each possibility to have reached a negative difference, there is an equivalent possibility to reach a positive difference while having hit zero difference before (consider mirroring the steps after reaching the zero the first time).

Therefore, the probability to still have not reached a zero difference, is equal to the probability to have reached a zero difference.

So for even positive values of $$t$$ we have:

$$\begin{array}{}P(T>t) &=& P(\text{difference} = 0 | T=t)\\ & = &{{t-1 }\choose {t/2-1} }0.5^{t-1} \end{array}$$

And the expectation value can be computed as

$$\begin{array}{} E[T] &=& \sum_{t=0}^\infty P(T>t) \\ &=& 2 \sum_{t=0}^\infty P(T>2t) \\ &=& 2 + \sum_{t=1}^\infty \underbrace{ {{2t-1 }\choose {t-1} }0.5^{2t-2}}_{= 2 \cdot \prod_{s=1}^t \frac{2s-1}{2s}} \end{array}$$

which diverges.

(the second equality occurs because the probabilities are the same for odd and even numbers, when equal boys and girls have not been reached for $$2k$$ children then neither will it have been reached for $$2k+1$$ children)

Comparison with simulations:

set.seed(1)

### function to simulate the random walk
sim = function() {
difference = 1
steps = 1
while(difference != 0) {
steps = steps + 1
if (steps == 1000) {
difference = 0 ## this will stop the loop
} else {
difference = difference + 1 - 2*rbinom(1,1,0.5)
}
}
return(steps)
}

### compute several walks
t = replicate(10^5, sim())

### compute the survival function
k = c(1:50)*2
s = sapply(k, FUN = function(ki) {mean(t>ki)})

### plot simulations with computation
plot(k,s,
xlab = "number of children t",
ylab = "P(T > t)",
main = "survival function of waiting time T \n for event of equal number in boys and girls")
lines(k,dbinom(k/2-1,k-1,0.5))


Could you perhaps give an intuitive explanation as to why the answer is infinite

Consider the absolute difference between boys and girls $$X$$ and the expected number of steps $$T(k \to l)$$ to go from $$X=k$$ to $$X=l$$.

After one child we always have $$X = 1$$, so let's consider $$T(1 \to 0)$$. From $$X=1$$ we get with $$1/2$$ probability back to $$X=0$$ and with $$1/2$$ probability to $$X=2$$. The waiting time can be expressed as one plus the weighted sum of the respective branches after that one step

$$T(1 \to 0) = 1 + \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot T(2 \to 0)$$

and since we can split up the expected waiting time $$T(2 \to 0) = T(2 \to 1) + T(1 \to 0)$$, and expected waiting time to go from two to one is the same as waiting time to go from one to zero $$T(2 \to 1) = T(1 \to 0)$$ we get to

$$T(1 \to 0) = 1 + T(1 \to 0)$$

You can try just calculating and see what happens - that would at least give you some insight. Obviously you need an even number of children. After two children, your chance is 50% of having equal numbers, and 50% for a difference of two. With a difference of two, after two more children the chance is 25% for equal numbers, 50% for a difference of two, and 25% for a difference of four. With a difference of four, after two more children it's 25% for a difference of two, 50% for a difference of 4, 25% for a difference of 6.

So E0 = 2 + E2/2. E2 = 2 + E2/2 + E4/4. E4 = 2 + E2/4 + E4/2 + E6/2 and so on. We can remove for one number in each calculation, for example E10 = 2 + E8/4 + E10/2 + E12/4, so E10/2 = 2 + E8/4 + E12/4 and E10 = 4 + E8/2 + E12/2. This gives E0 = 2 + E2/2, E2 = 4 + E4/2, E4 = 4 + E2/2 + E6/2, E6 = 4 + E4/2 + E8/2 and so on.

Now if we take these equations and in each one substitute lower bounds for the remaining terms from left to right, then we get

E0 = 2 + E2 / 2 >= 2 + 4/2 = 4.
E2 = 4 + E4 / 2 >= 4 + 4/2 = 6.
E4 = 4 + E2 / 2 + E6 / 2 >= 4 + 6/2 + 4/2 = 9.
E6 = 4 + E4 / 2 + E8 / 2 >= 4 + 9/2 + 4/2 = 10.5.
E8 = 4 + E6 / 2 + E10 / 2 >= 4 + 10.5/2 + 4/2 = 11.25.
E10 = 4 + E8 / 2 + E12 / 2 >= 4 + 11.25/2 + 4/2 = 11.625 and so on.

Then we repeat and get

E0 = 2 + E2 / 2 >= 2 + 6/2 = 5.
E2 = 4 + E4 / 2 >= 4 + 9/2 = 8.5.
E4 = 4 + E2 / 2 + E6 / 2 >= 4 + 8.5/2 + 10.5/2 = 13.5.
E6 = 4 + E4 / 2 + E8 / 2 >= 4 + 13.5/2 + 11.25/2 = 16.375.
E8 = 4 + E6 / 2 + E10 / 2 >= 4 + 16.375/2 + 11.625/2 = 18 and so on.

You should be able to show that the lower bounds all go towards infinity.