The Bruss-Robertson Inequality: Elaborations, Extensions, and Applications

• Autorzy: Steele, J. M.

Warianty tytułu

PL

Nierówność Brussa-Robertsona: modyfikacje, rozszerzenia i zastosowania

• Języki publikacji: EN

Abstrakty

EN

The Bruss-Robertson inequality gives a bound on the maximal number of elements of a random sample whose sum is less than a specified value. The extension of that inequality which is given here neither requires the independence of the summands nor requires the equality of their marginal distributions. A review is also given of the applications of the Bruss-Robertson inequality, especially the applications to problems of combinatorial optimization such as the sequential knapsack problem and the sequential monotone subsequence selection problem.

PL

Nierówność Bruss-Robertson szacuje maksymalną liczbę elementów w próbie, której suma jest ograniczona przez zadaną liczbę. Uogólnienia tej nierówności podane w tej pracy nie wymagają założenia niezależności składników sumy ani tego, by były o tym samym rozkładzie. Podano także przegląd zastosowań nierówności Brussa-Robertsona, a zwłaszcza zastosowania do problemów kombinatorycznych, takich jak sekwencyjny problem upakowania i wybór monotonicznego podciągu.

Słowa kluczowe

PL

nierówności dla statystyk rangowych; sekwencyjny problem upakowania; wybór sekwencyjny; markowski problem decyzyjny; proces gałązkowy; równanie Bellmana

EN

order statistical inequalities; sequential knapsack problem; sequential monotone subsequence problem; sequential selection; online selection; Markov decision problems; resource dependent branching processes; Bellman equation

• Czasopismo: Mathematica Applicanda
• Rocznik: 2016
• Tom: Vol. 44, No. 1
• Strony: 3--16
• Opis fizyczny: Bibliogr. 16 poz., fot.

Twórcy

autor

Steele, J. M.

• The Wharton School, University of PeDigital Object Identifier (DOI): 10.14708/ma.v44i1.817nnsylvania, Department of Statistics, 3730 Walnut Street, Philadelphia, PA, 19104, U.S.A.,

Bibliografia

• [1] Arlotto, A., Mossel, E. and Steele, J. M. [2015], ‘Quickest online selection of an increasing subsequence of specified size’, to appear in Random Structures and Algorithms (eprint arXiv:1412.7985) .
• [2] Arlotto, A., Nguyen, V. V. and Steele, J. M. [2015], ‘Optimal online selection of a monotone subsequence: a central limit theorem’, Stochastic Process. Appl. 125(9), 3596–3622.
• [3] Baik, J., Deift, P. and Johansson, K. [1999], ‘On the distribution of the length of the longest increasing subsequence of random permutations’, J. Amer. Math. Soc. 12(4), 1119–1178. doi: 10.1090/S0894-0347-99-00307-0 URL: http://dx.doi.org/10.1090/S0894-0347-99-00307-0
• [4] Boshuizen, F. A. and Kertz, R. P. [1999], ‘Smallest-fit selection of random sizes under a sum constraint: weak convergence and moment comparisons’, Adv. in Appl. Probab. 31(1), 178–198. doi: 10.1239/aap/1029954272 URL: http://dx.doi.org/10.1239/aap/1029954272
• [5] Bruss, F. T. [2014], ‘Grenzen einer jeden Gesellschaft’, Jahresber. Dtsch. Math.-Ver. 116(3), 137–152. doi: 10.1365/s13291-014-0097-3 URL: http://dx.doi.org/10.1365/s13291-014-0097-3
• [6] Bruss, F. T. and Delbaen, F. [2001], ‘Optimal rules for the sequential selection of monotone subsequences of maximum expected length’, Stochastic Process. Appl. 96(2), 313–342.
• [7] Bruss, F. T. and Delbaen, F. [2004], ‘A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length’, Stochastic Process. Appl. 114(2), 287–311.
• [8] Bruss, F. T. and Duerinckx, M. [2015], ‘Resource dependent branching processes and the envelope of societies’, Ann. Appl. Probab. 25(1), 324–372. doi: 10.1214/13-AAP998 URL: http://dx.doi.org/10.1214/13-AAP998
• [9] Bruss, F. T. and Robertson, J. B. [1991], “Wald’s lemma” for sums of order statistics of i.i.d. random variables’, Adv. in Appl. Probab. 23(3), 612–623.
• [10] Coffman, Jr., E. G., Flatto, L. and Weber, R. R. [1987], ‘Optimal selection of stochastic intervals under a sum constraint’, Adv. in Appl. Probab. 19(2), 454–473.
• [11] Gnedin, A. V. [1999], ‘Sequential selection of an increasing subsequence from a sample of random size’, J. Appl. Probab. 36(4), 1074–1085.
• [12] Gribonval, R., Cevher, V. and Davies, M. E. [2012], ‘Compressible distributions for high-dimensional statistics’, IEEE Trans. Inform. Theory 58(8), 5016–5034. doi: 10.1109/TIT.2012.2197174 URL: http://dx.doi.org/10.1109/TIT.2012.2197174
• [13] Pólya, G. [1917], ‘ Über eine neue Weise bestimmte Integrale in der analytischen Zahlentheorie zu gebrauchen’, Nachr. Ges. Wiss. Göttingen pp. 149–159.
• [14] Rhee, W. and Talagrand, M. [1991], ‘A note on the selection of random variables under a sum constraint’, J. Appl. Probab. 28(4), 919–923.
• [15] Romik, D. [2014], The Surprising Mathematics of Longest Increasing Subsequences, Cambridge University Press, Cambridge.
• [16] Samuels, S. M. and Steele, J. M. [1981], ‘Optimal sequential selection of a monotone sequence from a random sample’, Ann. Probab. 9(6), 937–947.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.

Identyfikatory

DOI

10.14708/ma.v44i1.817