Two Movies

You have a database with a countably infinite number of movies. Each movie has a rating that is uniformly distributed in and you want to find two movies such that the sum of their ratings is greater than . Your strategy for choosing the movies is as follows: you select one movie at a time, keeping only the movie with the highest rating so far. You stop when the sum of the ratings of the most recent movie selected and the movie with the highest rating of all previous movies is greater than .
Define an appropriate Markov chain and find the expected number of movies you will need to select.

Let be the value of the highest rating chosen after selections, without having terminated the process. Let’s also add a state to our Markov chain to denote when our sum exceeds , so our state space . If we define to be the expected hitting time of reaching starting from state , then our answer is . All we have to do is set up the first-step equations and solve for .

How can we set up these first-step equations? Let’s examine closely:

By law of iterated expectation:

If the next selection has a rating of , , , or , then is still equal to . If the next selection has a rating of , then . If the next selection has a rating of , then the sum of the ratings and exceeds , meaning .
Continuing on,

In general, the first-step equation is where is the state transitioned to after .

Setting up the rest of our first-step equations, we have

Solving this system of equations, we get .


If the movie ratings are instead uniformly distributed over , what is the expected number of movies you will need to select?

As before, let’s define as the maximum rating so far (unless the terminal state is reached), and as the rating of the next movie selected.

  1. Suppose .
    • No matter what is, their sum cannot exceed , so ; in fact, .
  2. Suppose .
    • If , then .
    • If , then .
    • If , then their sum does not exceed and .
    • Otherwise, and their sum exceeds so we reach the terminal state .
  3. Suppse .
    • If , then their sum does not exceed and .
    • Otherwise, and we reach the terminal state.

Using the above cases as a guide, let’s define our first-step equation as a piecewise function:

It’s reasonable to assume that is a continuous function, so and .

Let’s look at one of these functions. What is (when )?

Repeating the above for and we get the following first-step equations:

Solving for first,

Next, :

and should have the same value at the boundary, so , and we can solve for the constant and find .

Finally, :

Again, we can use the boundary and say , so .

This leads us to our final answer, .

A quick Monte Carlo simulation tells us we can be reasonably confident in our answer:

import numpy as np


def simulate() -> int:
    count: int = 0
    curr: float = 0.0
    while True:
        count += 1
        draw: float = np.random.uniform(low=0.0, high=5.0)
        if draw + curr > 7.5:
            return count
        curr = max(curr, draw)


n = 10000
results = [simulate() for _ in range(n)]
print(np.mean(results))
6.0322