×

Optimal rules for the sequential selection of monotone subsequences of maximum expected length. (English) Zbl 1005.60056

Summary: This article presents new results on the problem of selecting (online) a monotone subsequence of maximum expected length from a sequence of i.i.d. random variables. We study the case where the variables are observed sequentially at the occurrence times of a Poisson process with known rate. Our approach is a detailed study of the integral equation which determines \(v(t)\), the expected number (under the optimal strategy for time horizon \(t\)) of selected points \(L^t_t\) up to time \(t\). We first show that \(v(t)\), \(v'(t)\) and \(v''(t)\) exist everywhere on \(\mathbb{R}^+\). Then, in particular, we prove that \(v''(t)<0\) for all \(t\in[0,\infty[\), implying that \(v\) is strictly concave on \(\mathbb{R}^+\). This settles a conjecture of Gnedin and opens the way to stronger bounds for \(v\) and its derivatives. We can show \(v'(t)\sqrt{2t}\sim 1\) from which we derive new and much tighter bounds for \(v(t)\), namely \[ \sqrt{2t}-\log(1+\sqrt{2t})+x\leqslant v(t)\leqslant\sqrt{2t}. \] Using a martingale approach, we can show that the variance of \(L^t_t\) satisfies \[ \frac 13v(t)\leqslant\text{Var}(L^t_t)\leqslant\frac 13v(t)+c_1\log(t)+c_2. \] Further we obtain several results on the process \((L_u^t)_{0\leqslant u\leqslant t}\), where \(L_u^t\) denotes the number of selected points up to time \(u\) when applying the optimal rule with respect to the time horizon \(t\). We will also show that the integral equation which yields \(v(t)\), has a unique solution. As an application, this result is used to extend a known result on the equivalence of a specific bin-packing problem with a certain subsequence problem. Our more personal interest in quick selection rules and their performance leads us also to the study of a class of convenient graph-rules. Known results on the concentration measure of record values suggest that the asymptotically best graph-rule should be the diagonal line rule, and we prove this intuition to be correct.

MSC:

