Ratio prophet inequalities when the mortal has several choices
成果类型：
Article
署名作者：
Assaf, D; Goldstein, L; Samuel-Cahn, E
署名单位：
Hebrew University of Jerusalem; University of Southern California
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
发表日期：
2002
页码：
972-984
关键词：
摘要：
Let X-i be nonnegative, independent random variables with finite expectation, and X-n* = max{X-1, ..., X-n}. The value EXn* is what can be obtained by a prophet. A mortal on the other hand, may use k greater than or equal to I stopping rules t(1), ..., t(k), yielding a return of E[max(i=1), ..., k X-ti]. For n greater than or equal to k the optimal return is V-k(n) (X-1, ..., X-n) = sup E[max(i=1) ,..., k X-ti] where the supremum is over all stopping rules t(1), ..., t(k) such that P(t(i) less than or equal to n) = 1. We show that for a sequence of constants g(k) which can be evaluated recursively, the inequality EXn* < 9(k) V-k(n)(X-1, ..., X-n) holds for all such X-1, ..., X-n and all n greater than or equal to k; g(1) = 2, g(2) = 1 + e(-1) = 1.3678 ..., g(3) = 1 + e(1-e) = 1. 1793 .... g(4) = 1.0979 ... and g(5) = 1.0567 ... Similar results hold for infinite sequences X-1, X-2, ....