Threshold function - slide 21

Hi ! [slide 21]
While following the lecture, I did not get why the threshold function is defined that way.
Does the Coupon Collector problem give an insight of why it is this particular value log(n)/n ?
It probably does but I did not manage to find the link.


Top comment

The idea is that the coupon collector problem tells us the average number of edges in a graph of n nodes such that every node in the graph has at least a degree of 1.

A bin represents a node and a bin having a ball means that at least one node in the network flipped a coin and decided to draw an edge to this node.

Then, in the Erdös-Rényi random graph model, the expected number of edges is n times E[degree of a node] = n^2 times p. Hence, taking the result from the coupon collector problem, p should be around log(n)/n.

Thanks for the explanation - one small correction: given that an edge has two end points (in an undirected graph), it contributes to the degrees of two nodes --> for this reason, the expected # of edges is in fact

\({n \choose 2}p \sim n^2 p / 2\)

Page 1 of 1

Add comment

Post as Anonymous Dont send out notification