3
$\begingroup$

This is a hard problem for me to word in the title, so I'll try to do better now. Consider the following "game":

You are sitting in a room beside a table. In the middle of the table there exists a box containing a very large sum of money. The box will only open if you've waited long enough (the time to wait is a random value between $0$ and $MAX$ seconds inclusive). So, there is a chance that the box will be unlocked immediately, or it very well might not unlock until MAX seconds have elapsed.

Here is the tricky part. The act of CHECKING the box to see if its open resets the timer back to zero. So say we have $MAX = 100$ seconds, $MIN = 0$ seconds, and the ACTUAL timer on the box is $25$ seconds. If we wait at least $25$ seconds, the box will be open. However, if we open at any time before 25 seconds, we have to wait at least $25$ seconds from THEN before the box will be open.

So you might ask "Who cares if I have to wait MAX seconds? Im guaranteed to be able to open it after MAX seconds". Well what if we add the twist that each elapsed second since you sat down will decrease the value inside the box by $\frac{3}{4*MAX}$ of the original value. If we use that, then that means if you wait MAX seconds, you will get a quarter the money $\frac{money - 3*MAX}{4*MAX} = 0.25*money$. If you open it at $25$ seconds (max seconds is $100$ remember), then you get $\frac{money - (3*25)}{(4*100)*money} = \frac{325}{400}$ of the money, or 81.25%. This is the BEST you can do, you just don't know that.

So, what is the optimal strategy to get the most money out of the box? If the actual timer was $0$ seconds, you could immediately take 100%. However if it's $10$ seconds and you first check $1s$, then $2s$, then $3s$... you're quickly losing value since the penalty is based on TOTAL ELAPSED TIME. So checking at 1, 2, 3 would be 6 elapsed seconds.

Another key piece of information is that the actual timer value is EQUALLY LIKELY to be any time between 0 and MAX seconds. I think that this fact and the penalty equation ($\frac{3}{4*MAX}$ for example) are the main keys to solving this puzzle.

Obviously you can guarantee yourself $25%$ money by just waiting MAX seconds, but we are greedy and want the most we can possibly get (On AVERAGE). What is our strategy?

As for my thoughts... I think the answer is that you check every k seconds... maybe $\sqrt(MAX)$ or something. It would be something that I could easily play with and simulate in a programming sandbox, trying all sorts of different stepping schemes for a bunch of random actual values between 0 and some max. Eventually I may be able to pull out some sort of general solution.

It would be more interesting to me though if anyone recognizes this problem and knows an analytical optimal solution based on the penalty amount and the fact that the chances are uniform. Any ideas are welcome, this is just for fun!

PS. I thought of this because I was recently playing a game and got banned for joining and leaving too many games too quickly. You are banned for a time between MIN and MAX seconds (based on offense though, not equally likely) and every time you try to login your penalty timer resets. So you don't know what the penalty timer is, you just know the time you waited since your last try wasn't long enough. Goal of course is to play again in the quickest amount of time. But this should be pretty much identical to what I've described above.

EDIT: SOLUTION Thanks to the derivation of the optimization function by Bey, I was able to solve this problem.

I noticed that with a few tests, $\sum_{i=1}^{N-2}t_i > \sum_{i=1}^{N-2}t_i*t_{i+1}$

Consider N = 3, which gives us: $t_1 > \dfrac {1}{M} * (t_1*t_2)$

Which is the same as:

$t_1(1 - \dfrac{t_2}{M}) > 0$

This is always true since $t_2 \leq {M}, t_1 \geq 0$

Or, in general...

$t_1 + t_2 +...+t_{N-2} > \dfrac {t_1t_2 + t_2t_3 +...+ t_{N-2}t_{N-1}} {M}$

because:

$t_1(1 - \dfrac{t_2}{M}) + t_2(1 - \dfrac{t_3}{M}) +...+t_{N-2}(1 - \dfrac{t_{N-1}}{M}) > 0$

Thus, our best solution is to simple use N = 1 guess, where $t_1 = t_n = M$, because the cost function is zero there.

So unfortunately not an exciting result, but it seems in such circumstances as this, you cannot do better on average than just making one choice which is the max time. If you don't know the maximum time? That's a different problem!

