Inferring quantity based on changing repitition rate

[sir_manning]

Hey

I was bored the other day and I stumbled across a webcomic site. In my boredom, I kept on clicking "random" to choose a random comic. After a couple clicks on the random button, a comic that I had already read popped up.

Assuming it was truly random, I would have to run out of comics sometime. Also, as the amount that I read got smaller and smaller, clicking the random button would give me more and more comics that I had already read.

So now I'm wondering how I could go about getting an approximate number of how many individual comics exist on the site by applying some statistics to my initial few clicks (assuming that out of these clicks I will mostly get comics I haven't read but I will also get some repeats).

Thanks.

 

[John Creighto]

I'd start by making the assumption that they are uniformly distributed. For each comic you get their should be an average amount of clicks be for you get that comic again.

The average number of clicks would be given by:

\sum_1^\infty n p^n

where p is the probability of getting a given comic each click.

Thus if you look for the average number of clicks to get a given comic to repeat, you can estimate p. Once you have P then N would be equal to 1/p.

 

[John Creighto]

As a note to the above, the most accurate method would be to do maximum likelihood on a joint poison distribution. Your random variable would be the number of occurrences of each comic after a given number of clicks. If their is a lot of comics I suspect that this would be difficult computationally.

 

[John Creighto]

Here is a simple method. Count the average number of times each comic shows up after N clicks subtract one and take the average. Divide this by N.

Clearly for large N this should give the probability of getting a given comic each click. The inverse of this should be related to the number of comics. However, I'm not sure how large N needs to be for this to give a good estimate.