Kissing the frog: A mathematician's guide to matingIssue 48
Finding the Decision Numbers
As discussed in the main article, if the frogs are randomly numbered between 0 and 1, with the prince having the highest number, there is a sequence of decision numbers associated with the best strategy for choosing the top frog. Since we're meant to be doing some maths, we need some notation. We'll consider the general case with frogs, and let the number on the th frog be , . In addition, we'll try to find an increasing sequence of decision numbers, , , such that we kiss the th frog if it has the largest number seen so far and . In other words, to think about kissing the last frog we need , the next to last frog, , and so on. The reasons for this back to front numbering of the decision numbers should become clear below.
Let's assume that the th frog has the largest number so far on its back, , which we'll write as just to make things look nicer on the page. There are therefore frogs still to come out of the pond. If we kiss the frog, the probability that he's the handsome prince is equal to the probability that the remaining frogs have numbers less than , which is . That's the easy part of the calculation. The next bit is rather more tricky, but basically just involves counting (or combinatorics as it's rather grandly called by mathematicians).
If we don't kiss the frog, but choose the next one with number larger than , we can work out the probability that we kiss the prince by considering the situation when there are exactly frogs remaining that have numbers higher than the current frog's, , and adding up our answers for all possible values of . The probability that there are exactly frogs remaining that are numbered higher than is equal to times the number of different ways that we can choose frogs from the final , which is
What happens as k gets large?
We can see from the graphs in the main article that as , but how fast does this happen? In order to do this, we need to find the positive solution of equation (1) when is large. You could have a think about how you might do this before reading on, but I'll warn you that it's not easy. The summed part of equation (1) looks like a binomial series, except for the factor of multiplying the terms. However, if we differentiate the series, this goes away. This suggests that we can write the equation as an integral of a binomial series, and a little experimentation shows that equation (1) is equivalent to