Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
See also the earlier MO question, "Random Sampling a linearly constrained region in n-dimensions…. –  Joseph O'Rourke Apr 22 at 20:52

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer

This has been studied at length, see Kannan and Narayanan

share|improve this answer
    
Thanks @Igor for the reference. –  Kiu Apr 22 at 18:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.