1
$\begingroup$

I got the following question in my interview: there is a fully connected graph with each edge has a weight $w$, i.i.d generated from an unknown distribution $F$. A pair $(a, b)$ is called a good pair if their edge weight $w_{ab} $ is the largest for all edges of $a$ and $b$. What is the expected number of good pairs when there are $n$ vertices?

My initial idea is to use a brute-force method to calculate the expectation. Basically there are $N$ chooses $2$ different pairs and we can think the probability that it is a good pair but this approach seems to be hard.

$\endgroup$
1
  • 1
    $\begingroup$ By “all edges of $a$ and $b$”, are you referring to all edges that are incident to $a$ or $b$ (or both)? Or are you referring to all $\binom{n}{2}$ edges of the graph? $\endgroup$
    – VTand
    Sep 20, 2022 at 3:54

1 Answer 1

1
$\begingroup$

For any pair $\{a,b\}$, there are $2n-3$ edges with at least one endpoint at $a$ or $b$, including edge $ab$. Because the edge weights are all identically distributed, any of these $2n-3$ edges has a $\frac1{2n-3}$ probability of being the one with the highest weight; in particular, there is a $\frac1{2n-3}$ probability that the weight $w_{ab}$ will be higher than all the others. Therefore there is a $\frac1{2n-3}$ probability that the pair $\{a,b\}$ is a good pair.

There are $\binom n2$ pairs total; by linearity of expectation, the expected number of good pairs is $\frac1{2n-3} \binom n2$. This doesn't simplify any further but is approximately equal to $\frac n4$, since $\frac1{2n-3} \approx \frac1{2n}$ and $\binom n2 \approx \frac{n^2}{2}$.

We can check that this is a reasonable quantity to expect from first principles. On the one hand, the edge with the largest weight in the whole graph always gives us a good pair, so we know the expected number of good pairs should be bigger than $1$. Other weights that are close to the largest should also be very likely to create good pairs. On the other hand, the number of good pairs can never be bigger than $\frac n2$, because two different good pairs cannot share a vertex. So an average close to $\frac n4$ is not surprising.

For a closely related problem, see How likely is it not to be anyone's best friend? which is about the probability that a particular vertex $a$ will have an edge $ab$ whose weight is higher than any other edge out of $b$. (A good pair is exactly a pair of mutual best friends, in the linked question's terminology.)

$\endgroup$

You must log in to answer this question.

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