MATH4200: Modelling of business, industrial & everyday life problem

Assignment 1 – A sketch proof of the Optimal Stopping Theorem

Hesavan Silvapan. Student number: 302908

Introduction
Let's assume that we are trying to find the best restaurant possible out of a total of N restaurants to choose from. At each step, we can either stop and eat, or keep looking. If we stop, the reward is the food at the restaurant. If we keep looking, we take the risk of missing out on the current food. We want to get the biggest reward possible, that is, the best food! We cannot window-shop all N restaurants because we get too hungry after a while! So the question is: what strategy would give us the best chance to get the best reward?

The optimal stopping theorem
One strategy is to look at M-1 restaurants, then pick the best next one that come along. We can think of the M-1 restaurants as “data”, and if our database is large enough, then the one who top it must be very good overall! How big should M be compared to N? The optimal stopping theorem states that it should be 37%. This assignment attempts to explain to a layman why 37% is the magic number, through a counting argument. No mathematical backgrounds is required.

The explanation
Let's consider the case where N=4. Rank the restaurants from 1 (worst) to 4 (best). We bump into them in some random order, like 1324, 2134… There are 24 possible combinations like these. Now, we can consider the possible cases of M:

M = 1
If M = 1, it means we look at M-1 = 0 restaurants before hand, and just pick the best one, which means we just pick the first restaurant we see. Then we can get the best (4) restaurant only if we see the best restaurant at first go! So, the order of appearance of the restaurants which would make us win includes:

• 4123
• 4132
• 4213
• 4231
• 4312
• 4321

So there are 6 possible sequences in which we can “win”. The probability of this happening is, 6 out of 24, which is 25%.

M = 2
If M = 2, it means we look at M-1 = 1 restaurant first, then pick the next one that is better than this one. Then we can get the best restaurant if:

Case 1: we see the best restaurant immediately after seeing the first one:

• 1423
• 1432
• 2413
• 2431
• 3412
• 3421

Case 2: after seeing the first one, we see another one that is worse, and then we see the best restaurant

• 2143
• 3142
• 3241

Case 3: after seeing the first one, the next 2 restaurants are worse, and finally the last restaurant is the best

• 3214
• 3124

The probability of this happening: 11 out of 24: almost 50%!

M = 3
If M = 3, it means we look at M-1 = 2 restaurants first, then pick the next one that is better than these. Similarly, we work out that we would win if:

Case 1: after seeing the first 2, we see the best one next.

• 1243
• 1342
• 2143
• 2341
• 3142
• 3241

Case 2: after seeing the first 2, we see a worse one, and finally the best one.

• 1324
• 2134
• 3214
• 3124

The probability of this happening: 10 out of 24: almost as good as M = 2.

M = 4
If M = 4, it means we look at M-1 = 3 restaurants first, then pick the next one that is better than these. So we would win if we meet the best restaurant last:

• 1234
• 1324
• 2134
• 2314
• 3124
• 3214

The probability of this happening: 6 out of 24 = 25%

So here, for N = 4, we see that the best M is 2. For a bigger N, the same argument will show that the best M is 37% of N.

Reference: