9
$\begingroup$
  1. Consider a planar (2D) random walk comprised of N steps.

  2. Consider the minimum convex polygon enclosing the N points visited by the random walker.

  3. Assume the definition of the width of a convex polygon given in http://cgm.cs.mcgill.ca/~orm/width.html

Is it possible to determine the probability density of the width of such a random convex polygon?

$\endgroup$
6
  • 2
    $\begingroup$ There is info available, not necessarily answering your precise question, e.g. What's the average width of a convex polygon?. $\endgroup$ Commented Oct 5, 2013 at 22:04
  • 1
    $\begingroup$ @JosephO'Rourke your link is about computing the average width (usually known as the "mean width") rather than what is wanted in this question, the (minimum) width. $\endgroup$
    – j.c.
    Commented Oct 6, 2013 at 9:53
  • 4
    $\begingroup$ You're looking for information on the convex hull of a random walk on which there is some literature. In particular, this paper of Spitzer and Widom ams.org/journals/proc/1961-012-03/S0002-9939-1961-0130616-7 computes the expected perimeter of such a polygon, using Cauchy's surface area formula which relates the perimeter to the mean width (averaged over projections onto lines in all directions). Unfortunately, I don't (yet?) see how to compute from their work anything about the minimum width (over all projections). $\endgroup$
    – j.c.
    Commented Oct 6, 2013 at 10:06
  • 1
    $\begingroup$ In 1941 Daniels was the first to investigate the extent or span of a 1D random walk. He actually determined the probability density of the span of a random walk in 1D. G.H. Weiss and R.J. Rubin generalized the notion of span to multi-dimensional random walks. Spans are the sides of the smallest rectangular box with sides parallel to the coordinate axes that entirely contains the random walk. In 2D, they were able to determine the probability densities for the smallest and largest spans. This is as close as I could get to the answer. $\endgroup$
    – toni
    Commented Oct 6, 2013 at 13:37
  • 1
    $\begingroup$ A related and perhaps easier question might be the following: What is the distribution of the diameter of the smallest sphere entirely containing the random walk. This question was discussed by Weiss and Rubin here in 1983. Is it possible that the question is still open? I tried combing the literature, but could not find anything. Perhaps I have missed some very important works. $\endgroup$
    – toni
    Commented Oct 6, 2013 at 14:00

1 Answer 1

7
$\begingroup$

(Not an answer; rather an example.)

Here is a random walk with random $\pm 1$ $xy$-steps with equal probability (you didn't specify details), for $n=10^4$ steps, and its convex hull.
   RandWalk10K
And here is the very same random walk extended to $n=10^5$ steps:
   RandWalk100K


Added 15Oct15. There is a new paper relevant to this question:

Zakhar Kabluchko, Vladislav Vysotsky, and Dmitry Zaporozhets. "Convex hulls of random walks, hyperplane arrangements, and Weyl chambers." (arXiv abstract.)

"We give an explicit formula for the probability that the convex hull of an $n$-step random walk in $\mathbb{R}^d$ with centrally symmetric density of increments does not contain the origin."

By "contain" here they mean "strictly contain in the interior of the hull."


Update 1Apr2017. The same authors have revised their paper, establishing a formula for the expected number of $k$-dimensional faces of the convex hull of a random walk:

Kabluchko, Zakhar, Vladislav Vysotsky, and Dmitry Zaporozhets. "Convex hulls of random walks: Expected number of faces and face probabilities." Revised 21 Aug 2017. (arXiv:1612.00249 Abs.)

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .