What's the fastest way to sample a random walk on a directed graph conditional on the start and end points?
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.
-
I've done the maths for figuring out how to do similar things lazily as you go before and it works out pretty fiddly. You can solve increasingly large fragments to get upper and lower bounds on weights but it's a pain.
- Još 2 druga odgovora
Novi razgovor -
-
-
Oh wait the Boltzmann sampler version shows it works in general because you can just add fake edges that to nowhere useful. This is very much sledgehammer to crack a walnut. It's probably got an elementary proof it works but I don't have a blackboard to hand
-
Or you could do something hybrid: run the random walk for N steps, or until you enter the precomputed region, then do the linear algebra on the current reachable fragment, abort if you're in a probability zero region, or switch to weighted walk.
- Još 1 odgovor
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.