1
$\begingroup$

Start at a point $(0,0,z_0)$ and take $n$ steps of unit length in a random direction (for each step) in $\mathbb{R}^3$. Let such a walk be valid if the position of the last step, and only the last step, is under the plane $(x_n,y_n,z_n<0)$. Let a walk be almost valid if at least the last step is under the plane.

How can I sample uniformly from the set of all valid or almost valid walks without a trial and rejection method?

  • 0
    Metropolis algorithm?2012-10-10
  • 0
    @mjqxxxx How would I calculate an acceptance ratio? Generating the weight of a partial walk is part of the problem I think.2012-10-10
  • 0
    Nice question. Are you using "step" and "point" interchangeably, or is that part of the distinction between *valid* and *almost valid*?2012-10-10
  • 0
    @joriki For $n$ steps, there are $n+1$ points on the walk (counting the first and last). I clarified the wording a bit to make that clear. In an _almost valid_ walk, the points can dip below the plane before the $n$th step. In a _valid_ walk only the last can be below the plane.2012-10-10

1 Answers 1