10
$\begingroup$

I need to make sure that my XML sitemap has less than $1\%$ rubbish (broken links). The list of URL is in the hundred of thousands, and even if it could be feasible to test them all 1 by 1 I'd rather not, for many reasons:

1 - Saved bandwidth
2 - Faster traffic for real clients
3 - Less noise in visitor statistics (because my test would count as a visit)
5 - I could go on...

So I think taking a random subset would be sufficient, problem is I don't know probabilities.

Is there a simple function I can use?

If it helps, we can suppose to have an a priori information on the probability of a link to be broken across runs. Let’s say that across runs there is a $0.75\%$ for any given link to be broken.

Improve this question
$\endgroup$
10
  • $\begingroup$ How many URLs do you have? (Inference about a finite population is somewhat different from the usual case of inference about an infinite population.) $\endgroup$
    – Kodiologist
    Commented Sep 25, 2017 at 15:52
  • $\begingroup$ ?? a finite number obviously $\endgroup$
    – gurghet
    Commented Sep 25, 2017 at 15:53
  • $\begingroup$ That goes without saying, but which finite number? $\endgroup$
    – Kodiologist
    Commented Sep 25, 2017 at 15:53
  • $\begingroup$ in the hundred of thousands, every day is a bit different $\endgroup$
    – gurghet
    Commented Sep 25, 2017 at 15:55
  • $\begingroup$ What's happening to your site map that's changing it? Do you have a completely different site map each day, or are some URLs added and removed? If the latter, can you keep track of which have been added or removed, so that you only need to check new ones? $\endgroup$
    – Kodiologist
    Commented Sep 25, 2017 at 15:56

2 Answers 2

Reset to default
4
$\begingroup$

So it depends on the distribution of your prior belief about the breakage rate, but: about 3600. 

import scipy as sp

p = 0.0075
threshold = .01
confidence = .95

f = lambda n: sp.stats.beta(a=n*p, b=n*(1-p)).cdf(threshold) - confidence
print(sp.optimize.fsolve(f, 1000)[0])

>> 3627.45119614

The idea here is to model link breakages as a Bernoulli trial, and model your beliefs about the breakage rate as the beta distribution. The beta distribution is conjugate to the Bernoulli distribution, and the way to update a beta distribution when you run a trial is pretty simple:

  • if it's a failure, you add one to the first parameter, $\alpha$
  • if it's a success, you add one to the second parameter, $\beta$

So if we start with a $\text{Beta}(0, 0)$ distribution and see failures about .75% of the time, how many trials will it take before 95% of the distribution's mass is below 0.01? About 3600.

Improve this answer
$\endgroup$
1
  • $\begingroup$ One of those cases where Bayesian analysis makes more sense since the prior is not just a wild ass guess or worse an intent to manipulate. But perhaps you could perform a sweep over the $p$ parameter say from 0.5 to 0.9% and plot the corresponding required $n$ $\endgroup$
    – David Ernst
    Commented Sep 26, 2017 at 17:57
1
$\begingroup$

For $n$ samples with $p=0.0075$ chance of failure, the variance for number of failures is $n p (1-p)$. So using central limit theorem, with $Z$ a standard normal, \begin{align*} \mathbb{P}(\text{failures} < .01 n) \approx \mathbb{P}(Z < \frac{n (.01 - p)}{\sqrt{n p (1-p)}}) \approx \mathbb{P}(Z < \sqrt{n} .02898) \end{align*} Now we want the above to equal 95%, which corresponds to $Z = 1.645$. Solving for $\sqrt{n} .02898 = 1.645$, I get $n=3222$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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