Odds of a number being the smallest number not picked?

Question

Have a game where there are $N$ players choosing some $n\in\mathbb N$, and the one who picked the lowest number no one else picked wins. Now, lets have a scenario where all players pick uniformly randomly a number from $1$ to $N$.

What are the odds that $n$ will be picked and win?
(Talking about numbers, not players as each player is equally likely to win in this scenario)

Below are my observations so far.

---

Odds of no one winning are $$ \frac{\text{$f(N)$}}{N^N}$$

Where $f(N)=0, 2, 3, 40, 205\dots$ for $N=1, 2,3,4,5\dots$ players and is defined here: $A231797$

Now, how do we find $P(N,n)=?$ ;
The odds of number $n$ winning among $N$ players who each pick some $n$ randomly from $1$ to $N$?

One trivial thing is that $P(N,n+1)\le P(N,n),\space N,n\in\mathbb N, n \le N$
(Lower numbers win more often than larger)

---

We can write $P(N,n)=\frac{p(N,n)}{N^N}$, then I've found so far:

If $N<2$, then $p(N,1)=1$, else

$$p(N,1)= N(N-1)^{(N-1)}$$

If $N \lt 3$, then $p(N,2)= 0$, else

$$p(N,2)= p(N,1)\times \left( 1- \left(\frac{N-2}{N-1}\right)^{N-2} \right) $$

If $N \lt 3$, then $p(N,3)= 0$, else it equals $6, 36, 440, 6630, 117852\dots$ for $n=3,4,5,6,7\dots$

These so far are based on computed results:

$p(1,n)= 1$

$p(2,n) = 2, 0 $

$p(3,n) = 12, 6, 6 $

$p(4,n) = 108, 60, 36, 12 $

$p(5,n) = 1280, 740, 440, 260, 200 $

$p(6,n) = 18750, 11070, 6630, 3990, 2430, 1230 $

$p(7,n) = 326592, 195342, 117852, 71442, 43512, 26502, 17892 $

I've stopped at this point since I can't extract a formula for $p(N,3)$ already.

---

How would one mathematically solve this and find a closed expression for $P(N,n) ?$

Answer 1

Let $X_n$ be the number of players choosing $n$. Then

$$ (X_1, X_2, \ldots, X_N) \sim \text{Multinomial}\left(N; \frac {1} {N}, \frac {1} {N}, \ldots, \frac {1} {N} \right)$$

When the winning number $n = 1$, the winning condition is equivalent to $X_1 = 1$ and the probability is given by

$$ \binom {N} {1} \left(\frac {1} {N}\right)^1 \left(1 - \frac {1} {N}\right)^{N-1} = \left(1 - \frac {1} {N}\right)^{N-1}$$

which is well-mentioned in above discussion. When the winning number $n > 1$, the winning condition becomes $X_n = 1$ and $X_1 \neq 1, X_2 \neq 1, \ldots , X_{n-1} \neq 1$. Thus, the probability is $$ \begin{align} &~ \Pr\left\{(X_n = 1) \cap \bigcap_{i=1}^{n-1} (X_i \neq 1)\right\} \\ =&~ \Pr\left\{(X_n = 1) \cap \left(\bigcup_{i=1}^{n-1} (X_i = 1)\right)^c\right\} \\ =&~ \Pr\{X_n = 1\} - \Pr\left\{(X_n = 1) \cap \bigcup_{i=1}^{n-1} (X_i = 1)\right\} \\ =&~ \left(1 - \frac {1} {N}\right)^{N-1} - \Pr\left\{\bigcup_{i=1}^{n-1} [(X_n = 1) \cap (X_i = 1)]\right\} \\ =&~ \left(1 - \frac {1} {N}\right)^{N-1} - \sum_{j=1}^{n-1} (-1)^{j-1} \binom {n-1} {j} \Pr\left\{(X_n = 1) \cap \bigcap_{i=1}^{j} (X_i = 1)\right\} \\ =&~ \left(1 - \frac {1} {N}\right)^{N-1} - \sum_{j=1}^{n-1} (-1)^{j-1} \binom {n-1} {j} \frac {N!} {(1!)^{j+1}(N-j-1)! } \left(\frac {1} {N}\right)^{j+1} \left(1 - \frac {j + 1} {N} \right)^{N-j-1} \\ \end{align}$$

If you pull out the factor $\displaystyle \frac {1} {N^N}$, the expression becomes $$ \frac {1} {N^N} \left[ N\left(N-1\right)^{N-1} - \sum_{j=1}^{n-1} (-1)^{j-1} \binom {n-1} {j} \frac {N!} {(N-j-1)!} \left(N - j - 1 \right)^{N-j-1} \right]$$

Answer 2

For $n$ to win, one player has to pick it and all the others must pick something higher. The probability for that to happen are $N$ (to pick the player who chooses $n$) $\frac 1N$ (that the player picks $n$) $\left(\frac {N-n}N\right)^{N-1}$ (that all the other players pick larger numbers). The winning number is most likely to be $1$, with probability $\left(\frac {N-1}N\right)^{N-1}=\left(1-\frac {1}N\right)^{N-1}$ which tends to $\frac 1e$ as $N$ gets large. In general $n$ will be the winning number with probability about $\frac 1{e^n}$ for $n \ll N$. The chance of having a winning number at all, again for large $N$, is about $\frac 1{e-1}$