2
$\begingroup$

First:

Assume Earth's population is 8,037,860,611 and they have ID numbers 1 through 8,037,860,611

You make a set of cards numbered 1 through 8,037,860,611

A robot goes to each person in turn and shows them a card at random (cards get replaced)

If anyone is shown the number that matches their ID, I will GAIN $8,037,860,611 (one time only)

Second:

You pick a population size n, and these people get new ID numbers 1 through n

You make a set of cards numbered 1 through n

This time the robot gives each person a card, such that everyone has a unique card

If anyone has the card that matches their ID number, I will LOSE $8,037,860,611 (one time only)

The Question:

Assume your goal is to make me break even as much as is possible after doing these two things. What population size, n, do you choose and what is my expected value to the nearest cent?

You can have a perfect understanding of the formulas involved and still get the wrong answer. This question involves big numbers and high precision... something typical calculators have trouble with. You might have to additionally prove your methods or calculation tool don't run into this pitfall

$\endgroup$

2 Answers 2

11
$\begingroup$

Let $N=8037860611$ be the population of the Earth. Analysis of the first game:

By complementary counting, the probability of winning is $p_1=1-\left(1-\frac{1}{N}\right)^N$. Your expected winnings is hence $E_1=Np_1$. Taking a series expansion for $N\to\infty$: $$E_1=\frac{e-1}{e}N+\frac{1}{2e}+\mathcal{O}(N^{-1})=$5,080,896,941.40$$ Since $N^{-1}\ll0.01$, we ignore all higher order terms.

Analysis of the second game:

You win if the resulting permutation is a derangement on $n$ elements, which occurs $p_2=\frac{!n}{n!}=\frac{1}{n!}\left[\frac{n!}{e}\right]$ amount of the time, where $[x]$ is the nearest integer function. The magnitude of your expected losing is hence $E_2=N(1-p_2)$.

Solution:

Unlike the first game, the expectation of the second game is an easy computation to do, so we can manually search through values of $E_2$ for different values of $n$ to see which is closest to $E_1$. It turns out that the minimal absolute difference is achieved at $\boxed{n=13}$, in which case you expect to gain $E_1-E_2=\boxed{$0.10}$ on average.

$\endgroup$
6
  • $\begingroup$ Seems correct, although I'm not sure why OP gave warning about big numbers and precision. $\endgroup$
    – justhalf
    Commented Jun 10, 2023 at 19:35
  • 2
    $\begingroup$ @justhalf I think it's because if you try to just compute $\left(1-\frac{1}{N}\right)^N$ for very large $N$ directly, your calculator won't do it $\endgroup$
    – DanDan面
    Commented Jun 11, 2023 at 7:08
  • $\begingroup$ Even Mathematica 13.2 won't give a numerical value for it in a reasonable amount of time. $\endgroup$
    – DanDan面
    Commented Jun 11, 2023 at 7:12
  • $\begingroup$ That's one way to see it, although I'm not fully sure yet, because OP uses the wording "you can have a perfect understanding of the formulas involved and still get the wrong answer", which makes me feels like there should be some trickery/pitfalls (inability to calculate is not a pitfall. A pitfall means something that looks correct but actually is wrong, if you can't calculate it, it certainly doesn't look correct) $\endgroup$
    – justhalf
    Commented Jun 11, 2023 at 8:23
  • $\begingroup$ @DanDan0101 Could you double check E1 for me? I feel like we're in agreement but my dollar value isn't quite what yours is. $\endgroup$
    – Skosh
    Commented Jun 11, 2023 at 11:02
8
$\begingroup$

@DanDan0101 calculates the value N were the expected gain is as close to \$0 as possible. I would interprete the goal to 'break even as much as possible' as meaning one should maximize the probability of gaining exactly \$0 and I will provide a solution for that.

Winning exactly \$0 can happen in two ways, either I win in the first part and lose in the second or I don't get anything in either step. Using DanDan0101' computation, the probability to win in the first game is $5080896942.57/8037860611=63.21\%$, in particular it is greater than $50\%$.

As the probabilities of the two steps are independent, this means I can maximize the chance of getting exactly \$0 if I lose the second game with $100\%$ probability which gives a combined probability of $63.21\%$. Now I can achieve a guaranteed loss in the second game by picking $N=1$.

With this strategy the expected average return is a lossof a few billion dollars but this maximizes the chance to get exactly \$0 which will happen almost two times out of three.

$\endgroup$
1
  • 1
    $\begingroup$ This certainly isn't what I intended, but you're right that n=1 does a better job in getting me to walk away with exactly 0 dollars. When I said "make me break even as much as is possible" perhaps I should have said "get my expected value as close to 0 as is possible" $\endgroup$
    – Skosh
    Commented Jun 11, 2023 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.