I have an $m \times n$ grid graph. I want to generate a simple path from $(1,1)$ to $(m, n)$ uniformly from the set of all such paths. (Note I am not constrainted to move only right/down; the path may move up/right/left/down at any step)
I can easily generate a random path by choosing each step randomly (and backtracking if I get stuck). However, the distribution won't be uniform, as if you step uniformly in each direction, any direction that leads to fewer paths will be biased towards in the resulting distribution of paths.
I think if you could count the number of paths with a given prefix, you could simply choose which direction to move next by weighting by the amount of paths in that direction. However, Wikipedia suggests without a citation that counting such paths is thought to be a hard problem, so this would not lead to a tractable algorithm.
If this can't be done (efficiently), is there a good approximation scheme that gets close?
A similar problem is selecting a random MST uniformly, which Wilson's Algorithm accomplishes. I don't have a good enough understanding of why Wilson's Algorithm works to see if ideas from it can be applied to this situation.