## Amazon Interview Question

Software Engineer / Developers**Country:**United States

Hi Westlake, can you pls explain why probability of having only 2 children, 1 boy and 1 girl is 0.5^2. It should be 0.5 not 0.25

In general the probability formula for having k successes in n tries is

(n!/(n-k)! * k!) * p^k * q^(n-k)

Here

k = success (Getting a boy)

n = number of tries (in 2 children case, number of tries are 2)

p = Probability of success in 1 trial (Probability of getting a boy and a girl is 0.5 each)

q = 1-p = Probability of failure in 1 trial (probability of failure, that is getting a girl child is 0.5)

So for p(2,1) = (2! / 1! * 1!) * 0.5 ^1 * 0.5^1 = 0.5

The couple have 2 children when they first had a girl and then a boy.

The change for a girl is 0.5 and the chance for a boy is 0.5. The chance for this combination is 0.5*0.5 = 0.25.

How did you come up with this:

```
It's easy to find out that
Q*2 - Q = P
P*2 - P = 1
```

???

I think

```
Q*2 - Q = Q
P*2 - P = P
2 * 2 - 2 = 2 != 1
```

This problem can be solved by using Negative Binomial distribution NB(r,p), where the r is the number of success(boys), in this case: r=1. Let X be the number of girls. You would need to calculate the expected value of girls: E(X)= pr/(1-p)=(1/2)/(1/2)=1 for NB distribution. So the ratio is E(X)/E(# of boys) = 1/1=1.

This question can be extended: say the probability of having a boy is not 1/2, say 51/100, and # of boys each family want is 3. Now this ratio should be E(X)/r = p/(1-p) = 49/51. So the # of boys won't affect the ratio, while the probability of having a boy will.

I believe the answer is - there is eventually no one left. Eventually, you have all boys (whats left of them) and the next generation cannot proceed. This is because as each generation passes, you will have the possibility of having less girls than boys. When that happens, the next set of parents will less than the previous set. The boys who did not get married will die and not replace themselves for the next generation. On an infinite cycle, its inevitable that the boys will reduce. The girls could have been more than the boys in any given generation, but that is inconsequential becuase the excess girls cannot marry. Therefore, the number of boys can never increase.

While this is a nice observation, it is the answer to a different question, and perhaps based on a different model.

You are asked to quantify the ratio of girls / boys not what happens to the whole population. What if there are no couples and the villagers are self-cloning aliens?

Regardless, based on your model, at any generation "t", we have E[boys] = E[girls]. This expected value could be vanishing-ly small, assuming a marriage model, or excessively large if we assume a self-cloning model.

I think it's one, because even you have more boys than girls, but one boy can only married to one girl. So this make the ratio to 1 in infinite years. The boys who don't have wife will die without children.

While NOT mathematically what people where are expecting .. for that see the standard answer on summing together a infinite series which translates to ratio 1.. I agree with you. The answer looks valid to me. May be people are angry because the could not think beyond maths.

In the mathematical answer as well, there would be time when the ratio would be skewed from perfect 1. And so it would be in case of this answer as well.

Expected number of children N = 1/2 + 2/2^2 + 3/2^3 + ...

2N = 1 + 2/2 + 3/2^2 + 4/2^3 + ...

N = 1 + 1/2 + 1/2^2 + ... = 2.

Thus we would expect the ratio of 1.

I think...

Expectation = sum over x * (probability of x)

1 child = 1 * 1/2

2 child = 2 * 1/2 * 1/2

3 child = 3 * 1/2 * 1/2 * 1/2

...

and so on.

Add them up.

Assuming having a village with 64 families.

After they all have their babies, the village will have 32 baby boys and 32 baby girls. The number of boys = number of girls. Now, 32 families who had boys will stop having babies.

Of the remaining 32 families... 16 will have boys and 16 will have girls. The "total" number of baby boys = total number of baby girls = 32+16=48

Now, we have 16 families still going at it... of these, 8 boys and 8 girls will come out. Total number of boys = total number of girls = 32+16+8 = 56

Now, 8 couples will produce 4 boys and 4 girls. We have 60 boys and 60 girls total.

Next, 4 couples will have 2 boys and 2 girls. 62 boys and 62 girls

2 couples left... 63 boys and 63 girls

And finally we have only 1 couple left... Ignoring this pop couple who have had 8 babies in a row... As counter-intuitive as it looks, we can see that the ratio of baby boys/baby girls remains constant.

for the people that are too concerned about the "infinite years"...

there will come a time, when the sun will turn into a black hole... in billions of billions of billions.... years... but definitely that will happen before "infinite years".

there will be no boys and no girls. the ratio of girls to boys will be undefined (divide by zero)

I think the intent of the interviewer was not to ask about "infinite years", but wanted the interviewee to take a limit as n goes to infinity in the expected value of the two numbers.

The ratio is 1. Think about it this way.

Given "N", "N / 2" of families will have a single boy. The other "N / 2" will have a girl as a first child.

Now let's assume the second "N / 2" give their first-born (girl) to the first "N / 2" family. So we have "N / 2" families with 1 boy and 1 girl, and "N / 2" families where they keep trying until they get a boy. By recursion, you find that the ratio has to be one.

The expected number of boys is 1, since they keep making babies until getting a boy :)

