a riddle related to American-style options

I saw a fun riddle this week. To get you in the right mindset before sharing it I’ll introduce the so-called secretary problem. I first came across this concept when I was a trainee at SIG from John Allen Paulos’ Innumeracy in the context of choosing a mate.

From Wikipedia:

The basic form of the problem is the following: imagine an administrator who wants to hire the best secretary out of n rankable applicants for a position. The applicants are interviewed one by one in random order. A decision about each particular applicant is to be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator gains information sufficient to rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants.

The question is about the optimal strategy (stopping rule) to maximize the probability of selecting the best applicant. If the decision can be deferred to the end, this can be solved by the simple maximum selection algorithm of tracking the running maximum (and who achieved it), and selecting the overall maximum at the end. The difficulty is that the decision must be made immediately.

The shortest rigorous proof known so far is provided by the odds algorithm. It implies that the optimal win probability is always at least 1/e or about 37%

The reason the secretary problem has received so much attention is that it’s the optimal policy for the problem, the stopping rule is simple and selects the single best candidate about 37% of the time, irrespective of whether there are 100 or 100 million applicants.

Key Insights

[These are a mix of my thoughts and Llama 3.1, the LLM you can chat with from Whatsapp]

• 37% provides sufficient information about the distribution of quality.
• Maximizes probability of selecting the best option.
• Balances exploration and exploitation(this should remind you of the multi-armed bandit problem — a problem so diabolical that the Allies considered “dropping” it on German scientists as the ultimate nerdsnipe — to distract them from the more urgent matter of developing weapons. See my notes from Algorithms To Live By author Brian Christian)

Real-World Applications

• Job Searching: Interview 37% of candidates before making an offer.
• Dating: Meet 37% of potential partners before committing.
• Shopping: Research 37% of options before purchasing.
• Recruitment: Screen 37% of applicants before inviting for interviews.

Assumptions

• Random arrival: Options arrive randomly and independently.
• No recall: Previously rejected options cannot be revisited.
• No additional information: No new information becomes available after observing an option.

Limitations

• Small sample size: With few options, the 37% Rule may not provide accurate results.
• Non-uniform distribution: If options are not uniformly distributed (e.g., clustered), the rule may fail.
• Correlated options: If options are correlated (e.g., similar), the rule may not account for this.

Practical Considerations

• Difficulty in estimating 37%: Real-world applications may make it challenging to determine the exact 37% mark.
• Time constraints: The rule assumes unlimited time for observation and decision-making.
• Multiple criteria: The rule focuses on a single criterion; real-world decisions often involve multiple factors.

Contextual Limitations

• Irreversible decisions: The rule may not apply to irreversible decisions (e.g., marriage).
• High-stakes decisions: The rule may not suffice for critical decisions (e.g., life-or-death).
• Dynamic environments: The rule assumes a static environment; changing circumstances may require adjustments.

Application to financial options

With that background, you can see how American-style options are a specific instance of “optimal stopping time problems”. That’s because they can be exercised any time before expiration, unlike European options, which can only be exercised at expiration. The holder of the option must decide the best time to exercise, if at all, to maximize their payoff.

This is why American-style options are priced by simulations such as tree methods while European-style options have closed-form equations.

In the simulations, the value of the option is computed by looking at the value at the next time step (i.e., whether to exercise now or wait). A backward induction process unravels from the expiration date back to the present. The model calculates the optimal decision at each point in time based on the payoff of immediate exercise versus the expected value of holding the option.

With ALL that said, you are ready for the riddle!

Flip 100 coins, labeled 1 through 100.

Alice checks the coins in order (1, 2, 3, …) while Bob checks the odd-labeled coins, then the even-labeled ones (so 1, 3, 5, …, 99, 2, 4, 6, …)

Who is more likely to see two heads first?

• Alice
• Bob
• Equally likely

The riddle is neat because it works the same muscles as pricing an option. In fact, the riddle doesn’t even require math!

🔓See my reasoning and the original thread

Welcome to 2024…

The cost to learn is COLLAPSING if your eyes are open. Culturally I can sense (and anticipate much more) hand-wringing over what this means for society but right now I cannot emphasize enough how you should at least be taking advantage of all the consumer surplus LLMs are dumping in your lap. Earlier this week I mentioned that I screenshotted a spreadsheet of futures data and asked ChatGPT to write the formulas I’d need to arrange it the way I wanted. It spelled out exactly what helper column I needed and where to place all the formulas. It even stepped through the method so I can understand why its solution works.

Now consider that riddle.

• I prompted ChatGPT to give me the Python code to simulate the question many times to so I could validate my answer.
• I ran the code in Google Colab (cloud-based Jupyter notebook)

This entire process takes seconds not minutes.

Here are the steps you follow upon seeing the riddle on twitter:

1. open 2 tabs — ChatGPT & Google Colab
2. ctrl-c from twitter
3. ctrl-v into ChatGPT
4. type “what code that simulates this”
5. ctrl-c the response
6. ctrl-v into Google Colab
7. ctrl-enter to run the script

[And yes I use a PC…loving my new Surface laptop btw]

In 5 years, an AI agent implanted in your reading glasses will know you wanted to do that when you scrolled over the tweet and a tooltip will simply be projected over the tweet with the simulation results.

Just kidding.

Twitter will be gone by then.

If interested here’s my Google Colab link:

🔗coin-checking script.ipynb

[Not to get into the weeds but I had to have a couple back-and-forths with the LLM because it made the mistake of thinking that the position that the head is found in determines if Alice or Bob won but it’s actually which ordinal observation that determines the winner. The process took more like 5 minutes as I had to prompt a specific debug and explanation. It doesn’t take away from the point — we are talking about orders of magnitude decreases in the time to code up this simulation for someone whose coding skills are as soft as mine.]