Sequential selection of random vectors under a sum constraint

DOI10.1239/JAP/1077134673MaRDI QIDQ4819442zbMATH OpenOpenAlexFDO

Authors Mario Stanke

Publication date 24 September 2004

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/29371fcba778bbf76e8a7bd29f2ddeeeb18d47a9, https://resolver.sub.uni-goettingen.de/purl?gro-2/48714

zbMATH Keywords

online selectionsum constraintthreshold region

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40) Sums of independent random variables; random walks (60G50) Optimal stopping in statistics (62L15)

Review text

An i.i.d. sequence of coordinatewise nonnegative \(d\)-dimensional random vectors \(X_1,X_2,\dots, X_n\) is sequentially observed. When a certain random vector is observed it can be either selected or rejected but once made this decision is final. In each coordinate the sum of the selected vectors must not exceed one. The problem is to find a selection policy maximizing the expected number of selected vectors. Let \(\text{Opt}_n(\mu)\) denote the maximum (depending on the distribution \(\mu\) of \(X_1\)) and let \(\text{Proph}_n(\mu)\) denote the maximum a ``prophet (knowing the whole sequence in advance) can achieve. Clearly \(\text{Opt}_n(\mu)< \text{Proph}_n(\mu)\). The author studies the case of an absolutely continuous distribution \(\mu\). He obtains a selection policy (for which the expected number \(E_n(\mu)\) is achieved) being asymptotically optimal in the sense that \[ E_n(\mu)\sim \text{Opt}_n(\mu)\sim \text{Proph}_n(\mu)\sim n\mu(\Delta)\qquad (n\to\infty). \] Here, \(\mu(\Delta)\) denotes a positive constant depending on \(\mu\).

Recommendations

• A note on the selection of random variables under a sum constraint
• scientific article; zbMATH DE number 67294
• scientific article; zbMATH DE number 1959613
• Optimal Sequential selection of n random variables under a constraint
• Optimal selection of stochastic intervals under a sum constraint

Cites work

• A note on the selection of random variables under a sum constraint
• scientific article; zbMATH DE number 1959613 (Why is no real title available?)
• scientific article; zbMATH DE number 3281211 (Why is no real title available?)
• Optimal selection of stochastic intervals under a sum constraint
• Optimal Sequential Selection of Secretaries
• Resource constrained scheduling as generalized bin packing

Cited in

(5)

• The BRS-inequality and its applications
• Optimal Sequential selection of n random variables under a constraint
• A note on the selection of random variables under a sum constraint
• scientific article; zbMATH DE number 1959613 (Why is no real title available?)
• Optimal selection of stochastic intervals under a sum constraint

This page was built for publication: Sequential selection of random vectors under a sum constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4819442)