On Monday, you receive prices for each day of the week: $X_{1,1}, \ldots, X_{1,5}$.

On Tuesday, you receive prices for Tuesday, Wednesday, Thursday, and Friday: $X_{2,2}, \ldots, X_{2,5}$.

On Wednesday, you receive prices for Wednesday, Thursday, and Friday: $X_{3,3}, \ldots, X_{3,5}$.

On Thursday, you receive prices for Thursday and Friday: $X_{4,4}, X_{4,5}$.

On Friday, you receive the price for Friday: $X_{5,5}$.

You have a product to sell, and you want to sell it on any day but at the best price.

On Monday, you can:

  • sell it at $X_{1,1}$


  • commit to selling it later, on Tuesday at $X_{1,2}$, ..., on Friday at $X_{1,5}$


  • wait to make a decision.

Obviously, on Tuesday, the same process starts again and this continues until Friday, and there you must sell it at $X_{5,5}$ if you haven't sold it yet.

Assuming that $X_{i,j}$ for fixed $j$ is a martingale (you can specify the distribution that suits you to simplify computations), how do you find the best strategy?

The Bellman equation is easy to write but I found no distribution that would simplify the computation. How to proceed except numerically. The recursive equation (Bellman) is:

$v_5(x_{5,5}) = x_{5,5}$

and for $n \in \{1, \ldots, 4\}$:

$v_n(x_{n,n}, \ldots, x_{n,5}) = \max(x_{n,n}, \ldots, x_{n,5}, \mathbb{E}[v_{n+1}(x_{n,n+1} + \epsilon_{n,n+1}, \ldots, x_{n,5} + \epsilon_{n,5})])$ for some independent noises.

We easily get $v_4(x_{4,4}, x_{4,5}) = \max(x_{4,4}, x_{4,5})$, but, then, no clue to go to $v_3$, $v_2$ and eventually $v_1$

The next question was about the same problem over a month... Smells like curse of dimensionality...

  • $\begingroup$ Can you please add your proposed solution? Also: What about preferences: risk neutrality? And what about discounting: risk free rate equal to zero? $\endgroup$ Commented Jun 11 at 9:07
  • $\begingroup$ risk neutrality I believe and no discounting. $\endgroup$
    – Aristodog
    Commented Jun 11 at 11:30
  • $\begingroup$ I took the liberty of adding your extensions as text to your original question. $\endgroup$ Commented Jun 11 at 12:26

2 Answers 2


I gave this problem an attempt, but I'm very rusty. All comments and corrections are appreciated.

For random variables we use, let's just assume they're nice and have finite expectation and variance.

$v_5(x) = x$ as you said.

$v_4(x, y) = \max(x, y, \mathbb{E}(v_{5}(x_{5, 5})| x_{4, 5} = y) = \max(x, y)$ (again, as you said).

$v_5$ was linear so it played nicely with expectations and we got something trivial, but $v_4$ is not so it's more complicated.

$v_3(x, y, z) = \max(x, y, z, \mathbb{E}(v_{4}(x_{4, 4}, x_{4, 5})| x_{3, 4}=y, x_{3, 5}=z))$

$= \max(x, y, z, \mathbb{E}(\max(y + \epsilon_1, z + \epsilon_2))$ where $e_i$ are random, zero mean, independent.

Jensen's inequality gives us that $\mathbb{E}(\max(y + \epsilon_1, z + \epsilon_2)) > \max(y, z)$ so the expression simplifies to $v_3(x, y, z) = \max(x, \mathbb{E}(\max(y + \epsilon_1, z + \epsilon_2)))$

$v_2(x, y, z, w) =\max(x, \mathbb{E}( \max(y + \epsilon_y, \mathbb{E}(\max(z + \epsilon_1 + \epsilon_2, w + \epsilon_3 + \epsilon_4)))$

I need to double check myself here but I believe that I can say by the tower property, this gives: (edit: this step is probably a mistake, I need to update the rest of the equation to not do this)

$v_2(x, y, z, w) =\max(x, \mathbb{E}( \max(y + \epsilon_1, z + \epsilon_2 + \epsilon_3, w + \epsilon_4 + \epsilon_5))$

(in other words, the "inner expectation" is subsumed)

And following this (I'm running out of variable letters...)

$v_1(x, y, z, w, t) = \max(x, \mathbb{E}(\max(y + \epsilon_1, z + \epsilon_2 + \epsilon_3, w + \epsilon_4 + \epsilon_5 + \epsilon_6, t + \epsilon_7 + \epsilon_8 + \epsilon_9)))$

(note there is one epsilon associated with the second term, two with the third term, and three with both the fourth and the fifth, just because $v_5$ was linear so the last epsilon was zeroed out by expectation.

If $e_i$ are for example $N(0, 1)$ this gives

$v_1(x, y, z, w, t) = \max(x, \mathbb{E}(\max(y + \epsilon_1, z + \sqrt{2}\epsilon_2, w + \sqrt{3}\epsilon_4, t + \sqrt 3\epsilon_5)))$

and you can then compute that expectation however you like -- it might or might not be numerically challenging.

  • 1
    $\begingroup$ Rylan: It took me a while to follow it but what you did is interesting. What I noticed is that quite a few of the possibilities can be thrown out completely without any calculations. For example, one would never choose a price in a future day so $x_{ij}$ ( referring to the notation used in the definition of the problem ) can never be chosen for $j $ greater than $i$. This is because, if one wanted to choose $j$ on day $i$ for $j$ greater than $i$ then one would just wait until time $j$ because it costs nothing to wait and you gain more information by waiting. $\endgroup$
    – mark leeds
    Commented Jun 14 at 4:57
  • 1
    $\begingroup$ So, the only possible options that one would ever choose are $x_{11}, x_{22}, x_{3,3}, x_{4,4}$ and $x_{5,5}$. This makes the problem much simpler. When I have more time, I'll use this to try to write up a simpler solution. But, definitely I'll give you all the credit because I didn't see where that was going without what you did. $\endgroup$
    – mark leeds
    Commented Jun 14 at 5:01
  • 2
    $\begingroup$ I re-read the problem and, to make my point above clearer, the whole "commit to selling later" option would never be an optimal option no matter what happened in the interim because you lose nothing by waiting and not commiting. $\endgroup$
    – mark leeds
    Commented Jun 14 at 5:04
  • 1
    $\begingroup$ yeah. I tend to think of it as: when I'm at 4, all I can do is go to 5 so x_{4,5} is kind of the same as x_{5,5} because they are both the same "stopping times". So, regardless of $x_{4,5}$ value, it seems like $x_{5,5}$ is not even needed ? What's the difference between $x_{5,5}$ and $x_{4,5}$ really. They both go to 5 and game is over. So something seems redundant-weird at the end, atleast when there is no simpllfication so that only the $i=j$ states are kept. Note that there should be a similar methodology that includes all the states and still arrives at Doob's Optimal Stopping Theorem. $\endgroup$
    – mark leeds
    Commented Jun 14 at 7:51
  • 1
    $\begingroup$ Oh, the other thing I meant to say in the answer is that, if the question is extended to a month ( OP mentioned that at the end of his question ) then nothing changes. It still doesn't matter when you decide to stop. $\endgroup$
    – mark leeds
    Commented Jun 14 at 7:57

First, the majority of this answer is due to Rylan whose answer gave me the idea of reducing the number of states to 5. This then allowed me to avoid the use of Bellman's equation which is probably overkill for the simplified version of the problem.

Because of the simplification that I discussed in the comment, there are only 5 states in the problem where each state corresponds to the $ith$ day of the week. As far as the prices, we will let

$$ p_{1} = mon~~ price $$ $$ p_{2} = tues~~ price $$ $$ p_{3} = wed~~ price $$ $$ p_{4} = thurs~~ price $$ $$ p_{5} = fri~~ price $$

Since $p_{i}$ is assumed to be a martingale, we will assume that $p_{i+1} = p_{i} + \epsilon_{i+1} $ where $\epsilon_{i+1}~\sim~ N(0,1)$.

Then, clearly $E(p_{i+1}) = p_{1} ~\forall~ i = 1,2,3,4$

Also, we will let $s_{i} = 1$ if one chooses to stop at price $i$ and select it as the sell price. Otherwise, $s_{i} = 0$.

Clearly, to maximize the value of the strategy, one wants to make the best choice of when to stop. This means that the goal is to $max \left(E\left(\sum_{i=1}^{5}s_{i} p_{i}\right)\right)$

But $max \left(E\left(\sum_{i=1}^{5}s_{i} p_{i}\right)\right) = max \left(\sum_{i=1}^{5}s_{i} E(p_{i})\right) = max \left(\sum_{i=1}^{5}s_{i} p_1\right) $

The last equality in the last line above is because $E(p_{i}) = p_{1}$ which is due to $p_{i}$ being a martingale. Since the expression being maximized is independent of future prices then, in order to maximize that expression, it doesn't matter when one stops. Any chosen $i$ will result in the same expectation so there is nothing to maximize. The maximum of the expectation is obtained no matter what $i$ is chosen.

This question was mostly likely given because it demonstrates the discrete version of Doob's optimal stopping theorem. The link gives a very nice explanation and proof. https://math.dartmouth.edu/~pw/math100w13/lalonde.pdf

  • $\begingroup$ $p_i$ is not a martingale. Monday and Tuesday prices are independent. $\endgroup$
    – Aristodog
    Commented Jun 14 at 8:49
  • $\begingroup$ Hi Aristodog: I took the martingale description about fixed "j" to mean that ( in my notation, where I just have 5 states ), $E_{i}(p_{i+1}) = p_{i}$ where $p_{i}$ denotes the existing price on the ith day and the expectation is taken on the ith day. I'm not clear on what martingale you took it to be ? Thanks for more details. $\endgroup$
    – mark leeds
    Commented Jun 14 at 14:49
  • $\begingroup$ Note that the price process starts on monday and ends on friday and there's no other price process that I'm aware of besides that one travelling from one day to the next. So, the martingale that the question refers to, although poorly worded for sure, has to be referring to the prices on each day, $p_{i}$, where $i = 1, \ldots 5$ ( usng my single subscript notation ) $\endgroup$
    – mark leeds
    Commented Jun 14 at 14:59

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.