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?