Graph Search problem modelled as Coupon Collector

113 Views Asked by At

This is a problem in QuantGuide (named as Graph Search 1):
You are given an undirected graph with 10 nodes. From every node, you are able to access any other node (including itself), all with an equal probability of $\frac{1}{10}$. What is the expected number of steps to reach all nodes at least once (rounded to the nearest step)?
My Approach:
This problem resembles the Coupon Collector problem with 10 distinct toys(here nodes) as we can go from one node to any other node. Hence the expected number of steps resembles the expected number of boxes to collect such that we can have all the toys(nodes) in this case.
The answer would be $nH_n$ where n is 10. The answer should be 29.2896825397. But this answer doesn't pass.
Can anyone suggest where I'm going wrong?

1

There are 1 best solutions below

8
On

It is unclear if the question consider the first step, assuming not, then the answer should be $nH_n$ where $n=10$.

$$nH_n=10H_{10}\approx   29.289682539682538 \approx 29$$

where the last approximation is due to rounding to the nearest step.

enter image description here