13
$\begingroup$

Consider the following puzzle: On the integer line from 1 to $t$ (top, let's say 1000 for this example), you have two operators: uniform random on 1 to $t$, and subtract 1. What is the optimal algorithm to reach 1 with the least number of operators?

For example, if you do one random sample and then always count down, on average it will take 500 steps (or maybe 501 if you count the initial step). An obviously better algorithm is to pick a random value until you get below some threshold, and then count down.

We programmed this for $t=1000$ and the best threshold was 42. Interestingly (perhaps obviously) below this you get a power function (about $x^{-0.812}$), and above this it linearly increases to 500.

Two questions: 1. Is there a better algorithm in general? 2. If ours is optimal what is the general equation for the minimum threshold? (Implicit third question: Presumably someone's already asked this...pointer please!)

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Can you specify what you mean by optimality? For example, do you want to minimize the expected value of the number of steps that we take to reach 1? $\endgroup$
    – Joseph Van Name
    Commented Sep 24, 2023 at 16:33
  • 4
    $\begingroup$ It's written in an amateurish way, but I don't think this question is completely trivial, so the downvotes seems excessive to me. $\endgroup$
    – Sam Hopkins
    Commented Sep 24, 2023 at 17:48
  • 2
    $\begingroup$ What is amateurish about they writing? (Not defensive; Trying to learn.) The problem actually was posed by my 14 year old son, so perhaps it’s not too surprising that it’s amateurish as he’s an amateur. :-) $\endgroup$
    – jackisquizzical
    Commented Sep 25, 2023 at 2:16
  • 2
    $\begingroup$ @jackisquizzical Here's how I might write your first paragraph. Fix a positive integer $t$. Let $D$ denote the operation of replacing a given integer $n$ by $n-1$, and let $R$ denote the operation of replacing a given integer $n$ by a positive integer chosen uniformly at random from $\{1,2,\ldots,t\}$. Given a starting value $n_0$, we may apply any sequence of $D$'s and $R$'s we like to $n_0$. Our goal is to minimize the expected time to reach 1 for the first time. What is the optimal sequence of $D$'s and $R$'s? $\endgroup$
    – Timothy Chow
    Commented Sep 27, 2023 at 20:36
  • 2
    $\begingroup$ (continued) This rewrite is wordier, but it spells out explicitly that you're applying the operations sequentially to a single starting value, and that what you're trying to minimize is the expected time to reach 1 for the first time. These details can be plausibly inferred from your more concise description, but it's more "professional" to spell out such details explicitly, so as to remove all doubt about your intended question. There is also no need to use the word "puzzle." $\endgroup$
    – Timothy Chow
    Commented Sep 27, 2023 at 23:32

2 Answers 2

Reset to default
16
$\begingroup$

You can solve the problem via dynamic programming. For $n\in\{1,\dots,t\}$, let $V(n)$ be the minimum expected number of steps starting from $n$. Then $V(1)=0$ and otherwise $$V(n) = 1+\min\left(\frac{1}{t}\sum_{k=1}^t V(k), V(n-1)\right).$$

Because $V(n)$ appears on both sides, you cannot just iterate the recursion. Instead, you can use linear programming as follows. The problem is to maximize $\sum_{n=1}^t V(n)$ subject to linear constraints \begin{align} V(1) &= 0 \\ V(n) &\le 1 + \frac{1}{t}\sum_{k=1}^t V(k) \\ V(n) &\le 1 + V(n-1) \\ \end{align} Here's a plot of $V(n)$ for $n\in\{1,\dots,1000\}$: enter image description here

In particular, $$V(n)= \begin{cases} n-1 &\text{for $n \le 45$}, \\ 44+2/9 &\text{otherwise}. \\ \end{cases}$$

Improve this answer
$\endgroup$
0
16
$\begingroup$

Because using the random operator destroys any potential gain from a previous subtraction, the optimal strategy must look like the one stated in the question. The solution of @RobPratt showed that in this case $$ V(n) = 1+\min\left(\frac{1}{t}\sum_{k=1}^t V(k), V(n-1)\right).$$ For $t=1000$ he showed that the threshold value is $m=44$ and for $n\geq m+2$ one has a constant $V(n) = m+\xi$ with $\xi=2/9$, whilst for $n\leq m+1$ one has $V(n)=n-1$. For general $t$ one can use the equation to infer that for some $0\leq \xi<1$ $$V(m+2) ~=~ 1+\frac{1}{t}\sum_{k=1}^t V(k) ~=~1+ \frac{1}{t}\sum_{k=1}^{m+1} (k-1) + \frac{(m+\xi) (t-m-1)}{t}. $$ Because $V(m+2) =m+\xi$ This gives $$m+\xi ~=~ 1+ \frac{1}{t} {m+1 \choose 2} + \frac{(m+\xi) (t-m-1)}{t},$$ and after solving for $\xi$: $$\xi= \frac{t}{m+1} -\frac{m}{2},~~{\rm or}~~0\leq \frac{t}{m+1} -\frac{m}{2}<1.$$ Rearranging gives $${m+1 \choose 2} \leq t< {m+2 \choose 2}, $$ which uniquely defines the threshold $m$ as $$m ~=~ \left\lfloor \frac{\sqrt{8\,t+1} -1}{2} \right\rfloor.$$

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ So, I have a dilemma. I’d like to check mark both this and the previous answer that this one builds upon, but I don’t think that’s possible. $\endgroup$
    – jackisquizzical
    Commented Sep 25, 2023 at 2:17
  • 2
    $\begingroup$ @jack, flip a coin. No one here gets hung up about a few imaginary internet points. $\endgroup$
    – Gerry Myerson
    Commented Sep 25, 2023 at 12:53
  • 1
    $\begingroup$ Also, @jackisquizzical, your saying things like that tends to attract upvotes, so don't worry, Karl will get his imaginary internet points. $\endgroup$
    – Michael Lugo
    Commented Sep 25, 2023 at 14:40

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