$\endgroup$
  • $\begingroup$ Your equation $\frac{money-3*MAX}{4*MAX}=0.25*money$ is incorrect. You would need a set $money<3*MAX$ so you don't end up with a negative value. $\endgroup$ – Jeffrey L. Jun 2 '15 at 14:35
  • $\begingroup$ It was edited to use "math formatting", my original intention was money - (3*max/4*max). Or in general, money - (3*totalElapsed)/(4*max). It can still go below zero here, but hey that can be part of the game! If you guess too poorly you can actually have to pay money :) $\endgroup$ – user2045279 Jun 2 '15 at 14:56
  • $\begingroup$ An interesting extension would be to assume the stopping time follows an exponential distribution. It's memorylessness property will come in handy and ull get a problem without a maximum Possible cool down time $\endgroup$ – user237392 Jun 3 '15 at 22:30
1
$\begingroup$

Lets start with a finite-horizon sub-problem and expand:

Let $t_i$ be the amount of time you decide to wait on guess $i$ and lets say that you decide that you want the game to end after $N$ guesses (finite horizon). Now, lets say that you lose $c\%$ of the original amount per unit time. Finally, let $T$ be the random true waiting time, $T\sim U(0,M)$.

There are two possibilities for any given guess, $t_i$:

1) $t_i\geq T$ implying a loss of $ct_i$ for this guess (and the game ends) 2) $t_i<T$ and you incur a loss of $ct_i$ plus the expected loss of future guesses.

The expected loss function can be written recursively as:

$$L(t;i)=P(t_i\geq T|T>t_{i-1})ct_i+P(t_i<T|T>t_{i-1})E[ct_i+L(t;i+1)|T>t_{i}]=$$ $$ct_i+P(t_i<T|T>t_{i-1})E[L(t;i+1)|T>t_{i}]$$

The total expected loss will be a function of $N$ and the vector $t\in [0,M]^N$, and will be represented by $L(t;N)$, where this means that we start at $i=1$ and continue recursion for $N$ levels.Also, $0\leq t_{i-1}\leq t_i \leq M$ and $t_0=0,t_N=M$ to ensure we end the game by guess $N$.

Note that $L(t;i)$ is defined recursively.

However, since $T$ is uniformly distributed, we get:

$$ p_i:=P(t_i<T|T>t_{i-1})=\frac{M-t_{i}}{M-t_{i-1}}$$

Then if we expand the sum, we will get:

$$L(t;N)=ct_1+p_1[ct_2+p_2[ct_3+p_3[...[...[cM]...]...]]]$$

Simplifying and condensing we get:

$$L(t;N) = c\left[t_1+p_1t_2+p_1p_2t_3+p_1p_2p_3t_4+...+(p_1...p_{N-1})t_N \right]$$

Substituting in our equations, we get:

$$L(t;N)=c\left[\sum_{i=1}^{N}\left(t_i\prod_{j=1}^{i-1}\frac{M-t_j}{M-t_{j-1}}\right)\right]$$

Now, a nice thing happens with the product: it telescopes! We get a much simpler formulation now:

$$L(t;N)=\frac{c}{M}\sum_{i=1}^{N}\left[t_i(M-t_{i-1})\right]=c\left[ M+\sum_{i=1}^{N-1}t_i-\frac{1}{M}\sum_{i=1}^{N-2}t_it_{i+1}-t_{N-1}\right]$$

The optimization problem can be stated as:

$$\min_t \left\{\sum_{i=1}^{N-2}t_i-\frac{1}{M}\sum_{i=1}^{N-2}t_it_{i+1}\right\}$$ $$s.t.: 0\leq t_i\leq M \;\;\mathrm{for}\;i<N$$ $$t_i-t_{i-1}\geq0 \;\;\mathrm{for}\;1<i<N$$

and we are setting $t_N=M$ to stop the process.

So, even though we are stopping after $N$ time periods, we only have $N-1$ free variables to choose.

Note that the loss rate is inconsequential to finding the optimum, so I removed it from the objective function. This is a Quadratic Programming problem, for which there are a number of solution algorithms (see Wiki page). The overall solution procedure will be to plot the optimal expected loss (optimal value of objective function) for different values of $N$ and see where the global minimum is. This will be your solution.

