9
$\begingroup$

Consider a drunk, blind man starting in the middle of the two dimensional open unit ball. At each turn, the man chooses a direction to move a step of size $\delta > 0$ in. Unfortunately, he is very drunk, so he has a $\frac{1}{2}$ chance of moving in the reverse direction instead! Further, he is blind, and without a cane so he does not know where he is after each step.

Formally, we write $(x_n, \theta_n)$ for the position and orientation of the man, where we start at $x_0 = 0$, $\theta_0 = 0$. A strategy is a sequence of angles $\phi_n$, chosen in advance.

Let $\epsilon_n$ be a sequence of iid Bernoulli random variables, taking values $0$ and $1$ with equal probability. Denoting by $R_{\theta}$ the rotation by angle $\theta$, and writing $v := (\delta, 0)$, his position and orientation are then updated according to the rule

$$(x_{n+1}, \theta_{n+1}) = (x_n + R_{\theta_n + \phi_n + \epsilon_n \pi} v, \theta_n + \phi_n + \epsilon_n \pi).$$

Question: What is an optimal strategy for the man to take to minimize the expected time to exit the ball?

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ I'm confused about the direction choice. How does he choose a direction? Is it absolute or with respect to how he's oriented? Is he oriented the same way he went in the previous step? $\endgroup$
    – user479223
    Commented Mar 14 at 0:48
  • $\begingroup$ @user479223 That's a very good point. If he is blind, the direction choice should be with respect to how he's oriented since he wouldn't have enough info to make an absolute choice. He should be oriented the same way he went in the previous step. I will add this to the original post. $\endgroup$
    – Nate River
    Commented Mar 14 at 7:42
  • $\begingroup$ Shouldn't $v$ be $(\varepsilon, 0)$, not $(1,0)$? $\endgroup$
    – Daniel Weber
    Commented Mar 14 at 8:02
  • 1
    $\begingroup$ How about a variant where the man can see where he is, and he wants to maximize the amount of time he spends inside the ball? $\endgroup$
    – Sam Hopkins
    Commented Mar 14 at 17:19
  • 2
    $\begingroup$ @SamHopkins: Except for tiny details, this is the same problem and also answered by Ofer's analysis: The time takes care of itself if we only maximize the distance from the circle when we do leave. (If the disk were closed, it would be clear-cut: we can do what we want as long as not close to the boundary, and when we get within distance $\delta$, we must aim at the boundary exactly and then continue in the radial direction.) $\endgroup$
    – Christian Remling
    Commented Mar 15 at 2:51

1 Answer 1

Reset to default
6
$\begingroup$

The expected exit time (from a ball of radius 1) is $(1+o_\delta(1))/\delta^2$, regardless of the choice of strategy (the $o_\delta(1)$ term does depend on the strategy). Indeed, write $X_n=\sum_{i=1}^n \epsilon_i v_i$ where $v_i$ are the steps chosen at time $i$. We then obtain that $$ |X_{n+1}|^2=|X_n|^2+2\langle X_n, \epsilon_{n+1} v_{n+1}\rangle+|v_{n+1}|^2=|X_n|^2+\delta^2+G_{n+1}$$ where, conditioned on $\sigma(X_i,v_i, i=1,\ldots,n, v_{n+1})$, $G_{n+1}$ has mean $0$. Therefore, $|X_n|^2-\delta^2 n$ is a martingale with bounded increments. Letting $\tau$ denote the exit time, we obtain that $E(|X_\tau|^2)=\delta^2 E\tau$. But $E|X_\tau|^2\in [1,(1+\delta)^2)$ and hence the conclusion. Note that we actually got that $E\tau\geq 1/\delta^2$.

Now, if you choose the angles to stay on a one dimensional line (ie, choose $\phi_n=\phi=ct.$), then you obtain (if $1/\delta$ is an integer) that $E\tau=1/\delta^2$, so this is the optimal strategy in that case. If $1/\delta$ is not an integer, I don't know if it is actually optimal or only near optimal.

Improve this answer
$\endgroup$
16
  • $\begingroup$ It seems that the strategy of always choosing a direction perpendicular to the center (which can be executed without knowing where you are!) also achieves the optimal bound of $\frac{1}{\delta^2}$ in the case of $\frac{1}{\delta}$ integer. Actually, it achieves this time deterministically. $\endgroup$
    – Nate River
    Commented Mar 14 at 12:46
  • $\begingroup$ I never claimed uniqueness..... But how do you know the direction perpendicular to the center? For example, after 3 steps where the first was $(\delta,0)$, the second $(0,\delta)$? $\endgroup$
    – ofer zeitouni
    Commented Mar 14 at 12:52
  • $\begingroup$ Yes I did not infer uniqueness from your answer. I may be wrong but it seems like by symmetry you always know your orientation with respect to the line toward the center. For example, after the first step you are always a clockwise turn of $\frac{\pi}{2}$ away from the desired perpendicular direction, after the second you are always $\frac{\pi}{4}$ away, etc. $\endgroup$
    – Nate River
    Commented Mar 14 at 13:12
  • 1
    $\begingroup$ Staying on a line is not always optimal. If the largest integer multiple of $\delta$ that is $<1$ is almost, but not quite, equal to $1$, then taking a single step vertically and then moving only horizontally after that is better. (In the first case, we must hit $\pm N$ with a random walk, in the second one, we must reach $\pm (N-1)$ and have wasted a step, but clearly the second scenario is better because any walk that takes us to $N$ in $k$ steps also took us to $N-1$ in $\le k-1$ steps, while the converse is not true.) $\endgroup$
    – Christian Remling
    Commented Mar 14 at 15:05
  • 1
    $\begingroup$ More generally (and more to the point perhaps), your argument shows that optimizing $\tau$ is the same as minimizing the distance from the circle when we do leave it. As an immediate consequence, staying on a line can not always be best because there are many special situations where we can guarantee to hit the circle exactly with a different strategy. $\endgroup$
    – Christian Remling
    Commented Mar 15 at 19:16

You must log in to answer this question.

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