Question

Problem 5.10.10

Suppose you have n suitcases and suitcase i holds X_i dollars where X₁, X₂, …, X_n are iid continuous uniform (0, m) random variables. (Think of a number like one million for the symbol m.) Unfortunately, you don’t know X_i until you open suitcase i.

            Suppose you can open the suitcases one by one, starting with suitcase n and going down to suitcase 1. After opening suitcase i, you can either accept or reject X_i dollars. If you accept suitcase i, the game ends. If you reject, then you get to choose only from the still unopened suitcases.

            What should you do? Perhaps it is not so obvious? In fact, you can decide before the game on a policy, a set of rules to follow. We will specify a policy by a vector (t₁, … t_n) of threshold parameters.

• After opening suitcase i, you accept the amount X_i if X_i≥t_i .
• Otherwise, you reject suitcase i and open suitcase i-1.
• If you have rejected suitcases n down through 2, then you must accept the amount X₁ in suitcase 1. Thus the threshold t₁=0 since you never reject the amount in the last suitcase.

1. Suppose you reject suitcase n through i+1, but then you accept suitcase i. Find E[X_i|X_i≥ t_i ].
2. Let W_k denote your reward given that there are k unopened suitcases remaining. What is E[W₁]?
3. As a function of t_k, find a recursive relationship for E[W_k] in terms of t_k and E[W_k-1].
4. For n=4 suitcases, find the policy (t₁^*, … t₄^*) that maximizes E[W₄].

Answer 1