Part 2.2, exercice 2.7 and 2.8 [copy of a discord post]
Hello !
I was wondering for part 2.2, exercice 2.7 and 2.8 how to know the size of N ? (for how many steps to crawl). Should we compute the second eigenvalue lamda_2 in order to apply the mixing time of RW thm on slide 16 - lecture 4 ?
If so, I suppose computing all the possible set of nodes S would take an exponential time, is there a better way ?
(sorry for the duplicate question but I feel I might have more chance to get an answer here)
Should we compute the second eigenvalue lamda_2 in order to apply the mixing time of RW thm on slide 16 - lecture 4 ?
If so, I suppose computing all the possible set of nodes S would take an exponential time,
Good question! Using the theoretical bound is indeed computationally very (too) expensive (especially when the graphs get large).
is there a better way ?
As a hint: the random walk can be seen as a Markov chain. So, to get good estimates of quantities you want to measure (i.e., you are sampling from the chain), the chain needs to be near convergence.
Make sure to explain your strategy/motivation for choosing reasonable values of N (may or may not be different for different questions).
Part 2.2, exercice 2.7 and 2.8 [copy of a discord post]
Hello !
I was wondering for part 2.2, exercice 2.7 and 2.8 how to know the size of N ? (for how many steps to crawl). Should we compute the second eigenvalue lamda_2 in order to apply the mixing time of RW thm on slide 16 - lecture 4 ?
If so, I suppose computing all the possible set of nodes S would take an exponential time, is there a better way ?
(sorry for the duplicate question but I feel I might have more chance to get an answer here)
1
Good question! Using the theoretical bound is indeed computationally very (too) expensive (especially when the graphs get large).
As a hint: the random walk can be seen as a Markov chain. So, to get good estimates of quantities you want to measure (i.e., you are sampling from the chain), the chain needs to be near convergence.
Make sure to explain your strategy/motivation for choosing reasonable values of N (may or may not be different for different questions).
Hope it helps.
1
Thank you for your answer, I have a better idea now :)
1
Add comment