0

I come from a CS background and had to contend with a problem similar to this one. Essentially, I want a general-case estimate on how many rolls I'd have to make to land on the same number twice with a (fair) $k$-sided die.

I got as far as this for an expected value:

$$\displaystyle \sum_{n=1}^{k}\frac{(k-1)!\cdot n^2}{(k-n)!\cdot k^n}$$

and managed to simplify it to this cute looking guy:

$$\displaystyle \sum_{n=1}^{k}\frac{\binom{k-1}{n-1}\cdot n!\cdot n}{k^n}$$

But here, i have no idea how to proceed, I'd do with a simple asymptotic approximation but I got nothing. Through computer simulation, I found this very close to $\sqrt{k}$ as far as $k=10^{10}$ but I can't really prove it, any help would be appreciated.

Community
  • 1
bentheiii
  • 103
  • 3

1 Answers1

0

Hint: Look up the birthday paradox problem and calculations related to it. Your empirical observation that it has something to do with $\sqrt{k}$ is right on the money.

user2566092
  • 26,142