22:
1435:
1177:
3579:
3932:
and James B. Robertson (1991). This paper proves moreover that the upper bound is asymptotically tight if the random variables are independent of each other. The generalisation to arbitrary continuous distributions (Theorem 2) is due to
3862:
3945:
The BRS-inequality is a versatile tool since it applies to many types of problems, and since the computation of the BRS-equation is often not very involved. Also, and in particular, one notes that the maximum number
2227:
2887:
1169:
1430:{\displaystyle {\begin{aligned}N={\begin{cases}0&,{\rm {~if~}}~X_{1,n}>s,\\\max\{~k\in \mathbb {N} :~X_{1,n}+X_{2,n}+\cdots +X_{k,n}\leq s\}&,{\rm {~otherwise}}.\end{cases}}\end{aligned}}(1)}
3989:
selections without recall. Examples studied in Steele (2016) and Bruss (2021) touch many applications, including comparisons between i.i.d. sequences and non-i.i.d. sequences, problems of condensing
2425:
1182:
977:
one may think of looking at the list of all observations, first select the smallest one, then add the second smallest, then the third and so on, as long as the accumulated sum does not exceed
2750:
2077:
3669:
1754:
389:
3297:
2535:
1817:
1556:
1089:
2625:
177:
3354:
2948:
917:
817:
2121:
782:
2324:
1644:
732:
3702:
are independent exponential random variables, then the memoryless property implies (if s is exceeded) the distributional symmetry of the residual and the overshoot over
2365:
1965:
3395:
2795:
1689:
85:. This inequality gives a convenient upper bound for the expected maximum number of non-negative random variables one can sum up without exceeding a given upper bound
3232:
2272:
3403:
1884:
109:
3700:
3184:
3138:
3003:
2562:
672:
645:
318:
1486:
618:
494:
415:
291:
235:
3918:
3890:
3979:
3740:
3720:
3076:
3041:
2968:
2660:
2465:
2445:
1576:
1030:
995:
975:
937:
852:
574:
554:
534:
514:
450:
1997:
1916:
1849:
209:
3745:
3675:
The expected residual in the numerator is typically difficult to compute or estimate, but there exist nice exceptions. For example, if all
2970:, then (6) recaptures (3), and (5) recaptures (2). Again it should be pointed out that no independence hypothesis whatsoever is needed.
2129:
2803:
1094:
620:, if the uniform distribution is replaced by another continuous distribution? In all generality, what can one say if each
4058:
2370:
2668:
1488:
if one requires only the continuity of the joint distribution of all variables? And then, how to compute this bound?
65:
43:
36:
2005:
734:
be a sequence of non-negative random variables (possibly dependent) that are jointly continuously distributed. For
3591:
1697:
323:
3243:
2481:
1763:
1502:
1035:
2567:
117:
3937:(2016). Theorem 3 and other refinements of the BRS-inequality are more recent and proved in Bruss (2021).
3302:
2896:
857:
787:
1558:
be identically distributed non-negative random variables with absolutely continuous distribution function
452:
is a random variable, so what can one say about bounds for its expectation? How would an upper bound for
2467:
fixed, or vice versa, yield for the uniform distribution in the non-trivial case the same upper bound.
2085:
737:
2277:
1584:
685:
1211:
30:
4006:
2332:
1921:
3574:{\displaystyle E(N)\leq \left(\sum _{k=1}^{n}F_{k}(t(n,s))\right)-{\frac {s-E(S_{A})}{t(n,s)}}}
3359:
2759:
1653:
47:
3189:
2236:
1854:
88:
3678:
3147:
3084:
2981:
2540:
1760:
As an example, here are the answers for the questions posed at the beginning. Thus let all
650:
623:
296:
1447:
579:
455:
394:
240:
214:
8:
3994:
3895:
3867:
3949:
3725:
3705:
3046:
3043:
be the random set of those variables one can sum up to yield the maximum random number
3011:
2953:
2630:
2450:
2430:
1561:
1000:
980:
945:
922:
822:
559:
539:
519:
499:
420:
1970:
1889:
1822:
182:
3934:
3998:
3929:
3005:, refinements of Theorem 2 can be of true interest. We just mention one of them.
4002:
3928:
The first version of the BRS-inequality (Theorem 1) was proved in Lemma 4.1 of
4052:
3990:
4010:
3857:{\displaystyle {\frac {s-E(S_{A})}{t(n,s)}}\to 1/2{\rm {~as~}}n\to \infty }
4037:
The Bruss-Robertson
Inequality: Elaborations, Extensions, and Applications
3299:
be jointly continuously distributed with marginal distribution functions
4023:’Wald's Lemma’ for Sums of Order Statistics of i.i.d. Random Variables
2537:
be positive random variables that are jointly distributed such that
4030:
Resource dependent branching processes and the envelope of societie
3585:
The improvement in (7) compared with (5) therefore consists of
3986:
2222:{\displaystyle E(N)\leq n\,F(t)=n{\sqrt {2s/n}}={\sqrt {2sn}}}
1032:
can be defined in terms of the increasing order statistics of
2882:{\displaystyle \sum _{k=1}^{n}\int _{0}^{t}\,x\,dF_{k}(x)=s.}
1491:
1164:{\displaystyle X_{1,n}\leq X_{2,n}\leq \cdots \leq X_{n,n},}
1410:
3186:
denote the sum of these variables. The so-called residual
3981:
always dominates the maximum number of selections under
3952:
3898:
3870:
3748:
3728:
3708:
3681:
3594:
3406:
3362:
3305:
3246:
3192:
3150:
3087:
3049:
3014:
2984:
2956:
2899:
2806:
2762:
2671:
2633:
2570:
2543:
2484:
2453:
2433:
2373:
2335:
2280:
2239:
2132:
2088:
2008:
1973:
1924:
1892:
1857:
1825:
1766:
1700:
1656:
1587:
1564:
1505:
1450:
1180:
1097:
1038:
1003:
983:
948:
925:
860:
825:
790:
740:
688:
653:
626:
582:
562:
542:
522:
502:
458:
423:
397:
326:
299:
243:
217:
185:
120:
91:
2973:
3234:is by definition always non-negative, and one has:
2564:has an absolutely continuous distribution function
2420:{\displaystyle E(N)\leq {\sqrt {2000}}\approx 44.7}
3973:
3912:
3884:
3856:
3734:
3714:
3694:
3663:
3573:
3389:
3348:
3291:
3226:
3178:
3132:
3070:
3035:
2997:
2962:
2942:
2881:
2789:
2744:
2654:
2619:
2556:
2529:
2459:
2439:
2419:
2359:
2318:
2266:
2221:
2115:
2071:
1991:
1959:
1910:
1878:
1843:
1811:
1748:
1683:
1638:
1570:
1550:
1480:
1429:
1163:
1083:
1024:
989:
969:
931:
911:
846:
811:
776:
726:
666:
647:may have its own continuous distribution function
639:
612:
568:
548:
528:
508:
488:
444:
409:
383:
312:
285:
229:
203:
171:
103:
2427:. As one sees from (4), doubling the sample size
4050:
2745:{\displaystyle E(N)\leq \sum _{k=1}^{n}F_{k}(t)}
1270:
4032:, Ann. of Appl. Probab., Vol. 25 (1), 324-372.
2470:
2072:{\displaystyle n\int _{0}^{t}xdx=nt^{2}/2=s.}
3664:{\displaystyle {\frac {s-E(S_{A})}{t(n,s)}}}
1749:{\displaystyle n\int _{0}^{t}x\,dF(x)\,=\,s}
1362:
1273:
854:be the maximum number of observations among
771:
747:
378:
327:
2978:Depending on the type of the distributions
2797:is the unique solution of the BRS-equation
384:{\displaystyle \{X_{1},X_{2},...,X_{100}\}}
114:For example, suppose 100 random variables
4039:, Math. Applicanda, Vol. 44, No 1, 3-16.
3292:{\displaystyle X_{1},X_{2},\cdots ,X_{n}}
2847:
2843:
2530:{\displaystyle X_{1},X_{2},\cdots ,X_{n}}
2166:
1812:{\displaystyle X_{1},X_{2},\cdots ,X_{n}}
1742:
1738:
1722:
1551:{\displaystyle X_{1},X_{2},\cdots ,X_{n}}
1492:Identically distributed random variables.
1286:
1084:{\displaystyle X_{1},X_{2},\cdots ,X_{n}}
799:
66:Learn how and when to remove this message
4025:, Adv. Appl. Probab., Vol. 23, 612-623.
3985:additional constraint, such as e.g. for
29:This article includes a list of general
4044:The BRS-inequality and its applications
2620:{\displaystyle F_{k},~k=1,2,\cdots ,n.}
211:, not necessarily independent, and let
172:{\displaystyle X_{1},X_{2},...,X_{100}}
4051:
4021:Bruss F. T. and Robertson J. B. (1991)
3864:. This improvement fluctuates around
919:that one can sum up without exceeding
536:fixed, or alternatively, if one keeps
4028:Bruss F. T. and Duerinckx M. (2015),
3349:{\displaystyle F_{k},k=1,2,\cdots ,n}
2943:{\displaystyle X_{i},i=1,2,\cdots ,n}
912:{\displaystyle X_{1},X_{2},...,X_{n}}
812:{\displaystyle s\in \mathbb {R} ^{+}}
2950:have the same marginal distribution
391:such that their sum does not exceed
15:
2123:, and thus from the inequality (2)
1691:solves the so-called BRS-equation
13:
4046:, Probab. Surveys, Vol.18, 44-76.
3851:
3837:
3834:
3088:
1399:
1396:
1393:
1390:
1387:
1384:
1381:
1378:
1375:
1230:
1227:
677:
35:it lacks sufficient corresponding
14:
4070:
2974:Refinements of the BRS-inequality
2893:Clearly, if all random variables
2274:, this bound becomes trivial for
179:are all uniformly distributed on
83:Bruss-Robertson-Steele inequality
2329:For the example questions with
2116:{\displaystyle t={\sqrt {2s/n}}}
777:{\displaystyle n\in \{1,2,...\}}
496:behave, if one changes the size
20:
3940:
2319:{\displaystyle s\geq nE(X)=n/2}
1639:{\displaystyle E(N)\leq nF(t),}
727:{\displaystyle X_{1},X_{2},...}
3968:
3956:
3848:
3815:
3809:
3797:
3789:
3784:
3772:
3761:
3655:
3643:
3635:
3630:
3618:
3607:
3565:
3553:
3545:
3540:
3528:
3517:
3494:
3491:
3479:
3473:
3431:
3428:
3416:
3410:
3384:
3372:
3219:
3207:
3171:
3159:
3127:
3115:
3106:
3094:
3065:
3053:
3030:
3018:
2867:
2861:
2784:
2772:
2739:
2733:
2696:
2693:
2681:
2675:
2649:
2637:
2398:
2395:
2383:
2377:
2299:
2293:
2255:
2243:
2176:
2170:
2157:
2154:
2142:
2136:
1986:
1974:
1937:
1931:
1905:
1893:
1867:
1861:
1838:
1826:
1735:
1729:
1678:
1666:
1630:
1624:
1612:
1609:
1597:
1591:
1475:
1472:
1460:
1454:
1424:
1418:
1200:
1188:
1019:
1007:
964:
952:
841:
829:
607:
604:
592:
586:
483:
480:
468:
462:
439:
427:
280:
268:
259:
247:
198:
186:
1:
4016:
3920:, (simulations) seems quick.
3742:one can then show that :
3397:be the solution of (6). Then
1819:be uniformly distributed on
7:
2662:is defined as before, then
1999:. The BRS-equation becomes
10:
4075:
4059:Probabilistic inequalities
2471:Generalised BRS-inequality
2360:{\displaystyle n=100,s=10}
1960:{\displaystyle dF(x)/dx=1}
1440:What is the best possible
3923:
3892:, and the convergence to
3390:{\displaystyle t:=t(n,s)}
2790:{\displaystyle t:=t(n,s)}
1684:{\displaystyle t:=t(n,s)}
576:? What can one say about
293:be the maximum number of
516:of the sample and keeps
4007:Bruss-Duerinckx theorem
3993:, “awkward” processes,
3227:{\displaystyle s-S_{A}}
2267:{\displaystyle N\leq n}
50:more precise citations.
3975:
3914:
3886:
3858:
3736:
3716:
3696:
3665:
3575:
3462:
3391:
3350:
3293:
3228:
3180:
3134:
3072:
3037:
2999:
2964:
2944:
2883:
2827:
2791:
2746:
2722:
2656:
2621:
2558:
2531:
2461:
2441:
2421:
2361:
2320:
2268:
2223:
2117:
2073:
1993:
1961:
1912:
1880:
1879:{\displaystyle F(t)=t}
1845:
1813:
1750:
1685:
1640:
1572:
1552:
1482:
1431:
1165:
1085:
1026:
991:
971:
933:
913:
848:
813:
778:
728:
668:
641:
614:
570:
550:
530:
510:
490:
446:
411:
385:
314:
287:
231:
205:
173:
105:
104:{\displaystyle s>0}
81:is the short name for
3976:
3915:
3887:
3859:
3737:
3717:
3697:
3695:{\displaystyle X_{k}}
3666:
3576:
3442:
3392:
3351:
3294:
3229:
3181:
3179:{\displaystyle S_{A}}
3135:
3133:{\displaystyle \#A=N}
3073:
3038:
3000:
2998:{\displaystyle F_{k}}
2965:
2945:
2884:
2807:
2792:
2747:
2702:
2657:
2622:
2559:
2557:{\displaystyle X_{k}}
2532:
2462:
2442:
2422:
2362:
2321:
2269:
2233:Since one always has
2224:
2118:
2074:
1994:
1962:
1913:
1881:
1846:
1814:
1751:
1686:
1641:
1573:
1553:
1483:
1432:
1166:
1086:
1027:
992:
972:
934:
914:
849:
814:
779:
729:
669:
667:{\displaystyle F_{k}}
642:
640:{\displaystyle X_{k}}
615:
571:
551:
531:
511:
491:
447:
412:
386:
315:
313:{\displaystyle X_{j}}
288:
232:
206:
174:
106:
4035:Steele J.M. (2016),
4005:-type problems, the
3995:selection algorithms
3950:
3896:
3868:
3746:
3726:
3706:
3679:
3592:
3404:
3360:
3303:
3244:
3190:
3148:
3085:
3047:
3012:
2982:
2954:
2897:
2804:
2760:
2669:
2631:
2568:
2541:
2482:
2451:
2431:
2371:
2333:
2278:
2237:
2130:
2086:
2006:
1971:
1922:
1890:
1855:
1823:
1764:
1698:
1654:
1585:
1562:
1503:
1481:{\displaystyle E(N)}
1448:
1178:
1095:
1036:
1001:
981:
946:
923:
858:
823:
788:
738:
686:
651:
624:
613:{\displaystyle E(N)}
580:
560:
540:
520:
500:
489:{\displaystyle E(N)}
456:
421:
410:{\displaystyle s=10}
395:
324:
297:
286:{\displaystyle N:=N}
241:
230:{\displaystyle s=10}
215:
183:
118:
89:
4042:Bruss F. T. (2021),
3913:{\displaystyle 1/2}
3885:{\displaystyle 1/2}
2842:
2026:
1718:
3971:
3910:
3882:
3854:
3732:
3712:
3692:
3661:
3571:
3387:
3346:
3289:
3224:
3176:
3130:
3068:
3033:
2995:
2960:
2940:
2879:
2828:
2787:
2742:
2652:
2617:
2554:
2527:
2457:
2437:
2417:
2357:
2316:
2264:
2219:
2113:
2069:
2012:
1989:
1957:
1908:
1876:
1841:
1809:
1746:
1704:
1681:
1636:
1568:
1548:
1478:
1427:
1416:
1409:
1161:
1081:
1022:
987:
967:
929:
909:
844:
809:
774:
724:
664:
637:
610:
566:
546:
526:
506:
486:
442:
407:
381:
320:one can select in
310:
283:
227:
201:
169:
101:
3999:knapsack problems
3974:{\displaystyle N}
3935:J. Michael Steele
3842:
3833:
3813:
3735:{\displaystyle s}
3715:{\displaystyle s}
3659:
3569:
3071:{\displaystyle N}
3036:{\displaystyle A}
2963:{\displaystyle F}
2655:{\displaystyle N}
2586:
2460:{\displaystyle s}
2440:{\displaystyle n}
2409:
2217:
2201:
2111:
2082:The solution is
1571:{\displaystyle F}
1374:
1295:
1278:
1240:
1235:
1226:
1025:{\displaystyle N}
990:{\displaystyle s}
970:{\displaystyle N}
932:{\displaystyle s}
847:{\displaystyle N}
569:{\displaystyle s}
556:fixed but varies
549:{\displaystyle n}
529:{\displaystyle s}
509:{\displaystyle n}
445:{\displaystyle N}
76:
75:
68:
4066:
3980:
3978:
3977:
3972:
3919:
3917:
3916:
3911:
3906:
3891:
3889:
3888:
3883:
3878:
3863:
3861:
3860:
3855:
3844:
3843:
3840:
3831:
3825:
3814:
3812:
3792:
3788:
3787:
3750:
3741:
3739:
3738:
3733:
3721:
3719:
3718:
3713:
3701:
3699:
3698:
3693:
3691:
3690:
3670:
3668:
3667:
3662:
3660:
3658:
3638:
3634:
3633:
3596:
3580:
3578:
3577:
3572:
3570:
3568:
3548:
3544:
3543:
3506:
3501:
3497:
3472:
3471:
3461:
3456:
3396:
3394:
3393:
3388:
3355:
3353:
3352:
3347:
3315:
3314:
3298:
3296:
3295:
3290:
3288:
3287:
3269:
3268:
3256:
3255:
3233:
3231:
3230:
3225:
3223:
3222:
3185:
3183:
3182:
3177:
3175:
3174:
3139:
3137:
3136:
3131:
3077:
3075:
3074:
3069:
3042:
3040:
3039:
3034:
3004:
3002:
3001:
2996:
2994:
2993:
2969:
2967:
2966:
2961:
2949:
2947:
2946:
2941:
2909:
2908:
2888:
2886:
2885:
2880:
2860:
2859:
2841:
2836:
2826:
2821:
2796:
2794:
2793:
2788:
2751:
2749:
2748:
2743:
2732:
2731:
2721:
2716:
2661:
2659:
2658:
2653:
2626:
2624:
2623:
2618:
2584:
2580:
2579:
2563:
2561:
2560:
2555:
2553:
2552:
2536:
2534:
2533:
2528:
2526:
2525:
2507:
2506:
2494:
2493:
2466:
2464:
2463:
2458:
2446:
2444:
2443:
2438:
2426:
2424:
2423:
2418:
2410:
2405:
2366:
2364:
2363:
2358:
2325:
2323:
2322:
2317:
2312:
2273:
2271:
2270:
2265:
2228:
2226:
2225:
2220:
2218:
2207:
2202:
2197:
2186:
2122:
2120:
2119:
2114:
2112:
2107:
2096:
2078:
2076:
2075:
2070:
2056:
2051:
2050:
2025:
2020:
1998:
1996:
1995:
1992:{\displaystyle }
1990:
1966:
1964:
1963:
1958:
1944:
1917:
1915:
1914:
1911:{\displaystyle }
1909:
1885:
1883:
1882:
1877:
1850:
1848:
1847:
1844:{\displaystyle }
1842:
1818:
1816:
1815:
1810:
1808:
1807:
1789:
1788:
1776:
1775:
1755:
1753:
1752:
1747:
1717:
1712:
1690:
1688:
1687:
1682:
1645:
1643:
1642:
1637:
1577:
1575:
1574:
1569:
1557:
1555:
1554:
1549:
1547:
1546:
1528:
1527:
1515:
1514:
1487:
1485:
1484:
1479:
1444:upper bound for
1436:
1434:
1433:
1428:
1417:
1413:
1412:
1403:
1402:
1372:
1355:
1354:
1330:
1329:
1311:
1310:
1293:
1289:
1276:
1256:
1255:
1238:
1237:
1236:
1233:
1224:
1170:
1168:
1167:
1162:
1157:
1156:
1132:
1131:
1113:
1112:
1090:
1088:
1087:
1082:
1080:
1079:
1061:
1060:
1048:
1047:
1031:
1029:
1028:
1023:
996:
994:
993:
988:
976:
974:
973:
968:
938:
936:
935:
930:
918:
916:
915:
910:
908:
907:
883:
882:
870:
869:
853:
851:
850:
845:
818:
816:
815:
810:
808:
807:
802:
783:
781:
780:
775:
733:
731:
730:
725:
711:
710:
698:
697:
673:
671:
670:
665:
663:
662:
646:
644:
643:
638:
636:
635:
619:
617:
616:
611:
575:
573:
572:
567:
555:
553:
552:
547:
535:
533:
532:
527:
515:
513:
512:
507:
495:
493:
492:
487:
451:
449:
448:
443:
416:
414:
413:
408:
390:
388:
387:
382:
377:
376:
352:
351:
339:
338:
319:
317:
316:
311:
309:
308:
292:
290:
289:
284:
236:
234:
233:
228:
210:
208:
207:
204:{\displaystyle }
202:
178:
176:
175:
170:
168:
167:
143:
142:
130:
129:
110:
108:
107:
102:
71:
64:
60:
57:
51:
46:this article by
37:inline citations
24:
23:
16:
4074:
4073:
4069:
4068:
4067:
4065:
4064:
4063:
4049:
4048:
4019:
3991:point processes
3951:
3948:
3947:
3943:
3930:F. Thomas Bruss
3926:
3902:
3897:
3894:
3893:
3874:
3869:
3866:
3865:
3830:
3829:
3821:
3793:
3768:
3764:
3751:
3749:
3747:
3744:
3743:
3727:
3724:
3723:
3707:
3704:
3703:
3686:
3682:
3680:
3677:
3676:
3639:
3614:
3610:
3597:
3595:
3593:
3590:
3589:
3549:
3524:
3520:
3507:
3505:
3467:
3463:
3457:
3446:
3441:
3437:
3405:
3402:
3401:
3361:
3358:
3357:
3310:
3306:
3304:
3301:
3300:
3283:
3279:
3264:
3260:
3251:
3247:
3245:
3242:
3241:
3203:
3199:
3191:
3188:
3187:
3155:
3151:
3149:
3146:
3145:
3086:
3083:
3082:
3048:
3045:
3044:
3013:
3010:
3009:
2989:
2985:
2983:
2980:
2979:
2976:
2955:
2952:
2951:
2904:
2900:
2898:
2895:
2894:
2855:
2851:
2837:
2832:
2822:
2811:
2805:
2802:
2801:
2761:
2758:
2757:
2727:
2723:
2717:
2706:
2670:
2667:
2666:
2632:
2629:
2628:
2575:
2571:
2569:
2566:
2565:
2548:
2544:
2542:
2539:
2538:
2521:
2517:
2502:
2498:
2489:
2485:
2483:
2480:
2479:
2473:
2452:
2449:
2448:
2432:
2429:
2428:
2404:
2372:
2369:
2368:
2334:
2331:
2330:
2308:
2279:
2276:
2275:
2238:
2235:
2234:
2206:
2193:
2185:
2131:
2128:
2127:
2103:
2095:
2087:
2084:
2083:
2052:
2046:
2042:
2021:
2016:
2007:
2004:
2003:
1972:
1969:
1968:
1940:
1923:
1920:
1919:
1891:
1888:
1887:
1856:
1853:
1852:
1824:
1821:
1820:
1803:
1799:
1784:
1780:
1771:
1767:
1765:
1762:
1761:
1713:
1708:
1699:
1696:
1695:
1655:
1652:
1651:
1586:
1583:
1582:
1563:
1560:
1559:
1542:
1538:
1523:
1519:
1510:
1506:
1504:
1501:
1500:
1494:
1449:
1446:
1445:
1415:
1414:
1408:
1407:
1371:
1370:
1365:
1344:
1340:
1319:
1315:
1300:
1296:
1285:
1267:
1266:
1245:
1241:
1223:
1222:
1217:
1207:
1206:
1181:
1179:
1176:
1175:
1146:
1142:
1121:
1117:
1102:
1098:
1096:
1093:
1092:
1075:
1071:
1056:
1052:
1043:
1039:
1037:
1034:
1033:
1002:
999:
998:
982:
979:
978:
947:
944:
943:
942:Now, to obtain
924:
921:
920:
903:
899:
878:
874:
865:
861:
859:
856:
855:
824:
821:
820:
803:
798:
797:
789:
786:
785:
739:
736:
735:
706:
702:
693:
689:
687:
684:
683:
680:
678:General problem
658:
654:
652:
649:
648:
631:
627:
625:
622:
621:
581:
578:
577:
561:
558:
557:
541:
538:
537:
521:
518:
517:
501:
498:
497:
457:
454:
453:
422:
419:
418:
396:
393:
392:
372:
368:
347:
343:
334:
330:
325:
322:
321:
304:
300:
298:
295:
294:
242:
239:
238:
216:
213:
212:
184:
181:
180:
163:
159:
138:
134:
125:
121:
119:
116:
115:
90:
87:
86:
72:
61:
55:
52:
42:Please help to
41:
25:
21:
12:
11:
5:
4072:
4062:
4061:
4018:
4015:
4003:Borel-Cantelli
3970:
3967:
3964:
3961:
3958:
3955:
3942:
3939:
3925:
3922:
3909:
3905:
3901:
3881:
3877:
3873:
3853:
3850:
3847:
3839:
3836:
3828:
3824:
3820:
3817:
3811:
3808:
3805:
3802:
3799:
3796:
3791:
3786:
3783:
3780:
3777:
3774:
3771:
3767:
3763:
3760:
3757:
3754:
3731:
3711:
3689:
3685:
3673:
3672:
3657:
3654:
3651:
3648:
3645:
3642:
3637:
3632:
3629:
3626:
3623:
3620:
3617:
3613:
3609:
3606:
3603:
3600:
3583:
3582:
3567:
3564:
3561:
3558:
3555:
3552:
3547:
3542:
3539:
3536:
3533:
3530:
3527:
3523:
3519:
3516:
3513:
3510:
3504:
3500:
3496:
3493:
3490:
3487:
3484:
3481:
3478:
3475:
3470:
3466:
3460:
3455:
3452:
3449:
3445:
3440:
3436:
3433:
3430:
3427:
3424:
3421:
3418:
3415:
3412:
3409:
3386:
3383:
3380:
3377:
3374:
3371:
3368:
3365:
3345:
3342:
3339:
3336:
3333:
3330:
3327:
3324:
3321:
3318:
3313:
3309:
3286:
3282:
3278:
3275:
3272:
3267:
3263:
3259:
3254:
3250:
3221:
3218:
3215:
3212:
3209:
3206:
3202:
3198:
3195:
3173:
3170:
3167:
3164:
3161:
3158:
3154:
3142:
3141:
3129:
3126:
3123:
3120:
3117:
3114:
3111:
3108:
3105:
3102:
3099:
3096:
3093:
3090:
3067:
3064:
3061:
3058:
3055:
3052:
3032:
3029:
3026:
3023:
3020:
3017:
2992:
2988:
2975:
2972:
2959:
2939:
2936:
2933:
2930:
2927:
2924:
2921:
2918:
2915:
2912:
2907:
2903:
2891:
2890:
2878:
2875:
2872:
2869:
2866:
2863:
2858:
2854:
2850:
2846:
2840:
2835:
2831:
2825:
2820:
2817:
2814:
2810:
2786:
2783:
2780:
2777:
2774:
2771:
2768:
2765:
2754:
2753:
2741:
2738:
2735:
2730:
2726:
2720:
2715:
2712:
2709:
2705:
2701:
2698:
2695:
2692:
2689:
2686:
2683:
2680:
2677:
2674:
2651:
2648:
2645:
2642:
2639:
2636:
2616:
2613:
2610:
2607:
2604:
2601:
2598:
2595:
2592:
2589:
2583:
2578:
2574:
2551:
2547:
2524:
2520:
2516:
2513:
2510:
2505:
2501:
2497:
2492:
2488:
2472:
2469:
2456:
2436:
2416:
2413:
2408:
2403:
2400:
2397:
2394:
2391:
2388:
2385:
2382:
2379:
2376:
2356:
2353:
2350:
2347:
2344:
2341:
2338:
2315:
2311:
2307:
2304:
2301:
2298:
2295:
2292:
2289:
2286:
2283:
2263:
2260:
2257:
2254:
2251:
2248:
2245:
2242:
2231:
2230:
2216:
2213:
2210:
2205:
2200:
2196:
2192:
2189:
2184:
2181:
2178:
2175:
2172:
2169:
2165:
2162:
2159:
2156:
2153:
2150:
2147:
2144:
2141:
2138:
2135:
2110:
2106:
2102:
2099:
2094:
2091:
2080:
2079:
2068:
2065:
2062:
2059:
2055:
2049:
2045:
2041:
2038:
2035:
2032:
2029:
2024:
2019:
2015:
2011:
1988:
1985:
1982:
1979:
1976:
1956:
1953:
1950:
1947:
1943:
1939:
1936:
1933:
1930:
1927:
1907:
1904:
1901:
1898:
1895:
1875:
1872:
1869:
1866:
1863:
1860:
1840:
1837:
1834:
1831:
1828:
1806:
1802:
1798:
1795:
1792:
1787:
1783:
1779:
1774:
1770:
1758:
1757:
1745:
1741:
1737:
1734:
1731:
1728:
1725:
1721:
1716:
1711:
1707:
1703:
1680:
1677:
1674:
1671:
1668:
1665:
1662:
1659:
1648:
1647:
1635:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1602:
1599:
1596:
1593:
1590:
1567:
1545:
1541:
1537:
1534:
1531:
1526:
1522:
1518:
1513:
1509:
1493:
1490:
1477:
1474:
1471:
1468:
1465:
1462:
1459:
1456:
1453:
1438:
1437:
1426:
1423:
1420:
1411:
1406:
1401:
1398:
1395:
1392:
1389:
1386:
1383:
1380:
1377:
1369:
1366:
1364:
1361:
1358:
1353:
1350:
1347:
1343:
1339:
1336:
1333:
1328:
1325:
1322:
1318:
1314:
1309:
1306:
1303:
1299:
1292:
1288:
1284:
1281:
1275:
1272:
1269:
1268:
1265:
1262:
1259:
1254:
1251:
1248:
1244:
1232:
1229:
1221:
1218:
1216:
1213:
1212:
1210:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1183:
1160:
1155:
1152:
1149:
1145:
1141:
1138:
1135:
1130:
1127:
1124:
1120:
1116:
1111:
1108:
1105:
1101:
1078:
1074:
1070:
1067:
1064:
1059:
1055:
1051:
1046:
1042:
1021:
1018:
1015:
1012:
1009:
1006:
986:
966:
963:
960:
957:
954:
951:
928:
906:
902:
898:
895:
892:
889:
886:
881:
877:
873:
868:
864:
843:
840:
837:
834:
831:
828:
806:
801:
796:
793:
773:
770:
767:
764:
761:
758:
755:
752:
749:
746:
743:
723:
720:
717:
714:
709:
705:
701:
696:
692:
679:
676:
661:
657:
634:
630:
609:
606:
603:
600:
597:
594:
591:
588:
585:
565:
545:
525:
505:
485:
482:
479:
476:
473:
470:
467:
464:
461:
441:
438:
435:
432:
429:
426:
406:
403:
400:
380:
375:
371:
367:
364:
361:
358:
355:
350:
346:
342:
337:
333:
329:
307:
303:
282:
279:
276:
273:
270:
267:
264:
261:
258:
255:
252:
249:
246:
226:
223:
220:
200:
197:
194:
191:
188:
166:
162:
158:
155:
152:
149:
146:
141:
137:
133:
128:
124:
100:
97:
94:
79:BRS-inequality
74:
73:
28:
26:
19:
9:
6:
4:
3:
2:
4071:
4060:
4057:
4056:
4054:
4047:
4045:
4040:
4038:
4033:
4031:
4026:
4024:
4014:
4012:
4009:, and online
4008:
4004:
4000:
3996:
3992:
3988:
3984:
3965:
3962:
3959:
3953:
3938:
3936:
3931:
3921:
3907:
3903:
3899:
3879:
3875:
3871:
3845:
3826:
3822:
3818:
3806:
3803:
3800:
3794:
3781:
3778:
3775:
3769:
3765:
3758:
3755:
3752:
3729:
3709:
3687:
3683:
3652:
3649:
3646:
3640:
3627:
3624:
3621:
3615:
3611:
3604:
3601:
3598:
3588:
3587:
3586:
3562:
3559:
3556:
3550:
3537:
3534:
3531:
3525:
3521:
3514:
3511:
3508:
3502:
3498:
3488:
3485:
3482:
3476:
3468:
3464:
3458:
3453:
3450:
3447:
3443:
3438:
3434:
3425:
3422:
3419:
3413:
3407:
3400:
3399:
3398:
3381:
3378:
3375:
3369:
3366:
3363:
3343:
3340:
3337:
3334:
3331:
3328:
3325:
3322:
3319:
3316:
3311:
3307:
3284:
3280:
3276:
3273:
3270:
3265:
3261:
3257:
3252:
3248:
3239:
3235:
3216:
3213:
3210:
3204:
3200:
3196:
3193:
3168:
3165:
3162:
3156:
3152:
3124:
3121:
3118:
3112:
3109:
3103:
3100:
3097:
3091:
3081:
3080:
3079:
3062:
3059:
3056:
3050:
3027:
3024:
3021:
3015:
3006:
2990:
2986:
2971:
2957:
2937:
2934:
2931:
2928:
2925:
2922:
2919:
2916:
2913:
2910:
2905:
2901:
2876:
2873:
2870:
2864:
2856:
2852:
2848:
2844:
2838:
2833:
2829:
2823:
2818:
2815:
2812:
2808:
2800:
2799:
2798:
2781:
2778:
2775:
2769:
2766:
2763:
2736:
2728:
2724:
2718:
2713:
2710:
2707:
2703:
2699:
2690:
2687:
2684:
2678:
2672:
2665:
2664:
2663:
2646:
2643:
2640:
2634:
2614:
2611:
2608:
2605:
2602:
2599:
2596:
2593:
2590:
2587:
2581:
2576:
2572:
2549:
2545:
2522:
2518:
2514:
2511:
2508:
2503:
2499:
2495:
2490:
2486:
2477:
2468:
2454:
2434:
2414:
2411:
2406:
2401:
2392:
2389:
2386:
2380:
2374:
2354:
2351:
2348:
2345:
2342:
2339:
2336:
2327:
2313:
2309:
2305:
2302:
2296:
2290:
2287:
2284:
2281:
2261:
2258:
2252:
2249:
2246:
2240:
2214:
2211:
2208:
2203:
2198:
2194:
2190:
2187:
2182:
2179:
2173:
2167:
2163:
2160:
2151:
2148:
2145:
2139:
2133:
2126:
2125:
2124:
2108:
2104:
2100:
2097:
2092:
2089:
2066:
2063:
2060:
2057:
2053:
2047:
2043:
2039:
2036:
2033:
2030:
2027:
2022:
2017:
2013:
2009:
2002:
2001:
2000:
1983:
1980:
1977:
1954:
1951:
1948:
1945:
1941:
1934:
1928:
1925:
1902:
1899:
1896:
1873:
1870:
1864:
1858:
1835:
1832:
1829:
1804:
1800:
1796:
1793:
1790:
1785:
1781:
1777:
1772:
1768:
1743:
1739:
1732:
1726:
1723:
1719:
1714:
1709:
1705:
1701:
1694:
1693:
1692:
1675:
1672:
1669:
1663:
1660:
1657:
1633:
1627:
1621:
1618:
1615:
1606:
1603:
1600:
1594:
1588:
1581:
1580:
1579:
1565:
1543:
1539:
1535:
1532:
1529:
1524:
1520:
1516:
1511:
1507:
1498:
1489:
1469:
1466:
1463:
1457:
1451:
1443:
1421:
1404:
1367:
1359:
1356:
1351:
1348:
1345:
1341:
1337:
1334:
1331:
1326:
1323:
1320:
1316:
1312:
1307:
1304:
1301:
1297:
1290:
1282:
1279:
1263:
1260:
1257:
1252:
1249:
1246:
1242:
1219:
1214:
1208:
1203:
1197:
1194:
1191:
1185:
1174:
1173:
1172:
1158:
1153:
1150:
1147:
1143:
1139:
1136:
1133:
1128:
1125:
1122:
1118:
1114:
1109:
1106:
1103:
1099:
1091:, denoted by
1076:
1072:
1068:
1065:
1062:
1057:
1053:
1049:
1044:
1040:
1016:
1013:
1010:
1004:
984:
961:
958:
955:
949:
940:
926:
904:
900:
896:
893:
890:
887:
884:
879:
875:
871:
866:
862:
838:
835:
832:
826:
804:
794:
791:
768:
765:
762:
759:
756:
753:
750:
744:
741:
721:
718:
715:
712:
707:
703:
699:
694:
690:
675:
659:
655:
632:
628:
601:
598:
595:
589:
583:
563:
543:
523:
503:
477:
474:
471:
465:
459:
436:
433:
430:
424:
404:
401:
398:
373:
369:
365:
362:
359:
356:
353:
348:
344:
340:
335:
331:
305:
301:
277:
274:
271:
265:
262:
256:
253:
250:
244:
224:
221:
218:
195:
192:
189:
164:
160:
156:
153:
150:
147:
144:
139:
135:
131:
126:
122:
112:
98:
95:
92:
84:
80:
70:
67:
59:
56:February 2022
49:
45:
39:
38:
32:
27:
18:
17:
4043:
4041:
4036:
4034:
4029:
4027:
4022:
4020:
4013:strategies.
3982:
3944:
3941:Applications
3927:
3722:. For fixed
3674:
3584:
3237:
3236:
3143:
3007:
2977:
2892:
2755:
2475:
2474:
2447:and keeping
2367:this yields
2328:
2232:
2081:
1918:, and hence
1759:
1649:
1496:
1495:
1441:
1439:
1171:, namely by
941:
681:
113:
82:
78:
77:
62:
53:
34:
3078:, that is,
237:, say. Let
48:introducing
4017:References
3356:, and let
3238:Theorem 3.
2476:Theorem 2.
31:references
3852:∞
3849:→
3816:→
3756:−
3602:−
3512:−
3503:−
3444:∑
3435:≤
3338:⋯
3274:⋯
3197:−
3089:#
2932:⋯
2830:∫
2809:∑
2704:∑
2700:≤
2606:⋯
2512:⋯
2412:≈
2402:≤
2285:≥
2259:≤
2161:≤
2014:∫
1794:⋯
1706:∫
1616:≤
1533:⋯
1497:Theorem 1
1357:≤
1335:⋯
1283:∈
1140:≤
1137:⋯
1134:≤
1115:≤
1066:⋯
795:∈
745:∈
4053:Category
3144:and let
997:. Hence
1851:. Then
1756:. (3)
1578:. Then
1442:general
44:improve
4011:Tiling
3987:online
3924:Source
3841:
3832:
2756:where
2752:, (5)
2585:
2229:. (4)
1650:where
1373:
1294:
1277:
1239:
1234:
1225:
33:, but
3581:. (7)
2627:. If
3240:Let
3008:Let
2478:Let
2415:44.7
2407:2000
1499:Let
1258:>
819:let
784:and
682:Let
96:>
3983:any
2889:(6)
2387:100
2343:100
1967:on
1886:on
1646:(2)
1271:max
431:100
374:100
272:100
165:100
4055::
4001:,
3997:,
3367::=
2767::=
2393:10
2355:10
2326:.
1661::=
939:.
674:?
437:10
417:.
405:10
278:10
263::=
225:10
111:.
3969:]
3966:s
3963:,
3960:n
3957:[
3954:N
3908:2
3904:/
3900:1
3880:2
3876:/
3872:1
3846:n
3838:s
3835:a
3827:2
3823:/
3819:1
3810:)
3807:s
3804:,
3801:n
3798:(
3795:t
3790:)
3785:]
3782:s
3779:,
3776:n
3773:[
3770:A
3766:S
3762:(
3759:E
3753:s
3730:s
3710:s
3688:k
3684:X
3671:.
3656:)
3653:s
3650:,
3647:n
3644:(
3641:t
3636:)
3631:]
3628:s
3625:,
3622:n
3619:[
3616:A
3612:S
3608:(
3605:E
3599:s
3566:)
3563:s
3560:,
3557:n
3554:(
3551:t
3546:)
3541:]
3538:s
3535:,
3532:n
3529:[
3526:A
3522:S
3518:(
3515:E
3509:s
3499:)
3495:)
3492:)
3489:s
3486:,
3483:n
3480:(
3477:t
3474:(
3469:k
3465:F
3459:n
3454:1
3451:=
3448:k
3439:(
3432:)
3429:]
3426:s
3423:,
3420:n
3417:[
3414:N
3411:(
3408:E
3385:)
3382:s
3379:,
3376:n
3373:(
3370:t
3364:t
3344:n
3341:,
3335:,
3332:2
3329:,
3326:1
3323:=
3320:k
3317:,
3312:k
3308:F
3285:n
3281:X
3277:,
3271:,
3266:2
3262:X
3258:,
3253:1
3249:X
3220:]
3217:s
3214:,
3211:n
3208:[
3205:A
3201:S
3194:s
3172:]
3169:s
3166:,
3163:n
3160:[
3157:A
3153:S
3140:,
3128:]
3125:s
3122:,
3119:n
3116:[
3113:N
3110:=
3107:]
3104:s
3101:,
3098:n
3095:[
3092:A
3066:]
3063:s
3060:,
3057:n
3054:[
3051:N
3031:]
3028:s
3025:,
3022:n
3019:[
3016:A
2991:k
2987:F
2958:F
2938:n
2935:,
2929:,
2926:2
2923:,
2920:1
2917:=
2914:i
2911:,
2906:i
2902:X
2877:.
2874:s
2871:=
2868:)
2865:x
2862:(
2857:k
2853:F
2849:d
2845:x
2839:t
2834:0
2824:n
2819:1
2816:=
2813:k
2785:)
2782:s
2779:,
2776:n
2773:(
2770:t
2764:t
2740:)
2737:t
2734:(
2729:k
2725:F
2719:n
2714:1
2711:=
2708:k
2697:)
2694:]
2691:s
2688:,
2685:n
2682:[
2679:N
2676:(
2673:E
2650:]
2647:s
2644:,
2641:n
2638:[
2635:N
2615:.
2612:n
2609:,
2603:,
2600:2
2597:,
2594:1
2591:=
2588:k
2582:,
2577:k
2573:F
2550:k
2546:X
2523:n
2519:X
2515:,
2509:,
2504:2
2500:X
2496:,
2491:1
2487:X
2455:s
2435:n
2399:)
2396:]
2390:,
2384:[
2381:N
2378:(
2375:E
2352:=
2349:s
2346:,
2340:=
2337:n
2314:2
2310:/
2306:n
2303:=
2300:)
2297:X
2294:(
2291:E
2288:n
2282:s
2262:n
2256:]
2253:s
2250:,
2247:n
2244:[
2241:N
2215:n
2212:s
2209:2
2204:=
2199:n
2195:/
2191:s
2188:2
2183:n
2180:=
2177:)
2174:t
2171:(
2168:F
2164:n
2158:)
2155:]
2152:s
2149:,
2146:n
2143:[
2140:N
2137:(
2134:E
2109:n
2105:/
2101:s
2098:2
2093:=
2090:t
2067:.
2064:s
2061:=
2058:2
2054:/
2048:2
2044:t
2040:n
2037:=
2034:x
2031:d
2028:x
2023:t
2018:0
2010:n
1987:]
1984:1
1981:,
1978:0
1975:[
1955:1
1952:=
1949:x
1946:d
1942:/
1938:)
1935:x
1932:(
1929:F
1926:d
1906:]
1903:1
1900:,
1897:0
1894:[
1874:t
1871:=
1868:)
1865:t
1862:(
1859:F
1839:]
1836:1
1833:,
1830:0
1827:[
1805:n
1801:X
1797:,
1791:,
1786:2
1782:X
1778:,
1773:1
1769:X
1744:s
1740:=
1736:)
1733:x
1730:(
1727:F
1724:d
1720:x
1715:t
1710:0
1702:n
1679:)
1676:s
1673:,
1670:n
1667:(
1664:t
1658:t
1634:,
1631:)
1628:t
1625:(
1622:F
1619:n
1613:)
1610:]
1607:s
1604:,
1601:n
1598:[
1595:N
1592:(
1589:E
1566:F
1544:n
1540:X
1536:,
1530:,
1525:2
1521:X
1517:,
1512:1
1508:X
1476:)
1473:]
1470:s
1467:,
1464:n
1461:[
1458:N
1455:(
1452:E
1425:)
1422:1
1419:(
1405:.
1400:e
1397:s
1394:i
1391:w
1388:r
1385:e
1382:h
1379:t
1376:o
1368:,
1363:}
1360:s
1352:n
1349:,
1346:k
1342:X
1338:+
1332:+
1327:n
1324:,
1321:2
1317:X
1313:+
1308:n
1305:,
1302:1
1298:X
1291::
1287:N
1280:k
1274:{
1264:,
1261:s
1253:n
1250:,
1247:1
1243:X
1231:f
1228:i
1220:,
1215:0
1209:{
1204:=
1201:]
1198:s
1195:,
1192:n
1189:[
1186:N
1159:,
1154:n
1151:,
1148:n
1144:X
1129:n
1126:,
1123:2
1119:X
1110:n
1107:,
1104:1
1100:X
1077:n
1073:X
1069:,
1063:,
1058:2
1054:X
1050:,
1045:1
1041:X
1020:]
1017:n
1014:,
1011:s
1008:[
1005:N
985:s
965:]
962:s
959:,
956:n
953:[
950:N
927:s
905:n
901:X
897:,
894:.
891:.
888:.
885:,
880:2
876:X
872:,
867:1
863:X
842:]
839:s
836:,
833:n
830:[
827:N
805:+
800:R
792:s
772:}
769:.
766:.
763:.
760:,
757:2
754:,
751:1
748:{
742:n
722:.
719:.
716:.
713:,
708:2
704:X
700:,
695:1
691:X
660:k
656:F
633:k
629:X
608:)
605:]
602:s
599:,
596:n
593:[
590:N
587:(
584:E
564:s
544:n
524:s
504:n
484:)
481:]
478:s
475:,
472:n
469:[
466:N
463:(
460:E
440:]
434:,
428:[
425:N
402:=
399:s
379:}
370:X
366:,
363:.
360:.
357:.
354:,
349:2
345:X
341:,
336:1
332:X
328:{
306:j
302:X
281:]
275:,
269:[
266:N
260:]
257:s
254:,
251:n
248:[
245:N
222:=
219:s
199:]
196:1
193:,
190:0
187:[
161:X
157:,
154:.
151:.
148:.
145:,
140:2
136:X
132:,
127:1
123:X
99:0
93:s
69:)
63:(
58:)
54:(
40:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.