Probability Puzzles (Part 3)

Here’s a puzzle based on something interesting that I learned from Greg Egan. I’ve dramatized it a bit.

Traditional Tom and Liberal Lisa are dating. They discuss their plans for having children:

Tom: I plan to keep having kids until I get two sons in a row.

Lisa: What?! That’s absurd. Why?

Tom: I want two to run my store when I get old.

Lisa: Even ignoring your insulting assumption that only boys can manage your shop, why in the world do you need two in a row?

Tom: From my own childhood, I’ve learned there’s a special bond between sons who are next to each other in age. They play together, they grow up together… they can run my shop together.

Lisa: Hmm. Well, then maybe I should have children until I have a girl followed directly by a boy!

Tom: What?!

Lisa: Well, I’ve observed that something special happens when a boy has an older sister, with no intervening siblings. They play together, they grow up together… and maybe he learns not to be such a sexist pig!

They decide they are incompatible, so they split up and each one separately tries to find a mate who will go along with their reproductive plan.

Now for some puzzles. In these puzzles, assume that each time someone has a child, they have a 50% chance of having either a daughter or a son. Also assume each event is independent: that is, the gender of any children so far has no effect on that of later ones. Also ignore twins and other tricky issues.

Puzzle 1. If Tom carries out his plan of having children until he has two consecutive sons, and then stops, what is the expected number of children he will have?

Puzzle 2. If Lisa carries out her plan of having children until she has a daughter followed directly by a son, and then stops, what is the expected number of children she will have?

Puzzle 3: Which is greater, Tom’s expected number of children or Lisa’s? Or are they equal?

For maximum benefit, try to answer Puzzle 3 before doing the calculations required to answer Puzzles 1 or 2.

 

19-kids-and-counting

