# Random walk in a convex body or convex polytope

Let $\Delta$ be a convex body (i.e. a compact convex subset) or a convex polytope in $\mathbb{R}^n$. Let $x$ be a point inside $\Delta$ and consider a (uniform) random walk starting at $x$ inside $\Delta$. I am interested in the probability distribution of the first time the random walk hits a point in boundary $\partial \Delta$. We consider a uniform random walk were $x$ with equal probability can go to any point in a small neighborhood of radius $\delta$ of $x$. We are interested in the probability distribution (on the boundary) that the random walk hits a boundary point.

Is there a "nice" formula for this distribution on the boundary points (in terms of $x$ and $\Delta$)?

If $\Delta$ is a polytope one expects that this distribution should be related to the distance of $x$ to different facets of $\Delta$.

In general are there nice formula relating geometry of $\Delta$ and relative position of $x$ in $\Delta$ to probability distributions (associated to random walks)?

I am from algebraic geometry and don't know much about random walks. I thought this problem might be known to the experts.

## 2 Answers

As $\delta \to 0$ you are approximating Brownian motion. The measure on the boundary of the first hitting location of a Brownian motion is called harmonic measure. If you fix a subset of the boundary and let $x$ vary, the measure is a harmonic function of $x$.

In two dimensions, there is a conformal map to the disk which takes $x$ to the center, by the Riemann Mapping Theorem. This takes Brownian paths to Brownian paths, and for a nice enough region it extends to the boundary. The harmonic measure on the centered round disk is proportional to Lebesgue measure on the boundary circle, so the question is to compute the inverse of the Riemann map, restricted to the boundary. For polygons, there are complicated explicit Riemann maps, the Schwarz-Christoffel maps. There are numerous geometric estimates known.

This has been studied at length, see Kannan and Narayanan

• where can I find an implementation of this in Python? – gota Mar 1 '18 at 15:58
• – Vissarion Feb 9 at 14:39