Random xkcd comic problem
Moderators: gmalivuk, Moderators General, Prelates
Random xkcd comic problem
I'm sure it's been thought of before, but I can't find it. Here's the question:
If you were to start out on xkcd.com, and press the random button (assuming true randomness) to see different comics, how many times on average would I have to press it to see every single comic? I need to give the problem a second thought, and I'm betting it's not too difficult to figure out, but in the meantime I want to see what others come up with.
If you were to start out on xkcd.com, and press the random button (assuming true randomness) to see different comics, how many times on average would I have to press it to see every single comic? I need to give the problem a second thought, and I'm betting it's not too difficult to figure out, but in the meantime I want to see what others come up with.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26035
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Random xkcd comic problem
At first glance this looks like the birthday problem, where the number of "days" is the number of comics accessible from the "Random" button, and you want to know how many independent samples you'd need before you expect the same one twice.
Only kink I can think of is that maybe "Random" won't give you the same comic twice in a row, which ever so slightly changes the probabilities from complete independence.
Only kink I can think of is that maybe "Random" won't give you the same comic twice in a row, which ever so slightly changes the probabilities from complete independence.
Re: Random xkcd comic problem
Yes, that definitely looks like it. I have a working program that simulates the problem, and when I get the chance I'll put up some graphs. I'd like to see a mathematical model for this problem though, so I'll page my way through that Wikipedia link and see if I can figure it out.
Re: Random xkcd comic problem
What's your stopping criterion: (1) you stop when you've seen every comic at least once, or (2) you stop when there's at least one comic you've seen twice?
(2) is the birthday problem; (1) is the coupon collector problem.
(2) is the birthday problem; (1) is the coupon collector problem.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26035
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Random xkcd comic problem
Ah, yeah, I misread the OP. The problem described there is definitely coupon collector, rather than birthday.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Random xkcd comic problem
The way it would work is this: assume that you have n comics, it only takes 1 try to find a comic you've never read before if you haven't started yet, but then the average amount of time to find another (different) comic is n/(n1), as 1 comic has already been read. Now to read the x^{th} comic (x<n) you need n/(nx) as there are n comics, but only nx comics that you haven't read yet. This works out to n*H_{n}, where H_{n} is the nth harmonic number (harmonic numbers are the sum of the first few reciprocals of natural numbers). If you approximate this you get E(n)=n*(ln(n)+y)+0.5, where y is the eulermacheroni constant.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Random xkcd comic problem
skullturf wrote:What's your stopping criterion: (1) you stop when you've seen every comic at least once, or (2) you stop when there's at least one comic you've seen twice?
(2) is the birthday problem; (1) is the coupon collector problem.
I interpreted it as (1) and tried messing around with it for awhile. I was worried when I saw the first response mentioning the birthday problem since I was like "wtf, have I just been being stupid?" since I had spent a decent amount of time poking around the problem trying get a feel for it before looking at the responses. Based on the wiki page it's a fairly deep problem as far as really characterizing what is going on with the stopping time, but the expected value and variance are trivial to get.
Re: Random xkcd comic problem
This was a fun problem. For completeness, as of this weekend, there are 1011 xkcd comics.
Thus, the expected number of clicks to see all 1011 is, on average, 1011*H_1011 = 1011*7.4964 whose closest integer is 7579.
So, about 7579 clicks to see all xkcd comics. This is suboptimal when compared with say, the previous button.
Thus, the expected number of clicks to see all 1011 is, on average, 1011*H_1011 = 1011*7.4964 whose closest integer is 7579.
So, about 7579 clicks to see all xkcd comics. This is suboptimal when compared with say, the previous button.
 phlip
 Restorer of Worlds
 Posts: 7550
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Random xkcd comic problem
A complication: the xkcd randomcomic script keeps track of the last 200 comics its randomly chosen, and won't pick one of those.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Random xkcd comic problem
Does that really change anything?
The first 200 give you unique comics. Then you have (n200)/((n200)x) for each comic x>=200, from tomtom2357s solution
The first 200 give you unique comics. Then you have (n200)/((n200)x) for each comic x>=200, from tomtom2357s solution
Re: Random xkcd comic problem
Bomaz wrote:Does that really change anything?
The first 200 give you unique comics. Then you have (n200)/((n200)x) for each comic x>=200, from tomtom2357s solution
Not quite. keeping the "last 200" implies that it doesn't stay the same. That is, the oldest comic on the list gets booted out when you
hit random.
http://en.wikipedia.org/wiki/DSV_Alvin#Sinking wrote:Researchers found a cheese sandwich which exhibited no visible signs of decomposition, and was in fact eaten.
 phlip
 Restorer of Worlds
 Posts: 7550
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Random xkcd comic problem
Sure, but the 200 in the list are, by definition, ones you've seen before, and they'll be distinct from each other. So there are always (n200) comics it could choose, of which (nx) are the ones you're yet to see. So you'll expect (n200)/(nx) clicks to see a new comic when you've already seen x of them (for x >= 200). (Note not ((n200)x) in the denominator, as that 200 is already part of the value of x.)
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Who is online
Users browsing this forum: No registered users and 8 guests