Recognizing the MINIMUM of a sequence i am currently reading and working with the book "Recognizing the maximum of a sequence" from John Gilbert and Frederick Mosteller. It describes different styles of the dowry game and how to obtain an optimal rule on how to play it. I am working with a full-information dowry game. The authors give a recursive formula to calculate the expected score after each draw like so (page 34/40 in the book or section 5b):
$$R_{n+1}=\int_{R_n}^\infty xf(x)dx +R_n\int_{-\infty}^{R_n}f(x)dx$$
Now my question is, how would i want to change the formula if my goal is not to maximize but minimize the expected score. I came up with the idea to change the formula like so:
$$R_{n+1}=\int_{-\infty}^{R_n}xf(x)dx+R_n\int_{R_n}^{\infty}f(x)dx$$
Since the first integral is the expected value $E(X|X_n\lt R_n)$ and the second integral is the weighted probability to reject the card when it doesnt suffice $X_n\lt R_n$. At least this is my thought process. What do you guys think about it?
I am not a mathematician by the way so bear with me if i use wrong notation or got mixed up with some words.
 A: This is a stochastic dynamic programming problem.
In the $n$-th period, the person draws a card. The expected value is $ \mathbb{E}[V_n] = \int_{-\infty}^\infty x f(x) dx$.
In the $n-1$-st period, the person draws a card; let its value be $x_{n-1}$. Then the decision of whether to discard it and draw again is determined by
$$
V_{n-1}(x_{n-1}) = \min \{ x_{n-1}, \mathbb{E}[V_n] \}.
$$
So he keeps the current card if $x_{n-1} \le \int_{-\infty}^\infty x f(x) dx $. Then
$$
\mathbb{E}[V_{n-1}(x_{n-1})] = \int_{-\infty}^{\mathbb{E}[V_n]} x f(x)dx + \int_{\mathbb{E}[V_n]}^\infty \mathbb{E}[V_n] f(x)dx,
$$
or
$$
\mathbb{E}[V_{n-1}] = \int_{-\infty}^{\mathbb{E}[V_n]} x f(x)dx + (1-F(\mathbb{E}[V_n]))\mathbb{E}[V_n].
$$
You could probably integrate by parts and simplify further.
Continuing the backwards induction,
$$
V_t(x_t) = \min \{x_t, \mathbb{E}[V_{t+1}] \}
$$
and
$$
\mathbb{E}[V_t] = \int_{-\infty}^{\mathbb{E}[V_{t+1}]} xf(x)dx + \int_{\mathbb{E}[V_{t+1}]}^\infty \mathbb{E}[V_{t+1}]f(x)dx
$$
or
$$
\mathbb{E}[V_t] = \int_{-\infty}^{\mathbb{E}[V_{t+1}]} xf(x)dx +(1-F(\mathbb{E}[V_{t+1}]))\mathbb{E}[V_{t+1}].
$$
Integrating by parts doesn't seem to simplify things in a useful way, but maybe if you had a parametric expression for $F$, it would?
If you look at the $t$-th period expectation, you get
$$
\mathbb{E}[V_t] = \int_{-\infty}^{\mathbb{E}[V_{t+1}]} xf(x)dx +(1-F(\mathbb{E}[V_{t+1}]))\mathbb{E}[V_{t+1}] <\int_{-\infty}^{\mathbb{E}[V_{t+1}]} \mathbb{E}[V_{t+1}]f(x)dx +(1-F(\mathbb{E}[V_{t+1}]))\mathbb{E}[V_{t+1}] = \mathbb{E}[V_{t+1}]
$$
so that $\mathbb{E}[V_{t}] < \mathbb{E}[V_{t+1}]$. But without discounting, I doubt that there's a fixed point to the iteration process? I have a feeling you would just keep drawing forever as $n \rightarrow \infty$ unless there is a cost of drawing cards, or impatience on the part of the decision-maker. Then you would have a stopping time rule, like, "the first time $x<.125$, stop."
This is Discrete Time Dynamic Programming, and the value function iterations above are typically called Bellman Equations.
