[sclug] Probability problem

[Roland Turner]

I have forgotten how to work this out and, before I spend loads
of time on it, am hoping that someone can remember a
straightforward way to do it.


1. Assume the existence of a pool of n participants (network
nodes, human beings, bees, ...).

2. Participant X has Ax associates, chosen entirely at random
from the n-1 other participants in the pool.

3. Participant Y has Ay associates, chosen entirely at random
from the n-1 other participants in the pool.

4. Participant X's associates and participant Y's associates are
completely uncorrelated which, IIRC, means that the probability
of any one of X's associates also being one of Y's associates is
identical to the probability of any one participant being one of
Y's associates which is Ay/(n-1). {{ n-1 because Y is not an
associate of itself. }}

My question is: What is the probability that some participant X
has an associate in common with some other, specific, participant
Y?

A reasonable first approximation appears to be Ax.Ay/(n-1), but
how close is this? Over what range? Can an exact form be written
down?

In particular, how close is that approximation in the specific
case where Ax = Ay ~= SQRT(n) (N.B. Ax, Ay and n are all
integers). e.g. What is the probability that X and Y have an
associate in common when each has one thousand randomly chosen
associates from a pool of one million participants? The above
approximation approaches (indeed, exceeds) 1.0 in this example.
How far is this from the reality?

(The underlying problem is connectivity in peer-to-peer
networks.)

- Raz