# Kissing the frog: A mathematician's guide to mating

September 2008

### The 37% rule

The first question we need to answer is, why is the best strategy to throw back some number of frogs, and then kiss the next one that is better than all those you've seen so far? Well, what else could you do? All you know about the frogs that you've seen is how good they are relative to each other, which you can see from the numbers on their backs. When the first frog hops out, you have absolutely no information (the number on its back tells you nothing). You could kiss it, but there's only a 1 in 100 chance that it's really the handsome prince. So you'd be better off waiting until you've seen a few more frogs ... and that's the strategy!

Let's make things a little more general. If there are frogs in the pond, you will kick back the first frogs, and then kiss the next frog that has a higher number than all those you have seen so far. We have to work out what the best choice of is. To do that, we have to work out what your chances are of kissing the right frog, depending on where he appears in the sequence:

If the handsome prince is one of the first frogs, disaster, you'll kick him back in the pond.

If he is the th frog, success, you'll kiss him.

If he is the th frog, you'll kiss him, unless the th frog had the largest number of all the previous frogs. This unfortunate arrangement of frogs, which means that you'll kiss the th frog, not the handsome prince, only occurs in of the possible ways of arranging the first frogs. (There are just as many arrangements that have the largest numbered frog in the last position, as there are arrangements that have the largest numbered frog in any other position.) You'll kiss the right frog in of the possible cases.

If he is the th frog, you'll kiss him, unless the th or th frog had the largest number of the previous frogs. This only occurs in of the possible ways of arranging the first frogs. You'll kiss the right frog in of the possible cases.

...

And so on, until

...

If he is the th frog, you'll kiss him, unless the th, th, th,…or th frog had the largest number of the previous frogs. This only occurs in of the possible ways of arranging the first frogs. You'll kiss the right frog in of the possible cases.

Now, each of these possible positions of the handsome prince occurs in of the possible arrangements of the frogs, so your probability of winning is      For a given total number of frogs , we want to maximise your probability of kissing the handsome prince, , so we want starting with the first inequality means that    Cancelling the factor of gives    Now multiply out the first term of the top line to give    Take the right hand side over to the left to give and therefore We can go through the same calculation for (try it!), and find that so that, finally, we need We can now work out what you should use for various numbers of frogs in the pond (values of ). If there are only four frogs, we can see that so , and you should kick back the first frog, and kiss the next one that is better. If there are only five frogs, we can see that so , and you should kick back the first two frogs, and kiss the next one that is better. We could continue doing this by hand, but it gets very tedious. Instead, let's define and ask a computer to plot this function for us. For 100 frogs ( ), we can see below that you should choose . For 1000 frogs ( ), you should choose . Let's plot the value of that you should choose as a function of . As gets bigger, we can see that the proportion of frogs that you should kick back before thinking about kissing asymptotes to about . But why? Can we be more precise? Can we estimate the size of the function when is large?

Have a look at the graph drawn below. The area of the shaded blocks is . The curve drawn through the top left hand corners of the blocks is . We can see that the area under the curve is less than the area of the blocks, so But so Now look at the next graph. In this case, we can see that the area under the blocks (excluding the first block) is less than that under the curve, so Putting this together, we can see that      However, we are trying to find so that When and are large, , so we need to choose with But how often does this net you the handsome prince? We found a while ago that the probability of kissing the right frog is So the 37% rule wins the prince 37% of the time, whether there are a hundred, a thousand or a million frogs in the pond. Mind you, it might take a while to kiss 37% of a million frogs. There's another thing to think about in our model!