Probability and Making Decision

The secretary problem: also called the matching or marriage problem.

• You will see $T$ items, one at a time, from a distribution of types $F(x)$.
• You want the maximum. After you pass, you cannot go back.
• $t$ is the slot you are in: $t=1,\ldots,T$.
• Strategy: skip a prefix, then take the next candidate who is better than everyone you have seen.
• For large $T$ the prefix is a fraction $1/e$ of the list: $$\frac{1}{e} \approx 0.368.$$

A Simple Example

Say I have a budget to consider $T=10$ candidates, and they have the following scores (which I do not know)

    1  7  4  5  3  8  10  3  0  11

I decide to screen 3 candidates before making a decision.

• My best candidate from the screening pool is 7
• Next is 5 –> dump
• Next is 3 –> dump
• Next is 8 –> accept

Probability and Decision - Strategy

What’s your best strategy?

• Turns out its insensitive to the choice of distribution.
• Although there is the random sample i.i.d. assumption lurking.
• You’ll not doubt get married between $18$ and $60$. Waiting $\frac{1}{e}$ along this sequence gets you to age $33$. Then, pick the next best person!

If you take the best so far at $t$

• $T$ is the length of the list. Ten candidates, $T=10$.
• $t$ is the slot you are looking at. In the example you accepted at $t=6$.
• Best so far at $t$ means better than the first $t-1$. Candidate 8, after a screen whose best was 7.
• The overall best is equally likely to sit in any of the $T$ positions.
• Overall best implies best of the first $t$, so $$P(\text{overall best}\mid \text{best so far at }t) = \frac{P(\text{overall best})}{P(\text{best so far at }t)} = \frac{1/T}{1/t} = \frac{t}{T}.$$
• Take that candidate and you win with probability $t/T$. In the example, $6/10$.
• If $t$ is the overall best, it is automatically the best of the first $t$. The earlier ranks do not change the ratio.
• Being the best of the first $t$ has probability $1/t$.

Success under the $r$-rule

• Reject the first $r$. Then take the first later candidate who is the best so far.
• You win only if you take the overall best. Put that person at slot $a$. Probability $1/T$.
• You never take them if $a\le r$: still screening.
• If $a>r$ you still miss them whenever someone in $r+1,\ldots,a-1$ was the best so far. That happens when the best of the first $a-1$ sits after $r$. You would have taken that person and gone home.

Success under the $r$-rule

• So you need the best of the first $a-1$ to sit in the skipped prefix. Those $a-1$ ranks are in random order, so their max is equally likely in any of those $a-1$ slots: $$\frac{r}{a-1}.$$
• In the example, $r=3$. If the overall best is at $a=6$, the first five are $1,7,4,5,3$. Their max is $7$, in the prefix. Chance $3/5$.
• Denominator $a-1$, not $a$: slot $a$ is already the overall best. The comparison is among the others. $$P(\text{success}) = \frac{1}{T}\sum_{a=r+1}^{T}\frac{r}{a-1} = \frac{r}{T}\sum_{b=r}^{T-1}\frac{1}{b}.$$
• Need $r\ge 1$. If $r=0$ you take the first candidate and win with probability $1/T$.
• If nobody after $r$ is the best so far, you take the last one. That path never wins.

$1/e$ in a sample of $1000$

The peak is near $T/e$ and height $1/e$ (Monte Carlo, so the top wiggles).

• Average quality, not shown, peaks much earlier.
• Maximizing the chance of the absolute best is not the same as maximizing expected rank.

Decision Trees

Catastrophe Modeling

You live in a house that is somewhat prone to mud slides.

• Each rainy season there is a 1% chance of a mud slide occurring.
• You estimate that a mud slide would do $1 million in damage.
• You have the option of building a retaining wall that would help reduce the chance of a devastating mud slide. The wall costs $40,000 to build, and if the slide occurs, the wall will hold with a 95% probability.
• You also have the option of a Geologist’s opinion.

Should you build the wall? Should you use the Geologist’s Test and Bayes Rule?

Decision Tree Setup

Let’s formally solve this as follows:

• Build a decision tree.
• The tree will list the probabilities at each node. It will also list any costs there are you going down a particular branch.
• Finally, it will list the expected cost of going down each branch, so we can see which one has the better risk/reward characteristics.

There’s also the possibility of a further test to see if the wall will hold.

Decision Tree

Testing Option

Let’s include the testing option

• You also have the option of having a test done to determine whether or not a slide will occur in your location.
• The test costs $3000 and has the following accuracies. $$P(T \mid \text{Slide}) = 0.90 \quad \text{and} \quad P(\bar{T} \mid \text{No Slide}) = 0.85$$

If you choose the test, then should you build the wall?

Bayes Rule for Testing

Bayes Rule is as follows:

• The initial prior probabilities are $$P(\text{Slide}) = 0.01 \quad \text{and} \quad P(\text{No Slide}) = 0.99$$
• Therefore $$\begin{align*} P(T) &= P(T \mid \text{Slide}) P(\text{Slide}) + P(T \mid \text{No Slide}) P(\text{No Slide}) \\ P(T)&= 0.90 \times 0.01 + 0.15 \times 0.99 = 0.1575 \end{align*}$$

We’ll use this to find our optimal course of action.

Bayes Probabilities - Positive Test

The Bayes probability given a positive test is $$\begin{align*} P(\text{Slide} \mid T) &= \frac{P(T \mid \text{Slide}) P(\text{Slide})}{P(T)} \\ &= \frac{0.90 \times 0.01}{0.1575} = 0.0571 \end{align*}$$

Bayes Probabilities - Negative Test

The Bayes probability given a negative test is $$\begin{align*} P(\text{Slide} \mid \bar{T}) &= \frac{P(\bar{T} \mid \text{Slide}) P(\text{Slide})}{P(\bar{T})} \\ &= \frac{0.1 \times 0.01}{0.8425} \\ &=0.001187 \end{align*}$$

Compare this to the initial base rate of a $1$% chance of having a mud slide.

Probability Lose Everything - Without Testing

You build the wall without testing, what’s the probability that you lose everything?

With the given situation, there is one path (or sequence of events and decisions) that leads to losing everything:

1. Build without testing (given)
2. Slide ($0.01$)
3. Doesn’t hold ($0.05$)

$$P(\text{losing everything} \mid \text{build w/o testing}) = 0.01 \times 0.05 = 0.0005$$

Probability Lose Everything - With Testing

You choose the test, what’s the probability that you’ll lose everything?

There are two paths that lead to losing everything:

1. First Path: There are three things that have to happen to lose everything Test +ve ($P=0.1575$), Build, Slide ($P= 0.0571$), Doesn’t Hold ($P=0.05$)
2. Second Path: Now you lose everything if Test -ve ($P=0.8425$), Don’t Build, Slide given negative ($P=0.001187$)

Conditional Probabilities

For the first path $$P(\text{first path}) = 0.1575 \times 0.0571 \times 0.05 = 0.00045$$

For the second path $$P(\text{second path}) = 0.8425 \times 0.001187 = 0.00101$$

Hence putting it all together $$P(\text{losing everything} \mid \text{testing}) = 0.00045 + 0.00101 = 0.00146$$

Risk and Reward

Risk-Return Trade-off

Expected Cost: Fee + Build + Loss

Expected cost: $3 + 40\times 0.1575+ 1000\times 0.00146$ or $10,760

What do you choose?