Bizarre vending machine and probability

Probability Level pending

Suppose that you are playing with your favorite toy vending machine which accepts only 1 dollar coins. It contains 100 unique items that you wish to collect. Currently, you possess $n$ (different) items. You want to play until you obtain a new $(n+1)^{th}$ item. The machine has, however, a few very peculiar properties.

First, the probability to obtain a new item if a coin is inserted (by which we mean an item that you currently do not have) is given as: $\frac{100-n}{100}$ . Second, the machine allows introducing extra coins before turning the lever, improving your chances to get a new item as: $\frac{100-n+c}{100}$ , where c denotes the extra coins inserted. Consider 2 strategies:

(I) Old school: insert one coin, turn the lever and hope for a new item. Rinse and repeat if no new item is obtained.

(II) Insert enough coins to be guaranteed to get a new item and turn the lever.

For what values of n is the strategy (II) (strictly) better than (I)?

Credit to the mini game in Danganronpa Trigger Happy Havoc for inspiring this problem.

Always! Never! n>1 n>50 n>25

n \geq \left\lfloor \frac{100}{\sqrt{2}} \right\rfloor

n>75

1 solution

Patrick Bourg
Jun 18, 2018

Let us start with strategy (II) as this is the easiest. To be guaranteed to obtain a new item, we need to insert c=n extra coins; that is n+1 coins in total.

Now, for strategy (II) : we continue to try our luck until a first success ( i.e. obtaining a new item) is achieved. The probability distribution therefore follows a typical Negative binomial distribution given as: $P(X=x | r, p) = \binom{x-1}{r-1}p^r (1-p)^{x-r}$ with X denoting the attempt ( also called trial) at which the rth success occurs and p is the probability of success. In our case of course r=1.

We wish to know how many attempts it will take on average to get our first success. This is just the expectation value of the distribution which is: $E[X] = \sum_{x=r}^{\infty} P(X=x | r, p) = \frac{r}{p}$

Thus, in our case, it will take (and therefore cost): $\boldsymbol{\frac{100}{100-n}}$ coins.

But now, the turning points of these two strategies occur whenever: $n+1 = \frac{100}{100-n} \Rightarrow n = 0 \ \ or \ \ 99$

which is to say, it is never worth to employ strategy (II), as required.

Bizarre vending machine and probability

1 solution

0 pending reports