60G40 Stopping times; optimal stopping problems; gambling theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aldous, D. J.; Diaconis, P., Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc., 36, 413-432 (1999) · Zbl 0937.60001
[2] Arnold, B. C.; Balakrishnan, N.; Nagaraja, H. N., Records. (1998), Wiley: Wiley New York, Chichester, Weinheim, Brisbane, Singapore, Toronto
[3] Baik, J.; Deift, P. A.; Johansson, K., On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc., 12, 1119-1178 (1999) · Zbl 0932.05001
[4] Baik, J., Rains, E.M., 1999. Algebraic aspects of increasing subsequences. Technical Report math.CO/9905083, XXX, Math Archiv.; Baik, J., Rains, E.M., 1999. Algebraic aspects of increasing subsequences. Technical Report math.CO/9905083, XXX, Math Archiv. · Zbl 1007.05096
[5] Baryshnikov, Y.M., Gnedin, A.V., 2000. Sequential selection of an increasing sequence from a multidimensional random sample. Ann. Appl. Probab., to appear.; Baryshnikov, Y.M., Gnedin, A.V., 2000. Sequential selection of an increasing sequence from a multidimensional random sample. Ann. Appl. Probab., to appear. · Zbl 1163.60310
[6] Billingsley, P., 1995. Probability and Measure. Wiley Series in Probability, New York, Chichester, Toronto, Singapore.; Billingsley, P., 1995. Probability and Measure. Wiley Series in Probability, New York, Chichester, Toronto, Singapore. · Zbl 0822.60002
[7] Boshuisen, F. A.; Kertz, R. P., Smallest-fit selection of random sizes under a sum constarint: weak convergence and moment comparisons, Adv. Appl. Prob., 31, 178-198 (1999) · Zbl 0937.60041
[8] Brémaud, J., Point processes and queues. (1981), Springer: Springer New York, Heidelberg, Berlin · Zbl 0478.60004
[9] Bruss, F. T.; Robertson, J., Wald’s Lemma for sums of order statistics of I.I.D. random variables, Adv. Appl. Prob., 23, 3, 612-623 (1991) · Zbl 0752.62057
[10] Coffman, E. G.; Flatto, L.; Weber, R. R., Optimal selection of stochastic intervals under a sum constraint, Adv. Appl. Prob., 19, 2, 454-473 (1987) · Zbl 0616.90035
[11] Critchlow, D., Ulam’s metric, Encyclopedia Statist. Sci., 9, 379-380 (1988)
[12] Deuschel, J.-D.; Zeitouni, O., Limiting curves for i.i.d. records, Ann. Probab., 23, 852-878 (1995) · Zbl 0834.60058
[13] Feller, W., An introduction to probability theory and its applications, Vol. II, Second Edition. (1971), Wiley: Wiley New York, London, Sidney, Toronto · Zbl 0219.60003
[14] Gnedin, A. V., Sequential selection of an increasing subsequence from a sample of random size, J. Appl. Probab., 36, 4, 1074-1085 (1999) · Zbl 0960.62084
[15] Gnedin, A.V., 2000a. Sequential selection of an increasing subsequence from a random sample with geometrically distributed sample size. In: Thomas Bruss, F., Lucien Le Cam (Eds.), Papers in honor of T.S. Ferguson, Lectures Notes of the Institute of Mathematical Statistics—Monograph Series, Vol. 35. Springer, Berlin, pp. 101-109.; Gnedin, A.V., 2000a. Sequential selection of an increasing subsequence from a random sample with geometrically distributed sample size. In: Thomas Bruss, F., Lucien Le Cam (Eds.), Papers in honor of T.S. Ferguson, Lectures Notes of the Institute of Mathematical Statistics—Monograph Series, Vol. 35. Springer, Berlin, pp. 101-109. · Zbl 0980.62064
[16] Gnedin, A. V., A note on sequential selection from permutations, Combin. Probab. Comput., 9, 13-17 (2000) · Zbl 0943.05002
[17] Goldie, C. M.; Resnick, S. I., Ordered independent scattering, Commun. Statist. Stochast. Models, 12, 4, 523-528 (1996) · Zbl 0873.60037
[18] Hammersley, J. M., A few seedlings of research, Proc. Sixth Berkeley Symp. Math. Stat. Prob., 1, 345-394 (1972) · Zbl 0236.00018
[19] Jacod, J.; Shiryaev, A. N., Limit Theorems for Stochastic Processes. (1987), Springer: Springer Berlin, Heidelberg, New York, London, Paris, Tokyo · Zbl 0635.60021
[20] Logan, B. F.; Shepp, L. A., A variational problem for random young tableaux, Adv. Math., 26, 206-222 (1977) · Zbl 0363.62068
[21] Mallows, C. L., Patience sorting, Bull. Inst. Math. Appl., 9, 216-224 (1973)
[22] Protter, P., Stochastic Integration and Differential Equations. (1995), Springer: Springer Berlin, Heidelberg, New York
[23] Rhee, W.; Talagrand, M., A note on the selection of random variables under a sum constraint, J. Appl. Probab., 28, 919-923 (1991) · Zbl 0749.60040
[24] Samuels, S. M.; Steele, J. M., Optimal sequential selection of a monotone sequence from a random sample, Ann. Probab., 9, 937-947 (1981) · Zbl 0473.62073
[25] Ulam, S. M., Some ideas and prospects in biomathematics, Ann. Rev. Biophys. Bioeng., 1, 277-292 (1972)
[26] Vers̀ik, A. M.; Kerov, S. V., Asymptotics of the plancherel measure of the symmetric group and the limiting form of the Young tables, Sov. Math. Dokl., 18, 527-531 (1977) · Zbl 0406.05008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.