16
$\begingroup$

An individual, henceforth called the runner starts at the center of an open two dimensional square $\Omega$ of side length $r \geq 2$.

At each turn, a vector $x \in S^1$ is chosen uniformly at random, and the runner may choose to move one unit in the direction $x$ or $-x$ - that is, his new position is just his old position, translated by $x$ or $-x$. The runner’s goal is to stay within $\Omega$ for as long as possible.

Such a choice of moves by the runner is called an admissible strategy. Formally, denoting by $X_i$ the uniform choice of angles at each step, an admissible strategy is a sequence of $\{-1, 1\}$-valued random variables that is adapted to the natural filtration of the $X_i$.

Denote by $P_t$ the runner’s position at time $t$, and given a strategy $S$, define the exit time $\tau_S$ by

$$\tau_S := \inf \{t \in \mathbb Z_+ \, | \,P_t \in \Omega^c\}.$$

It is true, and not overly difficult to prove that given any strategy $S$, $\tau_S$ is finite almost surely.

An optimal strategy is one that maximises the expected time to exit - that is, $S_0$ is optimal if

$$\mathbb E[\tau_{S_0}] = \sup_{S} \mathbb E[\tau_S],$$

where the supremum is taken over all admissible strategies $S$. By compactness there exists at least an optimal strategy.

Question: What is an optimal strategy for the runner to use?

Improve this question
$\endgroup$
16
  • 3
    $\begingroup$ I guess if your shape is a circle, optimal strategy is the one to minimize distance from the center. (For a circle, by symmetry distance from center is all that matters, and there has to be some monotonicity/coupling argument implying that choosing smaller distance is always best.) For a square my feeling is that the geometry is going to make things horrible to deal with. A crazy conjecture is that minimizing $L^1$ distance from the center is optimal, but I doubt this is true (probably slightly higher $L^1$ distance along edge is better than slightly lower $L^1$ distance in a corner). $\endgroup$
    – Ronnie Pavlov
    Oct 5, 2022 at 23:34
  • 1
    $\begingroup$ @RonniePavlov Yes in the case of the circle, there is only the distance from the center as the sole invariant we need to care about. I was thinking that the expected number of moves to exit from being $r$ distance away from the center (given an optimal strategy) should be monotone decreasing in $r$, and hence the optimal move is always to go toward the center, or minimise distance from it rather. That said, I am uncertain as to whether it’s actually monotone for all $r$… $\endgroup$
    – Nate River
    Oct 5, 2022 at 23:36
  • 5
    $\begingroup$ Because it took me a moment to convince myself: the finiteness argument is that there's a $\epsilon$ such that for any position $P$ of the runner, a positive fraction of movement vectors $x$ have both $P+x$ and $P-x$ at least $\epsilon$ further from the origin than $P$, and therefore for any distance $d$ a positive probability of getting a sequence of moves (of length $\lceil d/\epsilon\rceil$) that force the runner to distance $d$ from the center. $\endgroup$
    – Steven Stadnicki
    Oct 7, 2022 at 18:12
  • 1
    $\begingroup$ (1) Surely the optimal strategy is myopic (i.e. only depends on the current point and not the history). (2) It also seems likely that there exists a function f(x,y), where x,y are horizontal,vertical displacement from the center, such that, given the choice between moving to points described by (x1,y1) or (x2,y2), the optimal choice is the point that minimizes f. Agree? $\endgroup$
    – usul
    Oct 19, 2022 at 16:15
  • 1
    $\begingroup$ Yes, that's what I mean. So, we need a function from the set of pairs (current point, $\pm$ direction of the current step) to ($\pm 1$) which maximizes the expectation $\endgroup$
    – Fedor Petrov
    Jan 17 at 7:46

1 Answer 1

Reset to default
1
$\begingroup$

This is not an answer, just a comment, but I want my formula to display nicely - no need to upvote.

So practically, you want to compute the unique function that satisfies $$ f(x,y)=\begin{cases} 1+\int_{\alpha=0}^\pi \min\begin{cases} f(x+\cos(\alpha),y+\sin(\alpha))\\ f(x+\cos(\alpha+\pi),y+\sin(\alpha+\pi)) \end{cases} & |x|,|y|< r/2, \\ 0 & \max(|x|;|y|)\ge r/2. \end{cases} $$

This reminds one not only of Markov-chains, but also of harmonic functions.
As the boundary conditions can make the function nasty, I propose to first determine the function for the disk, in which case the strategy is trivial, but I want to know the value of the expected number of steps.
By disk, I of course mean that the boundary condition is modified to give 0 when $x^2+y^2\ge r^2$.
This question already makes sense for any $r>\frac12$, just for $r<1$ the function will vanish outside some annulus of width $2r-1$.
I wonder from what $r$ will the maximum be at the origin.

Improve this answer
$\endgroup$
1
  • $\begingroup$ My conjecture is that in the case of a disk with radius $r$, the expected number of steps is approximately $e^{r^2}$, up to a constant factor. Actually it’s more than a conjecture - I have a rough computation showing this is the case. $\endgroup$
    – Nate River
    Jan 22 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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