Consider two-dimensional brownian motion, but in a maze, such that there are "walls" which prevent the path from taking certain steps (based on this tweet).

I'm curious about algorithms to efficiently sample from two different distributions (for a particular maze):

  1. The distribution of the path of the first particle to reach the end, out of a population of N particles.
  2. The distribution of paths which reach the exit at exactly time $t$. This is like a two dimensional Brownian bridge, but with extra constraints

Of course since it's impossible to represent an actual Brownian motion, an algorithm that converges to the samples from these distributions would be fine.

Is it possible to do better than actually simulating N particles for the first one? For the second, how can one sample from the distribution at all?

  • 2
    $\begingroup$ Please don't require us to visit another site: describe what that animation does. Given that the maze obviously requires a complicated description, it's too much to hope that the distributions of either (1) or (2) can be worked out directly. Your final question is a little strange, because the answer seems obvious: when you run a simulation until time $t,$ you have sampled from the paths that exit by time $t.$ BTW, unless you modify (2) to read "exit at time $t,$" it's not an analog of a Brownian bridge. $\endgroup$
    – whuber
    Sep 22, 2021 at 21:00
  • $\begingroup$ @whuber I've updated the question so that it no longer requires visiting the tweet. Also, I asked for efficient algorithms, so for 1) Ideally one that runs in time less than $O(Nt)$, and for 2) your proposed method may fail to generate any paths which exit by the required time. $\endgroup$ Sep 22, 2021 at 21:13
  • 1
    $\begingroup$ Ah I see you can just repeat sampling up until time $t$ until eventually you get a trajectory that exits. I've updated the question to say reach the exit at time $t$, which I'd initially wanted, and why I drew the analogy to a Brownian bridge. $\endgroup$ Sep 22, 2021 at 21:15
  • $\begingroup$ This may be totally not helpful, but this reminded me of a computerphile video about maze solving algorithms. May be an insight from understanding maze solving that gets towards your question. youtube.com/watch?v=rop0W4QDOUI $\endgroup$ Sep 23, 2021 at 0:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.