Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There is a Wikipedia-type website of a fixed size of $S$ number of articles. You start at any article on Wikipedia. You then start to press the "random article" button and count the number of times $N$ that it takes for you to randomly generate the original page again.

The goal is to find the best estimate for $S$ given only the number $N$.

Assume that the "random article" function generates any particular article with a uniform probability and that each click is a (EDIT: independent) random event. The page that you start on does not count as a click and is thus not counted in $N$.

This problem reminds me of the solutions to the locomotive problem and the German tank problem. Since the button is clicked N times, the case with the highest number of articles has all N pages being different pages, yielding an estimate of (I think) $2N+1$. This would mean that the best estimate would be less than $2N+1$, because it is always possible for $N$ to contain an article, other than the one you were looking for, to be repeated multiple times.

Another possible solution is based off of the method of mark and recapture to estimate the size of animal populations in the wild. This method gives the estimate as $S=N$. This would because out of $N$ samples taken during the "recapture", exactly $1/N$ of them are articles viewed during the "mark" phase (original article that is remembered). Since $1/N$ of the pages are known to be picked from the group of one particular page, then the estimate would be that there would be $N$ pages in total.

share|improve this question
3  
Following the logic of the birthday problem, you can also look for the first time you see any repeated page. This will take of order sqrt(S) tries instead of order S –  Ross Millikan Mar 20 '12 at 23:28
    
This seems like a good problem for a latent random graph model. Given a model of some graph parameters (which will control the number of nodes and the diameter, etc.), you could use some Bayesian model fitting methods to decide which graph likely gives rise to your observed number of pages-before-repeat. That is how I would start, at least. Unlike the German tank problem, this one is sensitive to the graph structure you assume. There are well-confirmed network models of wiki-like graphs, though. Check out M.E.J. Newman's recent book on networks for some examples. –  EMS Mar 20 '12 at 23:31
    
"Assume that the "random article" function generates any particular article with a uniform probability and that each click is a random event." One might also want to assume independence of distinct "clicks". But are the assumptions valid? How would one test that? –  Michael Hardy Mar 21 '12 at 1:50
    
I was intending each click to be an independent event. Practically, I don't know how one would test that. –  PhiNotPi Mar 21 '12 at 1:54
2  
@EMS: I don't understand what graph structure has to do with this question. –  Qiaochu Yuan Mar 21 '12 at 3:45
add comment

2 Answers

up vote 5 down vote accepted

If $S$ is the total number of articles, the probability of observing $N$ is $$\frac{(S-1)^{N-1}}{S^N}.$$

We should choose an estimate for $S$ that maximizes this probability. Differentiating gives $$\frac{(N-1)(S-1)^{N-2} S^N - N S^{N-1} (S-1)^{N-1}}{S^{2N}} = (S-1)^{N-2} \frac{(N-1)S - N (S-1)}{S^{N+1}}$$

which is equal to $0$ when $S = 1$ and when $S = N$; the former is a local minimum and the latter is a local maximum, so indeed $S = N$ is a sensible estimate.


However, if you were actually going to try to do this, I think waiting until the first article repeats is a bad idea. You have to wait very long and in the meantime you're not using information about any other articles that may have repeated. As Ross says in the comments another idea is to wait until some article repeats. If $S$ is the total number of articles, the probability of observing $N$ is now $$P(S) = \frac{(S-1)(S-2)\cdots(S-N+1)N}{S^N} = \frac{N(S-1)!}{S^N (S-N)!}.$$

Stirling's approximation gives $$P(S) \approx C_N \frac{ (S-1)^{S-1} }{S^N (S-N)^{S-N} }$$

where $C_N$ is a constant depending only on $N$. Taking logarithms gives $$\log P(S) \approx \log C_N + (S-1) \log (S-1) - N \log S - (S-N) \log (S-N)$$

and taking derivatives gives $$\frac{P'(S)}{P(S)} \approx 1 + \log (S-1) - \frac{N}{S} - 1 - \log (S-N).$$

A local maximum should therefore occur when $\log (S-1) - \log (S-N) \cong \frac{N}{S}$, or when $$1 + \frac{N-1}{S-N} \approx e^{ \frac{N}{S} } \approx 1 + \frac{N}{S}$$

giving $S(N-1) \approx N(S-N)$ or $S \approx N^2$. So as Ross indicates this is much more efficient for obtaining an estimate.

share|improve this answer
    
The validity of all this depends on whether the "random article" function really picks a random article with a uniform distribution, and independence of distinct trials. How would one test that? –  Michael Hardy Mar 21 '12 at 1:49
add comment

It's first best to find out the distribution used by the random article generator. For a large site such as Wikipedia, I wouldn't be surprised to hear that a more computationally efficient random generator is being used rather than a fair uniform distribution.

To check your answer, WikiCount.net gives a good approximation to the number of articles in the English Wikipedia, using an interpolated polynomial from published data with updating coefficients.

share|improve this answer
    
The question was explicitly to Assume that the "random article" function generates any particular article with a uniform probability. Consider using the comment function for hints of this type. –  flonk Feb 26 at 10:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.