Number of Die Throws until you get a repeated number

[Master1022]

An asymptotic approximation would be: $\sum_{k=2}^{n+1}\frac{k!}{n^{k-1}}\binom{n-1}{k-2}\sim\sqrt{\frac{n\pi}2}+\frac23$
(with an error of approximately $\frac1{10\sqrt{n}}$). (ref)

Thanks @sysprog ! I actually made a Python simulation of this game for an arbitrary $n$-sided dice (unfortunately was made on a machine which I cannot access now). Nonetheless, your approximation gives a very similar result to some of the values I was getting from repeated experimentation (e.g. I also got a similar value for n = 100 to the one quoted by @FactChecker )

EDIT: what type of things should I read to learn about how one would derive that approximation? (or approximations to binomials in general)? I have never done any full probability & statistics courses so my knowledge only extends to reading random lecture notes on the internet.

 

[WWGD]

Thanks @sysprog ! I actually made a Python simulation of this game for an arbitrary $n$-sided dice (unfortunately was made on a machine which I cannot access now). Nonetheless, your approximation gives a very similar result to some of the values I was getting from repeated experimentation (e.g. I also got a similar value for n = 100 to the one quoted by @FactChecker )

EDIT: what type of things should I read to learn about how one would derive that approximation? (or approximations to binomials in general)? I have never done any full probability & statistics courses so my knowledge only extends to reading random lecture notes on the internet.

Try the original link and let us know if you have a question:

https://math.stackexchange.com/ques...ded-die-until-repeat-is-found/1908500#1908500

Here, basically, you have 6* options for the first throw, 5 for the second, etc. These can be rearranged in Cn,k (" n Choose k ) ways. All of it in n^k throws of the dice.

* Or, n, in the general case.

 

[Master1022]

Try the original link and let us know if you have a question:

https://math.stackexchange.com/ques...ded-die-until-repeat-is-found/1908500#1908500

Here, basically, you have 6* options for the first throw, 5 for the second, etc. These can be rearranged in Cn,k (" n Choose k ) ways. All of it in n^k throws of the dice.

* Or, n, in the general case.

Okay thanks will do. I will read the answer again, but I thought they just skipped from the summation expression to the form with $\sqrt{\frac{n \pi}{2}} + ...$

 

[WWGD]

Okay thanks will do. I will read the answer again, but I thought they just skipped from the summation expression to the form with $\sqrt{\frac{n \pi}{2}} + ...$

Yes, this is a limit form as the number of sides grows to $\infty$. I think it uses Stirling's approximation.

 

[sysprog]

Thanks @sysprog ! I actually made a Python simulation of this game for an arbitrary $n$-sided dice (unfortunately was made on a machine which I cannot access now). Nonetheless, your approximation gives a very similar result to some of the values I was getting from repeated experimentation (e.g. I also got a similar value for n = 100 to the one quoted by @FactChecker )

EDIT: what type of things should I read to learn about how one would derive that approximation? (or approximations to binomials in general)? I have never done any full probability & statistics courses so my knowledge only extends to reading random lecture notes on the internet.

Links to free textbooks on combinatorics:
https://www.whitman.edu/mathematics/cgt_online/cgt.pdf
https://users.math.msu.edu/users/bsagan/Books/Aoc/final.pdf
http://www-math.mit.edu/~rstan/ec/ec1.pdf
https://people.math.gatech.edu/~trotter/book.pdf
http://www.math.utk.edu/~wagner/papers/comb.pdf

There are many more if you do a search on: combinatorics textbook pdf
I included only a few that are from .edu sources; I can't be sure of the copyright authorizations on the others $-$ at least not sure enough to post them on PF.

In general, combinatorics may be thought of as a subdiscipline of discrete mathematics, although in asymptotic approximations and other aspects it abuts on or overlaps some continuous mathematics.