Ratio Prophet Inequalities for the General S_n Problem

摘要

For any sequence (X_1,..., X_N) of random variables taking values in [0, 1], let S_n:=∑ from i=1 to n of X_i, n=1,...,N, M(S_1/1,..., S_N/N) : = E(max_(n=1,...,N)S_n) and V(S_1/1,...,S_N /N):= sup_(τ∈T) E(S_τ/τ), where T denotes the set of stopping rules for (X_1,..., X_N). It is shown that M(S_1/1,..., S_N/N) ≤ (∑ from i=1 to N of 1/i) • V(S_1/1,..., S_N/N).