64 Responses to Probability Puzzles (Part 3)

  1. It’s late here right now so for now only preliminary quick guesses.
    If you wanna have a more formal go, maybe don’t look at this until you want a hint or a distraction, depending on whether my guesses are right.

    Puzzle 3 guess:
    Since any particular two-birth-sequence is equally likely (1/4 each), I’d guess that both scenarios are equally likely.

    Puzzle 1:
    Possible sequences:
    SS (1/4)
    DSS (1/8)
    DDSS (1/16)
    SDSS (1/16)
    DDDSS (1/32)
    DSDSS (1/32)
    SDDSS (1/32)
    DDDDSS (1/64)
    DDSDSS (1/64)
    DSDDSS (1/64)
    SDDDSS (1/64)
    SDSDSS (1/64)
    DDDDDSS (1/128)
    DDDSDSS (1/128)
    DDSDDSS (1/128)
    DSDDDSS (1/128)
    SDDDDSS (1/128)
    DSDSDSS (1/128)
    SDDSDSS (1/128)
    SDSDDSS (1/128)
    This looks suspiciously like \sum_{n=1}^\infty \frac{\text{fib}\left(n\right)}{2^{n+1}}
    There is probably some nice combinatorial argument to make to prove this.
    This sum – I didn’t prove but just quickly looked up – sums up to 1, so that’s good.
    The expectation value version of that sum just adds an n:
    \sum_{n=1}^\infty n \frac{\text{fib}\left(n\right)}{2^{n+1}}
    And that appears to sum to 5.

    Puzzle 2:
    Possible sequences:
    DS (1/4)
    SDS (1/8)
    DDS (1/8)
    SSDS (1/16)
    SDDS (1/16)
    DDDS (1/16)
    SSSDS (1/32)
    SSDDS (1/32)
    SDDDS (1/32)
    DDDDS (1/32)
    SSSSDS (1/64)
    SSSDDS (1/64)
    SSDDDS (1/64)
    SDDDDS (1/64)
    DDDDDS (1/64)

    The series appears to be

    \displaystyle{ \sum_{n=1}^\infty \frac{n}{2^{n+1}} }

    which also sums to 1.

    And the expectation value

    \displaystyle{ \sum_{n=1}^\infty \frac{n^2}{2^{n+1}} }

    goes to 3. So Lisa will actually most likely have fewer kids than Tom. Therefore my above prediction was wrong.

    Furthermore, if I did this right, Lisa can expect her value to hover around 3 by 2, whereas for Tom that uncertainty sits around 4.69.
    So in a fairly pessimistic (assuming you want to get there asap) outcome would be 5 trials for Lisa but 10 for Tom.

    (I used that \sigma^2 = \langle-^2\rangle but I’m tired and so possibly error-prone.)

    • Michael Nelson says:

      Here’s how fibonacci shows up:

      You can count the number of ways of Tom winning via a string of n turns by breaking it up into two cases:

      …….DSS
      ….DSDSS

      The first case you counted already in the previous string of length n-1. And the second case you counted already from the string before that of length n-2.

      • This is how I also ended up solving it, getting the Fibonnaci sequence immediately by using a construction approach to compute the number of binary strings (1 == boy, 0 == girl) that had the constraint of ending in ’11’ but with no other ’11’ in them. The construction as you show has the two ways to generate N+1: extend all the length N cases with a ‘0’ in the front and extend the N-1 cases adding ’10’ to the front. This means the number of ways to generate an appropriate string of length N+1 is Fib(N) since Count(N+1) = Count(N -1) + Count(N). And the total strings of length N+1 is 2^{N+1}. Dividing gives you the probability of each string length (number of kids) and the expectation is as was shown above as well. And of course phi (the Golden Mean) shows up in the solution of the characteristic of the Fibonnaci recurrence so ultimately I ended up using it to solve this. Pretty cool!

  2. It’s much quicker, Kram, to model each problem as a state machine.

    Let T_0 and T_1 be Tom’s expectation of future children after zero and one son respectively. We can say immediately that T_0 = \frac{1}{2}(s+T_1) + \frac{1}{2}(d+T_0) and T_1 = \frac{1}{2}(s) + \frac{1}{2}(d+T_0). The solution, if I haven’t blundered, is T_0 = 3d+3s.

    For Lisa: L_0 is her expectation before her first daughter; L_1 is her expectation after any daughter. L_0 = \frac{1}{2}(s+L_0) + \frac{1}{2}(d+L_1) and L_1 = \frac{1}{2}(d+L_1) + \frac{1}{2}(s). Solution: L_0 = 2d+2s.

    Lisa can expect two sons and two daughters; Tom can expect three daughters and three sons.

    The qualitative difference is that for Tom a daughter after a son puts him back a step, while for Lisa a child of the sex not hoped for leaves her in the same position.

    • John Baez says:

      This looks impressively efficient, Anton! But what does an equation like

      T_0 = \frac{1}{2}(s+T_1) + \frac{1}{2}(d+T_0)

      actually mean? I guess I’m lacking the necessary familiarity with state machines to know what type of entities these variables represent, and what addition means. I know what a state machine is; I’m just not familiar with this kind of equation.

      I can guess that T_n is allowed to be any expression of the form a s + b d where a,b \ge 0, and

      T_n = a s + b d

      means “after having had n sons, Tom expects in the future to have a total of a sons and b daughters”.

      But then I don’t know why

      T_0 = \frac{1}{2}(s+T_1) + \frac{1}{2}(d+T_0)

      should be true. It seems to say “after having no sons, Tom expects in the future to have the same thing as if he had a 50% chance of having one more son than what he expected after having one son, and a 50% chance of having one more daughter than what he expected after having no sons”.

      The horrible quoted phrase here certainly shows why a more concise notation is a good thing! It reminds me of what happens when you try to state the quadratic equation in ‘plain English’ without variables.

      But the problem is, I don’t see why it should be true.

      • My subscripts mean only that state 0 must occur before state 1 can occur. I could also say explicitly T_2 = L_2 = 0; does that make anything clearer?

        My equations are the invariants of the tree of futures. The one that you query can be read as: “From state 0, the branches of Tom’s future are: with probability 1/2, he has a son and moves to state 1; and with probability 1/2, he has a daughter and remains in state 0.” As long as his sequence of daughters continues, his expectation of future children remains the same, so the definition of T0 is recursive. From state 1 (one son) Tom cannot remain in state 1; he must either terminate or go back to 0. After a daughter, previous sons are irrelevant to Tom’s future tree, which is why there are not more states in this model.

        • Chris Upshaw says:

          Shouldn’t that be s * T1 then, if its a parallel notation to sum of products datatype notation? Its certainly not the same operation as the middle ‘+’.

        • That’s cos I don’t know nothin bout notating no datatypes.

        • John Baez says:

          I found Anton’s trick very hard to understand at first, mainly because the variables and operations in his equations had not been explained (and I didn’t already know this trick). Like Greg, I found XJY’s comment here helpful. Even then, I had to hit myself over the head with a rock a few times before I really understood what was going on.

          I’ve spent a lot of time thinking about other aspects of Markov processes, but I never thought about this particular trick. It’s very nice, but I think I need to digest it and blend it with other things I know, like generating functions and—yes—recursively defined data types.

        • Anton,

          This is a really cool solution! Not only do you compute Lisa’s expected # of kids, you compute how many sons and daughters she can expect. I have never seen this concept of expressing the invariants of the tree of futures before. Do you have a good reference for learning more about this? Is it standard CS?

          Thanks for posting this.

        • Rob, sorry, I have no idea where I got the, er, idea.

          “Invariant” may be a misnomer; thinking about it further, I reckon the analogy with the loop invariants of CS is not so strong.

  3. Adam Bincer says:

    I may have misunderstood the problem but it seems to me that as soon as Tom or Lisa reach their objective they STOP. Then Tom can have 2 sons in a row and it is over. On the other hand if they have a daughter Lisa can get a son and they stop, Tom can never get two sons.

    • John Baez says:

      Wow, you assumed that Tom and Lisa are married, and that their plans affect each other’s activities!

      I never thought that: I was imagining two people at a bar, who obviously hate each other, each discussing their own separate plans. But now I see that there’s an ambiguity in the phrase “their plans for having children”. I’ll fix that!

    • John Baez says:

      Upon rereading what I wrote, I see there’s no real ambiguity in the puzzles as stated. One asks what will happen if Tom carries out his plan. The other asks what will happen if Lisa carries out her plan. There’s nothing about what will happen if both of them try to carry out their conflicting plans.

      Nonetheless I added some stuff to make it crystal clear that Tom and Lisa are not going to be having children together.

  4. jamievicary says:

    I deliberately haven’t worked this out formally, because it’s more fun to see if intuition leads to a right answer. Write their progeny as a string in D and S. It’s ‘easy’ for a string of length n to lack a SS substring, as it could have no Ss, or just one S, or just two Ss spaced at least one apart, etc. But to lack a DS substring is relatively ‘hard’: you have to have all the sons before all the daughters. So, holding out for two sons in a row will take longer than waiting for a daughter followed by a son.

    I guess the reason it’s a bit paradoxical is that for any two adjacent children, SS is just as likely as DS. I suppose the reason is that combinatorially, like-gendered children are indistinguishable. In reality this is not the case. They should just ask for “two children adjacent in age, both with the temperament to run a shop”!

    (By the way, I found this post cognitively difficult to write, since on parenting forums DD and DS often meen ‘darling son’ and ‘darling daughter’.)

    • John Baez says:

      Jamie wrote:

      I guess the reason it’s a bit paradoxical is that for any two adjacent children, SS is just as likely as DS.

      Right, that was supposed to make the problem cognitively difficult.

      (By the way, I found this post cognitively difficult to write, since on parenting forums DD and DS often meen ‘darling son’ and ‘darling daughter’.)

      I never knew! I hadn’t expected that to cause cognitive difficulties. Do SD and SS mean ‘stupid daughter’ and ‘stupid son’?

      (I would probably be banned from the forum for that joke.)

      • Tamfang says:

        or Silly or Sweet

      • Charles Jackson says:

        Well, you did make the problem cognitively difficult for me.

        I did #3 first. I thought P(SS) = P(DS) => Expected births to first SS is same as for DS. WRONG—but

        I did 2 relatively quickly with something like Anton’s approach above.

        Then I looked at the answers in the comments. Oh, oh. I thought about it for awhile and I think I see an easy explanation for the answer.

        Consider the outcomes with up to three children. Make a little truth table-like figure with all 8 possible sequences of combinations of boy and girl babies. See below. Notice that there are 4 occurrences of the sequence DS in the table—each of which is the first occurrence of DS in the sequence containing it. (capitalized in table below)

        Birth Order
        1 2 3
        d d d
        d D S
        D S d
        D S s
        s d d
        s D S
        s s d
        s s s

        Now, search for SS, but only the 3 that are the first occurence in time.

        d d d
        d d s
        d s d
        d S S
        s d d
        s d s
        S S d
        S S s

        The difference (only 3 SS versus 4 DS) arises from the second SS that is a subsequence of the SSS sequence
        d d d
        d d s
        d s d
        d s s
        s d d
        s d s
        s s d
        s S S

        So, if the parties were restricted to 3 or fewer babies, Lisa would have a 50% chance of getting DS, but Tom would only have a 3/8 chance of getting SS.

        Of course, if they both had three babies, Tom would have a 1/8 chance of getting SS twice, but Lisa would have zero chance of getting DS twice.

        At the birth of the second baby they each have a 25% chance of getting their desired outcome. On the third baby, Lisa would also have a 25% chance but Tom would only have a 12.5% chance.

        Lisa’s probability of terminating the process at 3, 4, or 5 is higher than the probability for Tom. This pushes up the expected number for him relative to her.

        Chuck
        PS Thanks for your blog. I only read some of the posts but always enjoy those I complete. No doubt if I had more time and patience I get even more enjoyment from it.

      • Jenny Meyer says:

        The DD and DS tags are just a convention for anonymizing your family members. The D can be heavily ironic in context.

        (The picture of the Duggars was enough to make this too cognitively difficult for me.)

  5. Michael Nelson says:

    I think I understand. If we think of this as a game, where Lisa needs to get the sequence DS and Tom needs to get the sequence SS, then Lisa will certainly have the advantage. As soon as a D shows up, Tom will lose. On the other hand, if a S shows up, Lisa can still win. So Lisa has a greater chance of winning this game.

    • John Baez says:

      I’m not assuming that Tom and Lisa are having children with each other: they are two separate people, each pursuing their own separate agenda with their own spouse, each assuming their spouse will knuckle under and go along with their insane plan.

      Nonetheless you can still think of it as a game, where we imagine a random stream of babies being produced and both Tom and Lisa saying when they, personally, would prefer the stream to stop.

      • Michael Nelson says:

        Yes, this is what I meant. You phrased it better for me. I think I have a better way to think about this now. The number of ways that Lisa can win at the nth spot is just n. For example:

        DDDDDS
        SDDDDS
        SSDDDS Lisa wins at 5th spot
        SSSDDS
        SSSSDS

        DDDDDDS
        SDDDDDS
        SSDDDDS
        SSSDDDS Lisa wins at 6th spot
        SSSSDDS
        SSSSSDS

        The number of ways that Tom can win at the nth spot involves the fibonacci numbers though. For example:

        DDDDSS
        SDDDSS
        DSDDSS Tom wins at 5th spot
        DDSDSS
        SDSDSS

        DDDDDSS
        SDDDDSS
        DSDDDSS
        DDSDDSS Tom wins at 6th spot
        SDSDDSS
        SDDSDSS
        DSDSDSS

        DDDDDDSS
        SDDDDDSS
        DSDDDDSS
        DDSDDDSS Add D just before SS in 6th spot wins
        SDSDDDSS
        SDDSDDSS
        DSDSDDSS

        plus Tom wins at 7th spot

        SDSDSDSS
        DDSDSDSS
        DSDDSDSS Replace the last S in 5th spot wins with DSS
        SDDDSDSS
        DDDDSDSS

        That’s pretty cool that the fibonacci numbers are involved.

  6. Dave Doty says:

    I worked it out like this. I am nagged by the possibility that there is a more elegant simple way to do it.

    Each is picking a string from the alphabet \{ s,d \}. Both have a list of “allowed” strings of length n that indicate they must keep going.

    Lisa omits from this list all strings with the substring sd, and Tom omits all strings with the substring ss. Already we can see that Lisa has fewer allowed strings than Tom, and will therefore wait a shorter time before stopping, because to remain in an allowed string, she can only transition once (from s to d), whereas Tom can transition between s and d an arbitrary number of times.

    Lisa’s allowed strings match the regular expression s^*d^*; e.g., for length 5, her 6 allowed strings are

    sssss, ssssd, sssdd, ssddd, sdddd, ddddd

    In general, Lisa has n+1 allowed strings of length n, so probability \frac{n+1}{2^n} that a given length n string will be allowed. If the string is s^*, then either of s or d is allowed next, whereas if it ends in a d, only a d is allowed next. So the probability that Lisa ends on length n is the probability that she does not end before (i.e., the length n-1 prefix is allowed) times the probability that the whole length n string is disallowed, conditioned on length n-1 prefix being allowed. This is

    \displaystyle{ \frac{1}{2^{n-1}} \cdot 0}

    (the probability the string is s^{n-1}, times probability 0 since she will not stop after s^{n-1}), plus

    \displaystyle{ \frac{n}{2^{n-1}} \cdot \frac{1}{2} }

    (the probability the string is s‘s followed by at least one d, times the probability that the next symbol is s).

    So Lisa’s probability of stopping after n children is \frac{n}{2^n}.

    Thus her expected stopping time is

    \displaystyle{ \sum_{n=2}^\infty n \cdot \frac{n}{2^n} = \sum_{n=2}^\infty \frac{n^2}{2^n} = \frac{11}{2} }

    Tom’s allowed strings omit the substring ss. We can count recursively how many strings of length n satisfy this, denoted by T_n. If the first symbol is d, then all allowed strings of length n-1 could follow, of which there are T_{n-1}. If the first symbol is s, then the next symbol must be d, and any allowed string of length n-2 could follow, of which there are T_{n-2}. So T_n = T_{n-1} + T_{n-2}, the n‘th Fibonacci number, which is

    \displaystyle{ \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^n \sqrt{5}} }

    So Tom’s probability of stopping after n children is the probability that the last three symbols are dss (if it were sss he would have stopped at the second s) the prefix of length n-3 is allowed, which is

    \displaystyle{ \frac{T_n}{2^n} = \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^{2n} \sqrt{5}} }

    Thus his expected stopping time is

    \displaystyle{ \sum_{n=2}^\infty n \cdot \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^{2n} \sqrt{5}} = \frac{19}{2} }

    • John Baez says:

      Wow, what a tour de force! You are not getting the officially approved correct answers, but the officially approved correct answers do involve Fibonacci numbers, at least in the most direct approach.

  7. Bruce Smith says:

    I carefully solved each puzzle before reading beyond it (in case of spoilers), so puzzle 3 was not very interesting! (I had thought of it while starting to work on puzzle 2, but didn’t have the benefit of your stating it was worthwhile to work on it first, so I didn’t do so.)

    Another mistake — I initially assumed Tom and Lisa were married and were discussing their joint plan for having kids! This leads to puzzle 4 — suppose they do marry (before having any kids) and agree to have kids until both their criteria are satisfied…

    • John Baez says:

      I think it’s too late for me to make Puzzle 3 into Puzzle 1 without causing massive confusion.

      I have added verbiage to the puzzle to make it clear that Tom and Lisa are not married and never will be.

      Nonetheless, Puzzle 4 is interesting, and will doubtless lead to an even larger expected family.

    • For that case I get seven expected children, again equally divided.

      Next question: For each scenario, what are the variances? Do the variance in daughters and the variance in sons add up to the variance in total children? I don’t know how to figure these.

      • Unless I made an error, I already did the variances – or, well, the standard deviations which are just the square roots of the variances – in my reply (first one). However, all the other contributions here are much more fleshed out and nice. My approach was really just trying a couple and then guessing. It seems like the results were right, however it’s nice to read in the others’ replies why they are right.

        To get the variance, if you have all the sub-probabilities, you just do:
        Probability: P=\sum_{n \in \mathbb{N}} p\left(n\right) = 1

        Expectation: E = \sum_{n \in \mathbb{N}} n p\left(n\right)

        Variance: \sigma^2 = \sum_{n \in \mathbb{N}} n^2 p\left(n\right) - E^2

        Standard Deviation: \sigma = \sqrt{\sigma^2}

        For some reason, in my original reply, the \LaTeX didn’t work right. Looks like the fixed version still isn’t right though. Hopefully the above works.

        • John Baez says:

          The LaTeX at the very end of this comment of yours didn’t work, and it was pretty cryptic, so I guessed you were trying to say this:

          \sigma^2 = \langle-^2\rangle

          This means ‘the square of the standard deviation is the expected value of the square of the quantity in question’. (The little dash is a standard symbol for ‘the quantity in question’: a blank to be filled in.) But this is only true for quantities whose mean is zero, which isn’t the case in this problem. So, I must have guessed your meaning incorrectly. I should have written

          \sigma^2 = \langle-^2\rangle - \langle - \rangle^2

          But probably you weren’t trying to use the ‘little dash’ notation, which gets a bit scary in formulas that also contain minus signs!

  8. Ilya Surdin says:

    Puzzle 1:
    suppose d is the expectation value we’re looking for.
    then d=0.5(d+1)+0.5(0.5*2+0.5(d+2)) [if a daughter is born first, we’re back to point 1 again, if a son is born first then if another son is born the value is 2, and if a daughter is born second we’re back to square 1].
    so we get d = 0.75d +1.5 -> d=6

    Puzzle 2:
    suppose e is the expectation value we’re looking for.
    e = 0.5(e+1) + 0.5f,

    where summand 1 is if a son is born, and summand 2 is if a daughter is born, we only need to get a son (ds, dds, ddds, all options are good)

    f = 2 [ f=0.51+0.5(f+1) ]

    so e = 0.5e + 0.5 +1 -> e=3.

    Puzzle 3:
    At first sight, I guessed they will be equal.

  9. Graham says:

    Here’s a solution for Tom’s case using generating functions. Let T be a random variable representing the number of children Tom has. Let f(s) = \sum p_i s^i be the generating function for T, where p_i = \Pr(T=i). The first few p_i are

    p_0 = p_1 = 0, p_2=1/4, p_3=1/8.

    For i \ge 4, the sequence must end DSS, and there must be no SS occurring in the first i-3. So

    p_4 = (1/8)(1-p_1),

    p_5 = (1/8)(1-p_1-p_2),

    and so on.

    From this it follows that

    p_i = p_{i-1} - (1/8)p_{i-3}

    for i \ge 4.

    Then by comparing f(s), sf(s), s^3f(s), it is possible to calculate that

    \displaystyle{ f(s) = \frac{-s^2}{s^2+2s-4}. }

    Then

    E(X) = f'(1) = 6

    and

    E(X(X-1)) =  f''(1) = 52

    from which \mathrm{var}(X) = 52 + 6 -6^2 = 22.

  10. “In one word he told me secret of success in mathematics: Generalize!” What if the sex ratio at birth is not 1:1? I’ll get right on that — later.

    • John Baez says:

      Puzzle 5. For what sex ratio at birth would Tom and Lisa have an equal expected number of children?

      (Obviously it needs to be more sons than daughters.)

    • Greg Egan says:

      John wrote:

      Puzzle 5. For what sex ratio at birth would Tom and Lisa have an equal expected number of children?

      The answer is golden!

      \displaystyle{ p_{son} = \frac{\sqrt{5}-1}{2} }

      or:

      \displaystyle{\frac{p_{son}}{p_{daughter}} = \frac{\sqrt{5}+1}{2} }

      To prove this (stealing from and generalising an answer by “XJY”, which is a slightly more coarse-grained version of Anton Sherwood’s approach), we can write the expectation values for the number of additional children that Tom and Lisa will each have after their latest child was a daughter or a son (who didn’t yet complete their target sequence) as:

      T_d = p_{son} (1+T_s) + (1-p_{son}) (1+T_d)
      T_s = p_{son} +(1-p_{son}) (1+T_d)
      L_d = p_{son} + (1-p_{son}) (1+L_d)
      L_s = p_{son} (1+L_s) + (1-p_{son})(1+L_d)

      These are solved by:

      \displaystyle{T_d = \frac{1+p_{son}}{p_{son}^2} }

      \displaystyle{T_s = \frac{1}{p_{son}^2} }

      \displaystyle{L_d = \frac{1}{p_{son}} }

      \displaystyle{L_s = \frac{1}{p_{son}(1-p_{son})} }

      But T_d and L_s are also the expectation values for the number of children each will have in total, because they have 0 out of 2 elements of their target sequence.

      So if we solve:

      L_s = T_d

      the positive solution for p_{son} is:

      \displaystyle{ p_{son} = \frac{\sqrt{5}-1}{2} }

      and

      L_s = T_d = 2+\sqrt{5}

  11. Bruce Smith says:

    It turns out these puzzles show up (for numbers 1 and 3 sought by Alice and Bob) in this (otherwise mostly unrelated) blog post about primes:

    https://rjlipton.wordpress.com/2016/03/26/bias-in-the-primes/

    • John Baez says:

      Yes, that’s how Greg heard about this question, though he read about it here:

      • Erica Klarreich, Mathematicians discover prime conspiracy, Quanta, 13 March 2016.

      Soundararajan was drawn to study consecutive primes after hearing a lecture at Stanford by the mathematician Tadashi Tokieda, of the University of Cambridge, in which he mentioned a counterintuitive property of coin-tossing: If Alice tosses a coin until she sees a head followed by a tail, and Bob tosses a coin until he sees two heads in a row, then on average, Alice will require four tosses while Bob will require six tosses (try this at home!), even though head-tail and head-head have an equal chance of appearing after two coin tosses.

      I decided to dramatize this using children instead of coin tosses.

      By the way, I wrote about the ‘prime conspiracy’ here:

      • John Baez, Weirdness in the primes, _The n-Category Café 15 March 2016.

      There’s a bit of math here that’s not in the Quanta article.

  12. Rob says:

    Nice Puzzle.

    from “Mathematical Plums” edited by Ross Honsberger, chap 5 some surprises in probability, “Suppose a fair coin is tossed repeatedly and an indefinitely long sequence of H’s and T’s is generated…. what a surprise to learn that it is twice as likely that the triple TTH will be encountered ahead of the triple THT…” I love surprises in probability, and I find that most things about probability surprise me! The chapter also talks about something else you may like if you haven’t seen it, “Efron’s Dice”.

    By the way, have you read this paper, http://www.emis.ams.org/journals/TAC/volumes/26/4/26-04.pdf, Commutative Monads as a Theory of Distributions. I gather Prof. Kock is developing the theory to study probability theory. I can’t really understand it, but you may find it interesting.

    • John Baez says:

      Probability theory is often counterintuitive to humans, which must have something to do with why humans mess up so often.

      I haven’t read that paper. I’m pretty good friends with Anders Koch’s son Joachim, who also does category theory related work. But this paper is by Anders. I find it pretty hard going, at first because I’ve never understood strengths as much as I’d like, even though I did help come up with the more conceptual definition of them given on the link. (The more common definition, which involves writing down some commutative diagrams, always bothered me.)

      • Rob says:

        okay here is my reply to your puzzle.

        Say the first child is a G. Then we are guarateed that GB will occur prior to to BB. (cause for BB to happen, we must first have had GB)

        Now say the first child is a B. Then either the second child is a B, in which case BB happens first, or it is a G, in which case, again, GB will happen before BB.

        So we see that GB is 3x more likely to occur in any given familiy than BB. Thus I would expect that the expected value of the second random varable is less than the expected value of the first. Hah! well probability is so amazing, I expect that I am wrong! Now I will read through the comments where I expect to find the right answer.

        Also, if you don’t understand that paper, I never will! But I think it is really interesting so I will keep reading it. BTW I think your notes on Cat Theory are great. Thanks to all your students for putting that together.

  13. arch1 says:

    Puzzle 3: Represent all possible birth sequences as an infinite binary tree (at the risk of scaring you we’ll pretend that childbearing doesn’t stop when the goal is reached). Yes, at each level of the tree starting with the 2nd, ¼ of the arcs are DS arcs and ¼ are SS arcs. But the symmetry breaks when we look at the correlation between adjacent levels: While an SS arc can immediately follow an SS arc, a DS arc can’t immediately follow a DS arc (as that would require the shared middle node to be both an S and a D).

    Upshot: Half of the SS arcs “hide behind” an immediate SS parent, but DS-DS repulsion prevents DS arcs from ever doing this. This makes a DS arc likelier than an SS arc to be the first arc of its kind on a path from the root (put differently, it causes DS arcs to more efficiently “cover” the tree as viewed from the root). So the expected number of levels before encountering a DS arc is less than for an SS arc.

    Greg and John, I find these probability paradoxes very instructive and great for my humility. I hope you keep them coming.

    • John Baez says:

      Nice answer! Yes, probability puzzles are great for ones humility—maybe the right verb is “humiliating”?

      There should be a book of probability puzzles, similar to Mark Levi’s excellent physics puzzle book Why Cats Land on Their Feet: And 76 Other Physical Paradoxes and Puzzles. But I don’t know it!

      If anyone here hasn’t tried Probability Puzzles (Part 1) and Probability Puzzles (Part 2), now is the time! They’re all about boys and girls, oddly enough. The first one is particularly devastating, or infuriating.

      • arch1 says:

        (chuckle) I actually tend to find them more invigorating than humiliating, partly for noble reasons but mostly I think because I can’t wait to spring them on others.

        Ironically the closest I’ve come to humiliation recently was last week when I, er, “judged” a high school science fair project which explained how cats can land on their feet using gauge theory.

        • cclingen says:

          High school?! Cats landing their feet?! Gauge theory?! Where can I learn more?

        • John Baez says:

          Hi, Charlie! It’s probably good to start here:

          • Wikipedia, Falling cat problem.

          but then go to this paper by a friend of mine who is an expert on classical mechanics at U. C. Santa Cruz:

          • Richard Montgomery, Gauge theory of the falling cat, in M. J. Enos, Dynamics and Control of Mechanical Systems, American Mathematical Society, pp. 193–218.


        • arch1 says:

          Nowhere as far as I know (certainly not me as I gleaned only a scant understanding). Maybe a paper will come out later; meanwhile I’d prefer to let the student pursue things in his own way.

      • Re Prob Puzzle books. I just bought “Fifty Challenging Problems in Probability”. It looks like it has some really cool stuff in it. And best of all it was cheap!

    • Greg Egan says:

      The counterintuitive aspects of real statistical phenomena might have put an innocent man in prison for 38 years:

      An Unusual Pattern

      Like the statisticians who discuss the case, I’m not claiming any certainty that Geen is innocent, but on the face of it the statistical basis of the prosecution’s argument appears alarmingly wrong-headed.

  14. pauljurczak says:

    I hate to be a party pooper, but using infinite series in the top answer is yet another reason why lies and statistics are often mentioned in the same sentence. Human female can only have a limited number of children, much smaller than 100, which is much smaller than infinity.

    This is in general a problem of using mathematics to model physical “reality”, which always requires certain assumptions resulting in departure from “reality”. In this case, the assumption is immortality or more specifically, unlimited childbearing capability.

    P.S. Don’t take this post too seriously ;-)

    • John Baez says:

      I won’t take it too seriously—just more seriously than you expected.

      Puzzle 7: How do the answers for Tom’s and Lisa’s expected number of children change if we impose a ‘cutoff’, saying that a woman can have no more than 10 children?

    • Charles Jackson says:

      Note that that there is about a 1% that Tom will have to have 24 or more children before the desired SS outcome occurs.

  15. Edon says:

    These processes can be seen as absorbing Markov chains. Let T be the block in the transition matrix that holds the transitions from transient states to other transient states. It is a basic property that (I - T) is invertible and that the (i,j) entry of M=(I - T)^{-1} gives the expected number of times the chain is in state j before it is absorbed, given that we start from state i . Summing the entries in the appropriate row yields the answers to the puzzles.

  16. For some reason there isn’t a reply button below that latest reply of you, John, but yeah, that was what I was going for, although indeed not with the ‘little dash’ notation, but that works too. With just one minus sign it’s not that bad. Thanks for the fix. There must have been more wrong with it than just \langle \cdot \rangle if it was so cryptic. I’m not sure what I typed anymore but while typing it that was the only part I didn’t know whether it’d work. The rest I was pretty sure of. But oh well. I thought \left{<} would work for \langle but you guessed that part right.

    • John Baez says:

      Kram wrote:

      For some reason there isn’t a reply button below that latest reply of you…

      Unfortunately if you tell this blog that you don’t want comments to get indented more than 4 times (because they become absurdly skinny), it implements this by eliminating the ‘Reply’ button after a comment that’s been indented 4 times.

      What you should do in this case is reply not to the comment but to the comment it’s commenting on! In fact it’s often wise to do this. This keeps the comments from getting too skinny. I can tell who is a really expert blog-commenter by whether they do this.

      I thought \left{<} would work for \langle but you guessed that part right.

      I’ve never seen \left{<} in LaTeX; I think LaTeX is pretty careful about the difference between the less than symbol < and the left angle bracket \langle.

      But there’s an extra problem with LaTeX in most blogs! In HTML, < is an escape symbol, so you to get a less than symbol in LaTeX you have to use the HTML symbol &lt; rather than <. It’s very bizarre to be using HTML commands inside LaTeX equations, but that’s how it works! That’s true not only for this rather brain-dead WordPress blog but also some others I use.

  17. Tom says:

    Puzzle 6: Why did John use the name of his wife for the female character in this drama?

  18. David Cinabro says:

    This one got in my head, and I had to try to solve it.

    First Puzzle 3. Two children SS, SD, DS, DD. Tom and Lisa both stop 1 out of 4. Three Children for Tom SDS, SDD, DSS, DSD, DDS, DDD. Tom stops 1 out of 6. Three Children for Lisa SSS, SSD, SDS, SDD, DDS, DDD. Lisa stops 2 out of 6. Clearly the expected number of children is different and Lisa will have a smaller number than Tom.

    For Tom’s expected number of children, he has 1/4 chance stopping at 2, 1/6 stopping at 3, 2/10 stopping at 4, 3/16 stopping at 5, 5/26 stopping at 6, etc. The stopping chance numerators are Fibonacci seeded by 1 and 1, and the denominators are Fibonacci seeded by 4 and 6. The expected number of children is then 2(1/4) + 3(1-1/4)1/6 + 4(1-1/4)(1-1/6)3/16+…. ie he stops at 2 with a probability of 1/4, at 3 with a probability of (1-1/4)*1/6, etc. Perhaps there is a clever way to write that, but I wrote a little program to tell me that it goes to 6.

    Lisa has 1/4 chance stopping at 2, 2/6 stopping at 3, 3/8 stopping at 4, etc. The stopping chance numerators are 1,2,3,etc. and the denominators at 4,6,8, etc. The same sort of calculation gives the expected number of children 21/4 + 3(1-1/4)2/6+4(1-1/4)(1-2/6)*3/8+… This one is certainly even simpler to work out in closed from , but again the program tells me that it sums to 4.

  19. Michael Nelson says:

    By the way, you can prove the classic result involving pascal’s triangle and the fibonacci numbers by partitioning Tom’s string of n children into these cases:

    Tom has a total of 3 sons
    Tom has a total of 4 sons

    For those who aren’t familiar, the relation between pascal’s triangle and the fibonacci numbers involves summing over diagonals, like in this image:

    In other words, the nth fibonacci number equals (n-1 choose 0) plus (n-2 choose 1) plus …

  20. While on the subject of what is essentially run theory, mathematician Peter Donnelly has given a TED talk on the subject of fooling juries with statistics. His talk is based around the infamous English criminal case of Sally Clark. To illuminate the issues he poses this problem:
    you toss an unbiased coin many times and count the number of tosses until you get the pattern ”HTH”. You then calculate the average. You repeat the experiment but this time you look for the pattern ”HTT”. The question is: ”Is the average number of trials required to get ”HTH” greater than, less than or equal to the average number of trials required to get ”HTT”? ” Donnelly has tried this out on a wide range of audiences including professional mathematicians and the audience not surprisingly says the number of trials were equal. The expected number of trials to get ”HTH” is 10 while the expected number of trials to get ”HTT” is 8.
    My paper ( $\url{http://www.gotohaggstrom.com/Fooling%20juries%20with%20statistics.pdf}$ ) explains the generating function proof of Donnelly’s claim. This paper also sets out the background to the Sally Clark case. A 2013 English Court of Appeal case has had the effect of banning Bayesian reasoning in court cases. This shows that the “real” world of the justice system can intersect in bizarre ways with probability theory.

  21. Puzzle 1.
    We are looking at infinite sequence of coin flips (the coin has two sides: S and D) and waiting for first occurrence of SS.
    There are essentially 3 different states:
    s0: current sequence ends with D or is empty (initial state)
    s1: current sequence ends with exactly one S
    s2: current sequence ends with SS (end state)

    Let ei = expected number of flips to get from si to s2.
    Then we have the following system of linear equations:
    e2 = 0
    e1 = (1/2)(1+e2) + (1/2)(1+e0)
    e0 = (1/2)(1+e0) + (1/2)(1+e1)

    Solving it gives the answer to the puzzle: e0 = 6.

    Puzzle 2.
    We just need to wait for the first daughter, then wait for the first son. Since expected number of trials until first success equals 1/p, where p is the probability of success, the answer is obviously 2+2=4.

    Puzzle 3.
    The intuition is, that Tom has to make a “step back” sometimes but not Lisa, therefore she accomplishes her goal sooner.

  22. Check out this interesting, related puzzle and discussion.

    https://www.klittlepage.com/2013/11/20/dynasty-meets-the-central-limit-theorem/

    I just came across it. It has some surprising conclusions.

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s