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

Steele, J. M.

doi:10.14708/ma.v44i1.817

Powiadomienia systemowe

Sesja wygasła!

Artykuł - szczegóły

Tytuł artykułu

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

Autorzy

Steele J. M.

Wybrane pełne teksty z tego czasopisma

http://wydawnictwa.ptm.org.pl/index.php/matematyka-stosowana/

Identyfikatory

DOI

10.14708/ma.v44i1.817

Warianty tytułu

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

Języki publikacji

Abstrakty

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.

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

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

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

Wydawca

Polskie Towarzystwo Matematyczne

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.

steele@wharton.upenn.edu

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ę.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-4d8cc476-29a8-4041-9176-9da8f7c723a4