Expected discount shop owner will have to shell out in a guessing game with customers

Question

This question is a bit of a corollary to this one: Generate a random permutation of the first $n$ numbers on the fly

I have some customers coming to my shop. I'll accept the first $n$ and then close the shop. I'll assign each customer an ID between $1$ and $n$. The customers know they're going to get an integer ID, but don't know what $n$ is. Before they're assigned their ID, they will be given a chance to guess it. If they get it right, they'll be given a $1\$$ discount on any purchase.

The customers are very smart and will maximize their chances of getting the discount. They also talk to each other and so know the previous ID's. I want to minimize the discount I end up shelling out.

It seems intuitive that the best strategy for assigning ID's is to do it in a random order. So, take the numbers $1$ to $n$ and put them in an array. Randomly permute that array using the Fisher Yates shuffle and assign the IDs based on successive indices of the array. If the customers knew what $n$ was, the first customer would guess anything from $1$ to $n$, the second one would rule out the ID of the first customer and so on, making the total discount I'd end up giving becoming on average:

$$d = \sum\limits_{i=1}^n\frac{1}{i}$$

But, what will $d$ become when they don't know $n$?

Answer 1

The total discount is just what you said given that the customers know $n$. Each customer should guess the smallest number not yet handed out. If $i$ numbers have been handed out and the rest are randomly ordered, the chance this number wins is $\frac 1{n-i}$. The discount you award is then $\sum_{i=1}^n \frac 1{n-i}=\sum_{i=1}^n\frac 1i=d$ because you are adding the same terms in the reverse order. The point is that each customer knows that his/her number is still in play. If the number is less than the highest given out, it is in play. If you have given out $1$ through $k$ and no more, $k+1$ must be in play because you have not closed up. The customer does not know the chance they will win because they don't know $n$, but they know this number is as good as they can do.

Answer 2

Up to a term that goes to $0$ as $n \to \infty$, the expected discount is still the same. Essentially, the customers most likely to get the discount can have a pretty good idea of $n$, so they'll still get the discount with about the same probability.

In particular, suppose that the customers use the following strategy: each one guesses a random unassigned ID between $1$ and the highest ID assigned so far. (If all IDs in that range have been assigned, the customer just gives up in frustration.)

I'm going to ignore the first $\sqrt n$ customers. For each of the other customers:

• With probability $\frac1k \le \frac1{\sqrt n}$, the $k^{\text{th}}$ customer will have the highest ID assigned so far, which is unguessable by this strategy.
• Otherwise, the $k^{\text{th}}$ customer will have at least a $\frac1{n-k+1}$ chance of guessing their ID (possibly better).

So these customers get an expected discount of at least $$ d' = \left(1 - \frac{1}{\sqrt n}\right) \sum_{i=1}^{n - \sqrt n} \frac1i. $$ Let's compare it to the original $d = \sum_{i=1}^n \frac1i \approx \ln n + \gamma$. This $d'$ loses out on the entirety of $\sum_{i=n-\sqrt n}^{n} \frac1i$, but that's asymptotically only $\ln n - \ln (n - \sqrt n) = O(\frac1{\sqrt n})$ as $n \to \infty$. For $i \le \frac n2$, $d'$ only gets $(1 - \frac1{\sqrt n})$ of the expected discount, which loses us $O(\frac{\ln n}{\sqrt n})$.

So $d' = d - O(\frac{\ln n}{\sqrt n})$, even with this suboptimal strategy.