Django Wexler, an author I was rather fond of ten minutes ago, just did this to me:
If I have N N-sided dice (e.g. 100d100) and I roll them repeatedly, removing any that roll maximum (e.g. 100), what is the expected number of rolls until I have none left, in terms of N?
— Django Wexler (@DjangoWexler) April 17, 2018
I had a long day at work today, guys. My last customer of the night kept me at work well past closing time and didn’t buy, I want to curl up in bed with a book, and instead this damn math problem is in my head and fucking with me.
I may need to grab a note pad and oh fuck it I’ll do it on the blog.
Let’s say N is 2. So two bits, either 1 or 2. Roll them once.
25% of the time you get both twos. (so 25% of the time, only one roll)
50% of the time you get one two.
25% of the time you get two ones.
If you have one die left, you have a 50% chance of being done.
If you have both, see the above calculation.
this suggests you have a pretty big chance of being done after N rolls, with diminishing returns after N. I’m too tired to nail the numbers down, but I suspect N2 is a reasonable answer. Maybe tomorrow I’ll try to figure it out more carefully.
Assuming I can sleep, ever.