Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Solution to the optimal stopping problem

      1 September, 1997
      September 1997

      The probability of choosing the best partner when you look at M-1 out of N potential partners before starting to choose one will depend on M and N. We write P(M,N) to be the probability.

      For any value of N, this probability increases as M does, up to a largest value, and then falls again. P(1,N) and P(N,N) will always be 1/N because these two strategies, picking the first or last potential partner respectively, leave you no choice: it's just like picking one at random. Our aim is to find when P(M,N) is largest.

      Suppose that you have collected the information from M-1 potential partners and are considering the Kth in sequence.

      Since the potential partners come along in a random order, the chance that this one is the best is 1/N. But you only consider this potential partner if the highest ranking potential partner that you've seen so far was among the first M-1 of the K-1 that you have rejected (otherwise you wouldn't be looking at this potential partner at all). This happens with the following probability:

      (M-1)/(K-1)

      So the overall chance of achieving your aim of finding the best potential partner this time is:

      (M-1)/(N*(K-1))
      Diagram

      But K can take any of the values in the range from M to N, so we can write:

      P(M,N) = Sum(K=M..N,(M-1)/(N*(K-1))) = ((M-1)/N)*Sum(K=M..N,1/(K-1)

      The best value of M will be the one which satisfies:

      P(M-1,N) < P(M,N) > P(M+1,N)

      (If you want to be very awkward, you could ask what happens if there are two "best" values of M, with one of those strict inequality signs replaced by a partial inequality. It turns out that the only time when equality is possible is when N=2, which is not very interesting anyway.)

      1/M+1/(M+1)+...+1/(N-1) < 1 < 1/(M-1)+1/M+...+1/(N-1)

      We can use these inequalities to find M for any N. Try it! Fill in the blanks below:

      1/M + 1/(M+1)+...+1/(N-1) < 1 < 1/(M-1)+1/M+...+1/(N-1) and table N/M for values of N from 3 to 20

      [Answers]

      The fraction of the potential partners that you see M/N is tending to a limit as N becomes large. There is a sum in the calculation of P(M,N) which appears in other situations in mathematics too:

      Sum(K=1..L,1/K) = ln(L)+C

      Using this equation we can calculate an approximation for P(M,N) as follows:

      P(M,N) =~ (M-1)/(N-1)*ln((N-1)/(M-2))

      For big N, we can make it even more simple:

      P(M,N) =~ (M/N)ln(N/M)

      In order to find the best value of M we have to apply the approximation to the conditions that we derived before:

      ln(N/M) =~ 1, M/N ~= 1/e

      1/e is about 0.368. This result can be expressed simply in the following "37%" rule:

      37% rule

      Look at a fraction 1/e of the potential partners before making your choice and you'll have a 1/e chance of finding the best one!

      Further reading:

      For more information see the article "Mathematics, marriage and finding somewhere to eat" elsewhere in this issue.


      Answers to problems:

      Solution table

      [Back to questions]

      • Log in or register to post comments

      Anonymous

      26 April 2016

      Permalink
      Comment

      Many thanks for explaining why, after 45* years of dating, I still can't find a lasting match. With your permission I'd like to copy the article, enlarge the raw math sections, mount and frame it. There's a perfect spot on the wall next to my curio cabinet filled with souvenirs from a lifetime of dating duds.

      *First date at age 18. Am 63 yrs old now. Never been married, never cohabitated. Normal, pleasant, sensible, good career, well traveled, intelligent, average looks, many interests but not manic about any of them (eg no collections, no cats running wild around the house). Sort of the reliable older sister type but not stodgy.

      • Log in or register to post comments

      roccon

      20 February 2021

      In reply to Motivational Poster by Anonymous

      Permalink
      Comment

      very amusing sir, love your comment haha.

      best wish if that is true

      • Log in or register to post comments

      nil

      18 December 2019

      Permalink
      Comment

      think there is a typo in the formula #5: P(M-1,N) < P(M,N) < P(M+1,N), should have been P(M-1,N) < P(M,N) & P(M,N) > P(M+1,N)

      • Log in or register to post comments

      derek

      10 August 2023

      In reply to typo by nil

      Permalink
      Comment

      Ah! I did wonder.

      • Log in or register to post comments

      Elimelech

      30 September 2022

      Permalink
      Comment

      How big does N have to be for this approximation to hold?

      • Log in or register to post comments
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms