Optimal Stopping for Selling Under a Martingale Price Assumption

# A quant job interview question about (toy) futures


# A quant job interview question about (toy) futures












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}$

or

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

or

- 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...

## Answer by Rylan (score 2)

https://quant.stackexchange.com/a/79706

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.

## Answer by mark leeds (score 1)

https://quant.stackexchange.com/a/79726

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