The expected number of children is C = 1/2 + 2/2^2 + 3/2^3 + ... + k/2^k + ...

With some tricks we can find that C = 2.

Thus in average each family have 2 children, 1 boy, 1 girl!

Tricks:

```
C = 1/2 + 2/2^2 + 3/2^3 + ... + k/2^k + ...
2C = 1 + 2/2 + 3/2^2 + ... + k/2^(k-1) + ...
= 1 + (1/2+1/2) + (2/2^2 + 1/2^2) +...+ {(k-1)/2^(k-1) + 1/2^(k-1)} +...
= {(1 + 1/2 + 1/2^2 +...+ 1/2^(k-1) +...} + 1/2 + 2/2^2 +...+ (k-1)/2^(k-1) +...
= 2 + C
=> C = 2
```

I have a different thought. If we consider the fact that human has limited life span, eventually someone will die. In infinite time, don't u think there will be no one left because there there will be less and less girl to match a man?

Probability of having a boy=Probability of having a girl = 1/2

if a family has n children one among them is boy n-1 girls and1 boy

probability of having n children = 1/(2^n)

because n-1 fails(n-1 girl children) * 1 pass(a boy)=1/(2^n-1)*1/2

now the expected number of children in each family is

E[x]=Summation {number of children*probability of having them}

E[x]=1/2 + 2/2^2 + 3/2^3 + ... + k/2^k + ...

E[x]=2(already proven by many)

this means we can expect 2 children in each family but we know that each family has at least 1 boy that's why they stopped(except infinity case). that is 1 boy and 1girl so ratio is 1.

The question asks what will be the population of the village after infinite years. This question has definitely incomplete data. The answer depends on probability for each generation that a given couple will have boy or a girl.

Lets say that for 1st generation (adam and eve) the probability of having boy is 0.25. Which means adam and eve will have to procreate 4 times and 4th child will be a boy. Population after 1st generation will be 4. Now population for 2nd generation also depends on probability of having a boy which can be any number. Hence to predict population for a given generation, we need probability distribution for random variable for the event having a boy which is not given.

If we assume uniform distribution of .25, then the infinite series will not converge and hence the answer is infinity.

The series can converge only if PDF can be such that infinite series can converge.

Hope the answer helps

Doesn't look like my approach is in here!

Since couples stop producing at 1 boy, then we have these possibilities.

```
B
GB
GGB
G...GB
```

Now let's look at the possibilities that these each happen:

```
B (1/2)
GB (1/4)
GGB (1/8)
G...GB (1/(2^n) )
```

And the contribution to the ratio of boys in each of these:

```
B (1/2) (1)
GB (1/4) (1/2)
GGB (1/8) (1/3)
G...GB (1/(2^n) ) (1/n)
```

So we get an infinite series here:

`\sum_i (1/(2^i) ) (1/i)`

My series is shabby, but you can add the first few terms (1/2) and (1/8) and see that it is converging to 2/3.

Thus, over the long term and with a large enough population, 2/3 of the town will be boys and 1/3 of the town will be girls.

The answer is indeed half. Many of the solutions give nice formulas to prove this, but there's a much simpler answer: it's half no matter what stopping conditions are chosen, because of the simple fact that each child born has a 50% chance of being a boy.

Don't believe it's that simple? Consider a random bit string (this is from random.org):

1001101001001100111010110011000111110000

What's the expected fraction of zeros? Half. Now introduce breaks after each one (boy born):

1 0011 01 001 0011 00111 01 011 0011 00011111 0000

Each string is a family that waited til their first boy. *Now* what's the expected fraction of zeros?

It didn't change.

probability of having:

```
1 child = 1/2
2 children = 1/2*1/2
3 children = 1/2*1/2
...
n children = 1/(2^n)
```

Math expectation of having girls:

`1 * 1/2 + 2 * 1/2*1/2 + 3*1/2*1/2*1/2 ... + n * (1/(2^n))`

Math expectation of having boy:

`1/2 + 1/4 + 1/8 + ... + 1/(2^n) = 1`

which means that ratio girls/boy = sum(i=1;i<=n;) i/(2^(i+1)) which is infintiy

LOL :) You really made this board fully of joy! I like your answer very much. Anyway I will give my way to approve the result.

- Westlake March 13, 2014