House-Hunting Without Second Moments

摘要

In the house-hunting problem, i.i.d. random variables, X_1,X_2,... are observed sequentially at a cost of c > 0 per observation. The problem is to choose a stopping rule, N, to maximize E(X_N - Nc). If the X's have a finite second moment, the optimal stopping rule is N~* = min{n ≥ 1 : X_n > V~*}, where V* satisfies E(X - V~*)~+ = c. The statement of the problem and its solution requires only the first moment of the X_n to be finite. Is a finite second moment really needed? In 1970, Herbert Robbins showed, assuming only a finite first moment, that the rule N~* is optimal within the class of stopping rules, N, such that E(X_N - Nc)~- > - ∞, but it is not clear that this restriction of the class of stopping rules is really required. In this article it is shown that this restriction is needed, but that if the expectation is replaced by a generalized expectation, N~* is optimal out of all stopping rules assuming only first moments.