I want to solve for a conditioned random walk over a graph. I have a directed graph $G$. The random walkers start at a fixed node, Source. They all need to end up at fixed node, Sink. So the random walk is conditioned at the end point. I'm interested in the traffic at each edge. For one-dimensional random walks, there is the Brownian Bridge, and it has a simple enough simulation.
This is for an application, and good-enough approximate solutions are fine. I just don't want to re-invent the wheel if something like this is known. For an un-conditioned random walk, I would have used repeated multiplication with the transition matrix (adjacency matrix) of the graph.
This is what I was thinking:
- I simulate a forward walk for walkers starting at the source, and calculate the probability of ending up at each node $N$ at time $t$ by repeated matrix multiplication.
- Then I also simulate a reverse random walk from the sink. So I have a probability of ending up at each node from the sink.
- If I multiply these two, I should have the probability of going through each node on the way from the sink to the source.
But this would have to be calculated at each time point. Is this correct, and is it the best I can do? Is there a way to get the "steady state" solution, which is the probability of the random walkers being at each intermediate point for a steady flow from source to sink?
I know there are different algorithms for this, but can I do something as simple as this, instead of, say nonlinear optimization or MCMC simulation over all possible paths? My main problem is the size of the problem. My graph possibly has 100s of millions of edges, and 10s of thousands of nodes.