$\endgroup$
  • $\begingroup$ Thank you for the detailed explanation! I understood each step very clearly. So we are optimizing on the vector of guesses, t, where each subsequent guess is greater than the last and the final guess is always the max. In order to find the global optimum, we must find the optima of many N (number of guesses) to see which local optima is the best. I have Matlab, which can do such problems with the Optimization Toolbox... I'll look into getting a free trial of that, or perhaps another program/sdk can solve them. Thanks again, if I am able to solve it Ill update my post with the answer $\endgroup$ – user2045279 Jun 3 '15 at 15:14
  • 1
    $\begingroup$ @user2045279 no problem, glad that helped. You can use R to solve this too. Its free and has ready-made quadratic programming facilities: r-bloggers.com/… $\endgroup$ – user237392 Jun 3 '15 at 15:34
  • $\begingroup$ Very cool, I'll check it out! The cost function is so simple here (just 2 for loops in code), should be able to try a large number of different N. $\endgroup$ – user2045279 Jun 3 '15 at 15:38
  • $\begingroup$ I understand the edits, but now I am a little confused for our objective function... It looks like at N=1 guess, our min is zero. I then ask, is it possible that our function is ever negative? If not, then obviously the answer is to always make just one guess... max. So more formally (1/M)*SUM_1_N-2(t_i*t_i+1) > SUM_i_N-2(ti). Ill try to solve that... We can try with N = 3, for example: t1*t2/M > t1... t2/M > 1. That should never be the case since t_i+1 > t_i and t_n = MAX. $\endgroup$ – user2045279 Jun 3 '15 at 21:16
  • $\begingroup$ @user2045279 note that I've removed extraneous items from the objective function. Zero means you incur a loss of $M$ seconds. The objective function is simply to help set the variables to their optimum. $\endgroup$ – user237392 Jun 3 '15 at 21:19
1
$\begingroup$

Let $T$ be a random variable that measures the time before the box can be opened. Let $W_\vec x$ be a random variable that measures my winnings if $\vec x$ is a vector defining the times I'll wait (such that $x_1$ is the number of seconds before my first try, $x_2$ before the second, and so on). Note that $x_i<x_j\ \forall i<j$. Also I'll define $x_0=0$ since trying it at time $0$ doesn't affect. $m$ will be money and $M$ the max time.

$\begin{align} E[W_\vec x]&= \sum_{i=1} P(T\leq x_i\mid T > x_{i-1})(m-\frac{3m}{4M}((\sum_{j=1}^{i-1}x_j)-T))\\ &=\sum_{i=1} P(T\leq x_i\mid T > x_{i-1})m\frac{4M+3}{4M}(T-\sum_{j=1}^{i-1}x_j)\\ &=m\frac{4M+3}{4M}\sum_{i=1} P(T\leq x_i\mid T > x_{i-1})(T-\sum_{j=1}^{i-1}x_j)\\ &=m\frac{4M+3}{4M}(T\sum_{i=1} P(T\leq x_i\mid T > x_{i-1})-\sum_{i=1}P(T\leq x_i\mid T > x_{i-1})\sum_{j=1}^{i-1}x_j))\\ \end{align}$

Note that $x_i$ ranges from $0$ to $M$, both included and always increasing. Therefore, $\sum_{i=1} P(T\leq x_i\mid T > x_{i-1})=1$.

That means that we simply have to look for the $\vec x$ such that minimizes $\sum_{i=1}P(T\leq x_i\mid T > x_{i-1})\sum_{j=1}^{i-1}x_j))$

But note that since $T\sim U(0,M)$, $P(T\leq x_i\mid T > x_{i-1})=\frac{x_i-x_{i-1}}{M-x_{i-1}}$. So we want to minimize $\sum_{i=1}\frac{x_i-x_{i-1}}{M-x_{i-1}}\sum_{j=1}^{i-1}x_j))$

For the following, $I$ will be the last index of $\vec x$ and, as stated before, $x_I=T$. $\begin{align} f(\vec x)&=\sum_{i=1}^I\frac{x_i-x_{i-1}}{M-x_{i-1}}\sum_j^{i-1}x_j= \sum_{i=1}^I\sum_{j=1}^{i-1}\frac{x_i-x_{i-1}}{M-x_{i-1}}x_j= \sum_{i=1}^I\sum_{j=1}^{i-1}\frac{x_ix_j}{M-x_{i-1}}-\frac{x_{i-1}x_j}{M-x_{i-1}}\\ f_{x_n}(\vec{x})&= \end{align}$

Now making this derivative is the only remaining point, but should be the easiest

$\endgroup$
  • $\begingroup$ Thanks for your response! I'm trying to solve the cost function Bey proposed, but looking forward to any other suggestions as well $\endgroup$ – user2045279 Jun 3 '15 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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