What's the fastest way to sample a random walk on a directed graph conditional on the start and end points?
I haven't checked details but I think following works: Precompute P(ever reaches desired end given uniform walk) using linear algebra Beginning at start, walk sampling each node with weight proportional to the precomputed probability.
-
-
This should work. Certainly it gives you a random walk of the right type, and it produces the right answer for sure if all nodes have the same number of out edges (it's a Boltzmann sampler then) but like I say haven't checked details.
-
This sounds correct to me. I'm just wonder if there's a way to avoid solving the whole linear system. Like maybe there's a way for our sampling process to guide how much we need to solve.
- Još 3 druga odgovora
Novi razgovor -
Čini se da učitavanje traje već neko vrijeme.
Twitter je možda preopterećen ili ima kratkotrajnih poteškoća u radu. Pokušajte ponovno ili potražite dodatne informacije u odjeljku Status Twittera.