Minimalist Graph Theory
An interesting graph theory question asked in Quadeye Placements
You are given an undirected graph with 11 nodes. From every node, you are able to access any other node (not including itself), all with an equal probability of 1/10. What is the expected number of steps to reach all nodes at least once (rounded to the nearest step)?
Note: the image is not a visualisation of the graph in question.
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
.
.
Solution
When rewording it to think about it as a 11-sided die, and we are trying to figure out how many rolls it will take to see all 11 sides at least once, it is easy to see that this is a variation of the coupon collector's problem.
The time until the first result appears is 1 as it takes one step to start somewhere. After that, once again we are guaranteed to visit another node in 1 step, so we add another one. The random time until a third (different) result appears is geometrically distributed with parameter of success 9/10, hence a mean of 10/9 (as the mean of a geometrically distributed random variable is the inverse of its parameter).
After that, the random time until a fourth (different) result appears is geometrically distributed with parameter of success 8/10, hence a mean of 10/8. And so on, until the random time of appearance of the last and tenth node, which is geometrically distributed with parameter of success 1/10, hence with mean 10/1. We now know the mean time to see the first through last numbers pop up, so our total expectation will be summing all of the individual expectations up.
This yields our solution of 30.
.
.
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!