Maximum Expected Fishing Day (Recurrence Relation)

Question

John joined a meetup where organize day long fishing trip once a month. The organizers are vary poor at planning, so will organize fishing on a random day of the month without any advance notice. Sadly, John needs to inform his boss in order to get time off from work at least a day in advance. With this situation, John is forced to schedule vacation days and hopping that the fishing will take place on them. At the same time, he can be strategic about it. For instance, he can wait until the end of the month at which point the fishing would have already happened or will guarantee to occur the next day. John can use a total of v day of vacation for the next m months. What is the greatest expected number of fishing meetup that he can arrange to attend? For simplification, we can assume that a month is only 30 days longs.

It can be approached as: Defining the sub-problems as Maximum Expected Fishing Days MEFD: for every situation MEFD(m,d,v), where m is the number of months left including the current month, d is the numbers of days left in the current one, and v is the number of vacation days john left with the assumption that the fishing has not took place in the current month.

Base case: for any (m,d,v) such that i, j or l equals to 0, MEFD(m,d,v) =0

Recurrence Relation: MEFD(m,d,v) = max(MEFD$_{1}$(m,d,v), MEFD$_{2}$(m,d,v))

MEFD$_{1}$(m,d,v)=$\frac{1}{d}$(1+MEFD(m-1,30,v-1))+ $\frac{d-1}{d}$MEFD(m-1,d-1,v),

MEFD$_{2}$(m,d,v)=$\frac{1}{d}$(1+MEFD(m,30,v-1))+ $\frac{d-1}{d}$MEFD(m,d-1,v).

What does $\frac{1}{d}$ or $\frac{d-1}{d}$ means? Why do we need to multiply them ? Let's MEFD$_{1}$ means that the Maximum Expected Fishing Day that John takes a vacation day off in the next day. then it would fall into two cases: 1, fishing meetup take place, 2, it didn't take place. As we can tell from MEFD$_{1}$, 1 + ing means fishing meetup take place, then we - 1 from the months left and - 1 from vacations left.

What do we also need to -1 from months and vacations of the second part of the equation, + $\frac{d-1}{d}$MEFD(m-1,d-1,v)?

Or am i am reading this recurrence relation completely wrong? any points are really appreciated.

Answer 1

Although the subproblems are defined correctly in the approach quoted in the question, there are some typos and glitches when it comes to the base cases and recurrence relations.

Please see the corrected base cases and recurrence relations below.

---

Base case: for any $(m,d,v)$ such that $m$, $d$ or $v$ equals to 0, $$\text{MEFD}(m,d,v) =0\tag{R0}$$

Recurrence Relations: $$\begin{align*} \text{MEFD}(m,d,v) &= \max(\text{MEFD}_{1}(m,d,v), \text{MEFD}_{2}(m,d,v))\tag{R1}\\ \text{MEFD}_{1}(m,d,v)&=\frac{1}{d}(1+\text{MEFD}(m-1,30,v-1))\\&+\frac{d-1}{d}\text{MEFD}(m,d-1,v-1)\tag{R2}\\ \text{MEFD}_{2}(m,d,v)&=\frac{1}{d}\text{MEFD}(m-1,30,v))\\&+\frac{d-1}{d}\text{MEFD}(m,d-1,v)\tag{R3} \end{align*}$$

Equation (R1) says that the maximum expected fishing days is the larger of the expected fishing days yielded by two strategies, John selects the next day and John does not select the next day. John will proceed with the best strategy in the remaining days.

Equation (R2) compute the maximum expected finishing days when John has selected the next day. The probability that the next day will be a fishing day is $\frac1d$, in which case John will proceed with the best strategy for the remaining $m-1$ months and $v-1$ vacations day. The probability that the next day will not be a fishing day is $\frac{d-1}d$, in which case John will proceed with the best strategy for the remaining $d-1$ day and $v-1$ vacation days.

Equation (R3) compute the maximum expected finishing days when John has decided to work for the next day. The probability that the next day will be a fishing day is $\frac1d$, in which case John will proceed with the best strategy for the remaining $m-1$ months and $v$ vacations day. The probability that the next day will not be a fishing day is $\frac{d-1}d$, in which case John will proceed with the best strategy for the remaining $d-1$ day and $v$ vacation days.

Note "John needs to inform his boss in order to get time off from work at least a day in advance" is interpreted as something like if John wants to take tomorrow off, he can just inform his boss tonight, at which time he must have known whether today is a fishing day. If it is, he will not, of course, select any remaining day in the current month as a vacation day. That is why whenever the next day will be a fishing day, we will only consider the remaining $m-1$ months in the above recurrence relations.