3
$\begingroup$

my question

  • a website with a million (1 000 000) pages.
  • each of these pages has a random link section with 3 random links to other pages of the same website (the 1 000 000 pages)
  • a webpage does not link itself or to the same page twice from the random link section
  • what is the probability that each webpage has at least 1 link from another webpage (from the random link section)?

I calculated this years ago and estimated 98%, but well I now want to double check as I'm going to publish a book and my probability math skills are more than rusty.

thx a lot.

$\endgroup$
2
  • $\begingroup$ can a site link to the same page twice? $\endgroup$
    – JMP
    Commented Nov 5, 2015 at 15:36
  • $\begingroup$ hi, the three random links per page are unique per page. within one page there are no duplicate links. $\endgroup$ Commented Nov 5, 2015 at 15:38

1 Answer 1

3
$\begingroup$

The probability that each of the one million pages is linked to at least once is $0$ for all practical and impractical purposes.

We will instead compute the probability that a given page P is linked to at least once. The probability P is linked to by page Y is $\frac{3}{999999}$. So the probability it is not linked to by page Y is $1-\frac{3}{999999}$.

By independence, the probability that P is not linked to by any page is $\left(1-\frac{3}{999999}\right)^{999999}$.

This, to high accuracy, is $e^{-3}$. So the probability P is linked to by at least one page is very close to $1-e^{-3}$. This is quite close to $95\%$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .