1
$\begingroup$

Suppose a food court has two areas. In Area $1$ you will receive food at a rate of $0,2$ food per seconds. In Area $2$ you will receive food at a rate of $1$ food per seconds. While being in Area $2$, you have a probability of getting kicked out of the food court with probability $p > 0$ per seconds. If kicked out you cannot return to any of the areas. Say you have $10$ minutes, and want to optimize the amount of food gained. How do you distribute your time between the two areas? Should you ever switch from one area to the other? When and how often?

The answer depends on $p$.

$\endgroup$
4
  • $\begingroup$ there is no $k$ in the problem. Does $k=p$? $\endgroup$
    – lulu
    Commented Apr 28, 2017 at 13:00
  • $\begingroup$ I don't think this is clear. If I am kicked out in the first second, can I return in the next second? Can I be kicked out the same second I arrive? $\endgroup$
    – lulu
    Commented Apr 28, 2017 at 13:01
  • $\begingroup$ You are correct. See edit. $\endgroup$ Commented Apr 28, 2017 at 13:01
  • $\begingroup$ A brief note: Any solution or expected value $E(x)$ that results in gaining 120 food or less cannot be considered, because if you spend the full 10 minutes in Area 1 you will get $0.2$ food/second * $600$ seconds = 120 food. $\endgroup$
    – Toby Mak
    Commented Apr 28, 2017 at 13:10

3 Answers 3

2
$\begingroup$

Suppose you decide to stay $n$ seconds in Area 2. Your best strategy is to spend those seconds after staying $600-n$ seconds in Area 1, because after you are being kicked out, you can't go back.

So you will get $0.2\times(600-n$ food from Area 1. Then, in Area 2, you'll get $0$ food with probability $p$ (you are immediately kicked out), $1$ food with probability $qp$ ($q=1-p$, you are kicked after 1 second), ... $k$ food with probability $q^kp$, $n-1$ food with probability $q^{n-1}p$, and $n$ food with probability $q^n$.

So your expected gain with this strategy is : \begin{align}E_n &=120-0.2n+qp+2q^2p+\dots+(n-1)q^{n-1}p+nq^n \\ &= 120-0.2n + pq(1+2q+\dots+(n-1)q^{n-2})+nq^n\end{align} Now $$1+2q+\dots+(n-1)q^{n-2}=(1+q+q^2+\dots+q^{n-1})'=\left(\frac{1-q^n}{1-q}\right)'=\frac{(n-1)q^n-nq^{n-1}+1}{(1-q)^2}$$ So, if my math is right : $$E_n=120-0.2n+\frac{(2n-1)q^{n+1}+1}{1+q}$$ Let's study this function of $n$ : $$E_n'=-0.2+\frac{q^{n+1}}{1+q}(2+\ln q)$$ This derivative cancels when $$q^{n+1}=\frac{0.2(1+q)}{2+\ln q}$$ i.e. $$n=\frac1q\ln\left(\frac{0.2(1+q)}{2+\ln q}\right)$$ Can't go much further, I'm afraid...

$\endgroup$
5
  • $\begingroup$ I often suspect that a discrete approch makes life harder. Moreover there are techniques developed for reliability engineering (such as "reliability function" and"failure rate") that are perfectly suited for this case. @Nicolas $\endgroup$
    – lesath82
    Commented Apr 28, 2017 at 21:15
  • $\begingroup$ @lesath82 : my approach is one of a non specialist. The way the question was asked, I assumed a discrete approach was required. But you're right, my assumption may be wrong. $\endgroup$ Commented Apr 29, 2017 at 9:23
  • $\begingroup$ @user2552936 : BTW, neither approach seems to suit the OP, he didn't comment or upvote any of our answers. And in view of the length of all those answers, we spent quite some time on them :-( $\endgroup$ Commented Apr 29, 2017 at 9:26
  • $\begingroup$ I took this as a chance to review topics I'm sopposed to know, but you're right: let's hope he comes back and let us know if he received what he needed. In the meanwhile I've upvoted yours, it's deserved, if only for the effort! $\endgroup$
    – lesath82
    Commented Apr 29, 2017 at 11:02
  • $\begingroup$ I'm sure I tagged you in my comment, but I cannot see the tag! @Nicolas $\endgroup$
    – lesath82
    Commented Apr 29, 2017 at 11:34
2
$\begingroup$

I agree with some of the observations already done, but I disapprove the discrete approach so I'll follow a continous one.

If there is a moment when it is convenient to be in Area $2$, than it won't ever be convenient to go (back) to Area $1$: time spent in Area $1$ will always be more beneficial if spent before any time spent in Area $2$, where you risk being kicked out. Let's call $\Delta t_2$ the time interval that might be convenient to try spending in Area $2$. In such a time interval, Area $1$ would grant a food gain equal to $0.2 \, food/s \cdot \Delta t_2$. I don't like carrying numerical values, so I'll call $g_1 = 0.2 \,food/s$ and $g_2 = 1 \,food/s$, moreover $T = 600 \,s$. Now we have to evaluate the expected food gain in Area $2$ and maximize the difference.

I'm going to call $\tau$ the time spent in Area $2$, that is $\tau = t - \Delta t_1$. In Area $2$ there is a constant kick-out rate (probability per unit time), thus we have an exponential kick-out probability density function $f(\tau) = pe^{-p\tau}$. The expected survival time $E[\tau]$ ia evaluated as follows:

$$ \begin{align} E[\tau]&=\int_0^{\Delta t_2}\tau \cdot p e^{-p\tau} d\tau + \Delta t_2 \cdot \int_{\Delta t_2}^\infty p e^{-p\tau}d\tau=\\ &=\left[\tau(-e^{-p\tau}) \right]_0^{\Delta t_2}-\int_0^{\Delta t_2}(-e^{-p\tau}) d\tau \;-\Delta t_2\cdot \left[e^{-p\tau} \right]_{\Delta t_2}^\infty=\\ &=-\Delta t_2 \, e^{-p\Delta t_2} \;- \left[\frac{1}{p}\cdot e^{-p\tau} \right]_0^{\Delta t_2} \; + \Delta t_2 \, e^{-p\Delta t_2}=\\ &=-\frac{1}{p}\cdot e^{-p\Delta t_2}+\frac{1}{p}=\\ &=\frac{1}{p}\left(1-e^{-p\Delta t_2}\right) \end{align} $$

Let's check for correct limits: $$ \begin{align} p\rightarrow 0 &\Rightarrow E[\tau]\rightarrow \Delta t_2\\ p\rightarrow \infty &\Rightarrow E[\tau]\rightarrow 0\\ \end{align} $$

It's time to assess the food gain increment (note that $G_1$ is not the food gained during the first time interval, but what would be gained staying in Area $1$ during $\Delta t_2$): $$ \begin{align} \Delta G = G_2-G_1 &= g_2 \cdot \frac{1}{p}\left(1-e^{-p\Delta t_2}\right) - g_1 \cdot\Delta t_2\\ \frac{\Delta G\cdot p}{g_2} &= 1-e^{-p\Delta t_2} - \frac{g_1}{g_2} \cdot p\Delta t_2\\ y &= 1 - e^{-x} - \frac{g_1}{g_2} \cdot x\\ \end{align} $$ where the last line follows a substitution of variables to underline the function that has to be maximized. Note that $y(0)=0$ and that $y(x)$ is positive up to a certain value of $x$, so that we are sure to encounter a maximum. So,

$$ y'= e^{-x}-\frac{g_1}{g_2} \\ $$ $$ \begin{align} y'\geqslant 0 \iff& e^{-x}\geqslant\frac{g_1}{g_2}\\ &-x\geqslant \ln \frac{g_1}{g_2}\\ &\;\; x\leqslant \ln \frac{g_2}{g_1}\\ \end{align} $$ Finally, $t^* = T-\Delta t_2 = T-\frac{1}{p} \ln \frac{g_2}{g_1}$ is the ideal time to move to Area $2$, provided that $g_2 \gt g_1$, otherwise it woudn't obviously be convenient to ever switch to Area $2$. At the opposite extreme, if $ \Delta t_2 \gt T$, the best strategy is to spend all the time in Area $2$.

With the actual values of the question, we have $t^* = 600 \, s - 1/p * \ln\frac{1}{0.2}$ and it would be beneficial to start in Area $2$ since the beginning whenever $p\leqslant 2.68 \cdot 10^{-3} \, s^{-1}$.

$\endgroup$
1
$\begingroup$

Given s remaining seconds consider the EV of

Stay in area 1: $s*0.2$

Spend 1 second in area 2 then stay in area 1: $(1-p)*(1+(s-1)*0.2)$

We should preference the strategy which maximizes the EV and must reconsider this choice for each passing second.

For example: evaluate at s=600, choose best option, evaluate at s=599, choose best option, evaluate at s=598, choose the best option...

Intuitively we recognize strategy 1 favors larger s while strategy 2 favors smaller s. Because s is always decreasing it follows that should we ever reach a point where strategy 2 is favored it will remain favored for the remainder of the duration.

Both strategies will yield the same EV when

$s*0.2 = (1-p)*(1+(s-1)*0.2)$

$s= 4/p-4$

So, we should stay in area 1 until $4/p-4$ remaining seconds and then switch to area 2.

Notice that if p is sufficiently large we should never switch to area 2. Conversely if p is sufficiently small we might begin (and remain) at area 2 for the entire duration.

$\endgroup$
1
  • $\begingroup$ I'll repeat here that I don't like discretizing problems like this, yet I like the idea underlying of your reasoning. I could also translate it in continous terms getting (using the variables defined in my answer) Delta_t_2 = (1-p*dt)/p * (g_2 - g_1)/g_1 -> 1/p * (g_2 - g_1)/g_1 = 4/p, consistent with yours apart that it will always be convenient to go spending at least a fraction of a second in Area 2. The fact is that nothing that guarantees that this beneficial strategy is the optimal one! You are moving to Area 2 too soon! $\endgroup$
    – lesath82
    Commented Apr 29, 2017 at 8:33

You must log in to answer this question.

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