1382:
1111:
6967:
35:). The deviation or other function of the random variable can be thought of as a secondary random variable. The simplest example of the concentration of such a secondary random variable is the CDF of the first random variable which concentrates the probability to unity. If an analytic form of the CDF is available this provides a concentration
1377:{\displaystyle {\text{Pr}}(X-E\geq r)\leq {\begin{cases}{\dfrac {4}{9}}{\dfrac {\operatorname {Var} (X)}{r^{2}+\operatorname {Var} (X)}}&{\text{for }}r^{2}\geq {\dfrac {5}{3}}\operatorname {Var} (X),\\{\dfrac {4}{3}}{\dfrac {\operatorname {Var} (X)}{r^{2}+\operatorname {Var} (X)}}-{\dfrac {1}{3}}&{\text{otherwise.}}\end{cases}}}
2765:
3440:
3079:
6797:
6379:
5694:
47:
of classical probability theory which states that sums of independent random variables, under mild conditions, concentrate around their expectation with a high probability. Such sums are the most basic examples of random variables concentrated around their
4553:
4280:
6648:
335:
5168:
1941:
1046:
39:
that provides the exact probability of concentration. It is precisely when the CDF is difficult to calculate or even the exact form of the first random variable is unknown that the applicable concentration inequalities provide useful insight.
735:
625:
3853:
7269:
2540:
2441:
4805:
5316:
3974:
1758:
1641:
2560:
185:
3235:
2874:
960:
492:
6962:{\displaystyle \Pr \left(\sup _{x\in \mathbb {R} }{\bigl (}F_{n}(x)-F(x){\bigr )}>\varepsilon \right)\leq e^{-2n\varepsilon ^{2}}{\text{ for every }}\varepsilon \geq {\sqrt {{\tfrac {1}{2n}}\ln 2}}.}
6151:
6220:
1527:
5415:
6230:
6077:
4910:
1841:
5548:
5480:
3163:
2342:
5558:
4380:
4072:
3615:
2089:
6481:
2029:
4390:
4114:
7033:
845:
6534:
5838:
5766:
3689:
2190:
770:
216:
7065:
7195:
2147:
405:
7153:
4864:
3221:
887:
7330:
4628:
4104:
2860:
5952:
1836:
5993:
4940:
4655:
2810:
967:
5871:
636:
4995:
6760:
5702:
6019:
5900:
1103:
7091:
5926:
1670:
1553:
522:
117:
6522:
4967:
4682:
4585:
4312:
4004:
2278:
2247:
2220:
208:
7564:
Advanced
Lectures on Machine Learning: ML Summer Schools 2003, Canberra, Australia, February 2–14, 2003, T{\"u}bingen, Germany, August 4–16, 2003, Revised Lectures
6680:
6392:
530:
7294:
7111:
7004:
6784:
6724:
6704:
6422:
5786:
4987:
1781:
1460:
1077:
794:
369:
87:
3860:
This is a generalization of
Hoeffding's since it can handle random variables with not only almost-sure bound but both almost-sure bound and variance bound.
3697:
1967:
3708:
3447:
This is a different generalization of
Hoeffding's since it can handle other functions besides the sum function, as long as they change in a bounded way.
7205:
2447:
6484:
6986:
on how much a random variable can concentrate, either on a specific value or range of values. A concrete example is that if you flip a fair coin
2348:
4692:
5176:
7596:
3866:
2760:{\displaystyle \Pr \left\leq 2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)\leq 2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\right)}
3094:. See Fan et al. (2015). Note that if the simpler form of Azuma's inequality is used, the exponent in the bound is worse by a factor of 4.
1678:
1561:
3435:{\displaystyle \Pr \left<2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)<2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\right)}
3074:{\displaystyle \Pr \left<2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)<2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\right)}
898:
125:
7834:
5713:
The Mason and van Zwet inequality for multinomial random vectors concerns a slight modification of the classical chi-square statistic.
55:
Concentration inequalities can be sorted according to how much information about the random variable is needed in order to use them.
7448:
918:
5329:
416:
6491:
6398:
6082:
6525:
2813:
6156:
3454:
offers some improvement over
Hoeffding's when the variances of the summands are small compared to their almost-sure bounds
799:
Chebyshev's inequality can be seen as a special case of the generalized Markov's inequality applied to the random variable
7541:
2545:
It is often interesting to bound the difference between the sum and its expected value. Several inequalities can be used.
1465:
7359:
6374:{\displaystyle \Pr \left(\sum _{i=1}^{k-1}{\frac {(N_{i}-np_{i})^{2}}{np_{i}}}>\lambda \right)\leq ae^{bk-c\lambda }.}
4823:
The Efron–Stein inequality (or influence inequality, or MG bound on variance) bounds the variance of a general function.
1393:
5342:
6024:
5689:{\displaystyle \Pr \left(\sum _{i=1}^{n}|Z_{i}-Mp_{i}|\geq 2M\varepsilon \right)\leq 2^{n}e^{-2M\varepsilon ^{2}}.}
1439:
5485:
5420:
3224:
3100:
2549:
2286:
1959:
1951:
346:
4548:{\displaystyle \Pr\leq \exp \left(-{\frac {\lambda ^{2}}{2(V_{n}+\sum _{i=1}^{n}a_{i}^{2}+M\lambda /3)}}\right)}
4317:
4275:{\displaystyle \Pr\leq \exp \left(-{\frac {\lambda ^{2}}{2(V_{n}+\sum _{i=1}^{n}a_{i}^{2}+M\lambda /3)}}\right)}
4009:
3466:
7336:
5333:
2041:
6643:{\displaystyle F_{n}(x)={\frac {1}{n}}\sum _{i=1}^{n}\mathbf {1} _{\{X_{i}\leq x\}},\qquad x\in \mathbb {R} .}
6427:
1975:
1411:
330:{\displaystyle \Pr(X\geq a)=\Pr(\Phi (X)\geq \Phi (a))\leq {\frac {\operatorname {E} (\Phi (X))}{\Phi (a)}}.}
7355:
7009:
4813:
3451:
1963:
802:
5791:
5719:
3620:
2153:
1158:
743:
64:
7038:
7035:. This idea can be greatly generalized. For example, a result of Rao and Yehudayoff implies that for any
7363:
7158:
4869:
2099:
378:
2863:
1955:
1422:
7399:
7116:
4829:
3863:
6. Chernoff bounds have a particularly simple form in the case of sum of independent variables, since
3180:
1398:
In contrast to most commonly used concentration inequalities, the Paley-Zygmund inequality provides a
7756:
1936:{\displaystyle \operatorname {P} (|Z|>t)\leq {\sqrt {\frac {2}{\pi }}}{\frac {\exp(-t^{2}/2)}{t}}}
1792:
44:
7562:
Boucheron, St{\'e}phane; Lugosi, G{\'a}bor; Bousquet, Olivier (2004). "Concentration inequalities".
1763:
There are various
Chernoff bounds for different distributions and different values of the parameter
1041:{\displaystyle {\text{Pr}}(\left|X-\mu \right|\geq \lambda \sigma )\leq {\frac {4}{9\lambda ^{2}}}.}
850:
7723:
7344:
7299:
6397:
The
Dvoretzky–Kiefer–Wolfowitz inequality bounds the difference between the real and the empirical
4590:
4077:
3086:
This is a generalization of
Hoeffding's since it can handle other types of martingales, as well as
2819:
730:{\displaystyle \Pr(|X-\operatorname {E} |\geq a\cdot \operatorname {Std} )\leq {\frac {1}{a^{2}}},}
5931:
5163:{\displaystyle X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).}
1800:
7819:
7791:
7772:
7746:
7640:
7498:
7465:
5957:
4633:
2775:
773:
20:
5843:
7592:
7444:
7419:
6729:
5998:
5876:
1082:
7764:
7737:
Matthew Kwan; Benny
Sudakov; Tuan Tran (2018). "Anticoncentration for subgraph statistics".
7683:
7650:
7584:
7508:
7411:
7070:
5905:
4915:
1649:
1532:
620:{\displaystyle \Pr(|X-\operatorname {E} |\geq a)\leq {\frac {\operatorname {Var} }{a^{2}}},}
501:
96:
6500:
4945:
4660:
4563:
4290:
3982:
2256:
2225:
2198:
193:
7815:
6656:
6487:
3087:
28:
7760:
7279:
7096:
6989:
6769:
6709:
6689:
6407:
5771:
4972:
2250:
1766:
1445:
1433:
1062:
779:
354:
72:
32:
7828:
3091:
2091:
90:
7776:
3848:{\displaystyle \Pr \left<2\exp \left(-{\frac {t^{2}/2}{V_{n}+C\cdot t/3}}\right)}
7719:
7348:
7578:
7264:{\displaystyle \Pr \left(\langle x,Y\rangle =k\right)\leq {\frac {C}{\sqrt {n}}},}
7486:
7438:
7530:
7006:
times, the probability that any given number of heads appears will be less than
7704:
7415:
7382:
5336:
and a vector of expected values. A simple proof appears in (Appendix
Section).
2535:{\displaystyle V_{n}:=\operatorname {Var} =\sum _{i=1}^{n}\operatorname {Var} }
351:
Chebyshev's inequality requires the following information on a random variable
7354:
An interesting anti-concentration inequality for weighted sums of independent
7688:
7671:
7423:
7526:
7464:
Slagle, N.P. (2012). "One
Hundred Statistics and Probability Inequalities".
7440:
Probability and Computing: Randomized Algorithms and Probabilistic Analysis
2436:{\displaystyle E_{n}:=\operatorname {E} =\sum _{i=1}^{n}\operatorname {E} }
1529:
It always exists, but may be infinite. From Markov's inequality, for every
7614:
Weak convergence and empirical processes: With applications to statistics
7512:
7400:"A one-sided Vysochanskii-Petunin inequality with financial applications"
4800:{\displaystyle \Pr\leq 2e^{-k^{2}/4n}{\text{ for }}0\leq k\leq 2\sigma .}
411:
5311:{\displaystyle \mathrm {Var} (f(X))\leq {\frac {1}{2}}\sum _{i=1}^{n}E.}
7768:
7588:
3969:{\displaystyle \operatorname {E} =\prod _{i=1}^{n}{\operatorname {E} }}
43:
Another almost universal example of a secondary random variable is the
7672:"A Refinement of the KMT Inequality for the Uniform Empirical Process"
7655:
7628:
1753:{\displaystyle \Pr(X\leq a)\leq {\frac {\operatorname {E} }{e^{ta}}}.}
1636:{\displaystyle \Pr(X\geq a)\leq {\frac {\operatorname {E} }{e^{ta}}},}
7796:
180:{\displaystyle \Pr(X\geq a)\leq {\frac {\operatorname {E} (X)}{a}}.}
16:
Mathematical inequality explaining concentration of random variables
7751:
7645:
7470:
7503:
1105:, the one-sided Vysochanskij-Petunin inequality holds as follows:
7790:
Veraar, Mark (2009). "On Khintchine inequalities with a weight".
7583:. Lecture Notes in Mathematics. Vol. 649. pp. 332–341.
7335:
Such inequalities are of importance in several fields, including
49:
3169:
variables. This function changes in a bounded way: if variable
955:{\textstyle \lambda >{\sqrt {\frac {8}{3}}}=1.63299\ldots ,}
1783:. See for a compilation of more concentration inequalities.
487:{\displaystyle \operatorname {Var} =\operatorname {E} )^{2}]}
7487:"Exponential inequalities for martingales with applications"
6146:{\displaystyle \lambda >Cn\min\{p_{i}|1\leq i\leq k-1\}}
1370:
210:
is a strictly increasing and non-negative function, then
7629:"Monte Carlo Methods for the Shapley–Shubik Power Index"
190:
Note the following extension to Markov's inequality: if
7720:"The Communication Complexity of Gap Hamming Distance"
6929:
921:
907:
be a random variable with unimodal distribution, mean
7302:
7282:
7208:
7161:
7119:
7099:
7073:
7041:
7012:
6992:
6800:
6772:
6732:
6712:
6692:
6659:
6537:
6503:
6430:
6410:
6233:
6215:{\displaystyle \sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,}
6159:
6085:
6027:
6001:
5960:
5934:
5908:
5879:
5846:
5794:
5774:
5722:
5561:
5488:
5423:
5345:
5179:
4998:
4975:
4948:
4918:
4872:
4832:
4695:
4663:
4636:
4593:
4566:
4393:
4320:
4293:
4117:
4080:
4012:
3985:
3869:
3711:
3623:
3469:
3238:
3183:
3103:
2877:
2822:
2778:
2563:
2450:
2351:
2289:
2259:
2228:
2201:
2156:
2102:
2044:
1978:
1844:
1803:
1769:
1681:
1652:
1564:
1535:
1468:
1448:
1349:
1293:
1281:
1247:
1174:
1162:
1114:
1085:
1065:
970:
853:
805:
782:
746:
639:
533:
504:
419:
381:
357:
219:
196:
128:
99:
75:
7707:. Electronic Colloquium on Computational Complexity.
1522:{\displaystyle M_{X}(t):=\operatorname {E} \!\left.}
27:
provide mathematical bounds on the probability of a
7816:
A Gentle Introduction to Concentration Inequalities
7627:Yuto Ushioda; Masato Tanaka; Tomomi Matsui (2022).
2031:be independent random variables such that, for all
7577:Bretagnolle, Jean; Huber-Carol, Catherine (1978).
7324:
7288:
7263:
7189:
7147:
7105:
7085:
7059:
7027:
6998:
6961:
6778:
6754:
6718:
6698:
6674:
6642:
6516:
6475:
6416:
6373:
6214:
6145:
6071:
6013:
5987:
5946:
5920:
5894:
5865:
5832:
5780:
5760:
5688:
5542:
5474:
5409:
5310:
5162:
4981:
4961:
4934:
4904:
4858:
4799:
4676:
4649:
4622:
4579:
4547:
4374:
4306:
4274:
4098:
4066:
3998:
3968:
3847:
3683:
3609:
3434:
3215:
3157:
3073:
2854:
2804:
2759:
2534:
2435:
2336:
2272:
2241:
2214:
2184:
2141:
2083:
2023:
1935:
1830:
1775:
1752:
1664:
1635:
1547:
1521:
1454:
1376:
1097:
1071:
1040:
954:
881:
839:
788:
764:
729:
619:
516:
486:
399:
363:
329:
202:
179:
111:
81:
7398:Mercadier, Mathieu; Strobel, Frank (2021-11-16).
5410:{\displaystyle (Z_{1},Z_{2},Z_{3},\ldots ,Z_{n})}
1494:
7209:
6810:
6801:
6234:
6098:
5562:
4696:
4394:
4118:
3712:
3470:
3239:
3227:can also be used and it yields a similar bound:
2878:
2866:can also be used and it yields a similar bound:
2564:
1682:
1565:
640:
534:
241:
220:
129:
4684:, a typical version of Chernoff inequality is:
1946:Bounds on sums of independent bounded variables
6072:{\displaystyle \lambda ,p_{1},\ldots ,p_{k-1}}
5417:is multinomially distributed with parameters
1051:(For a relatively elementary proof see e.g.).
6870:
6829:
5768:be multinomially distributed with parameters
8:
7670:Mason, David M.; Willem R. Van Zwet (1987).
7383:Pukelsheim, F., 1994. The Three Sigma Rule.
7313:
7303:
7229:
7217:
7178:
7168:
6617:
6598:
6140:
6101:
7612:van der Vaart, A.W.; Wellner, J.A. (1996).
7358:random variables can be obtained using the
5543:{\displaystyle Z_{1}+Z_{2}+\dots +Z_{n}=M,}
5475:{\displaystyle (p_{1},p_{2},\ldots ,p_{n})}
3158:{\displaystyle S_{n}=f(X_{1},\dots ,X_{n})}
2337:{\displaystyle S_{n}:=\sum _{i=1}^{n}X_{i}}
1968:Bernstein inequalities (probability theory)
89:be a random variable that is non-negative (
7739:Journal of the London Mathematical Society
7437:Mitzenmacher, Michael; Upfal, Eli (2005).
6766:of random variables that are smaller than
5334:multinomially distributed random variables
5332:bounds the difference between a vector of
4375:{\displaystyle X_{i}\leq E(X_{i})+a_{i}+M}
4067:{\displaystyle X_{i}\geq E(X_{i})-a_{i}-M}
3610:{\displaystyle \Pr \left\leq 2\exp \left,}
31:deviating from some value (typically, its
7795:
7750:
7687:
7654:
7644:
7502:
7469:
7316:
7301:
7281:
7246:
7207:
7181:
7160:
7124:
7118:
7098:
7072:
7040:
7013:
7011:
6991:
6928:
6926:
6915:
6907:
6893:
6869:
6868:
6838:
6828:
6827:
6821:
6820:
6813:
6799:
6771:
6737:
6731:
6711:
6691:
6658:
6633:
6632:
6605:
6597:
6592:
6585:
6574:
6560:
6542:
6536:
6508:
6502:
6467:
6448:
6435:
6429:
6409:
6350:
6320:
6305:
6295:
6279:
6269:
6257:
6246:
6232:
6191:
6175:
6164:
6158:
6114:
6108:
6084:
6057:
6038:
6026:
6000:
5959:
5933:
5907:
5878:
5851:
5845:
5821:
5802:
5793:
5773:
5749:
5730:
5721:
5675:
5661:
5651:
5622:
5616:
5600:
5591:
5585:
5574:
5560:
5525:
5506:
5493:
5487:
5463:
5444:
5431:
5422:
5398:
5379:
5366:
5353:
5344:
5296:
5277:
5237:
5226:
5212:
5180:
5178:
5148:
5123:
5107:
5088:
5069:
5047:
5031:
5012:
4997:
4974:
4953:
4947:
4923:
4917:
4893:
4877:
4871:
4850:
4837:
4831:
4771:
4758:
4752:
4744:
4717:
4711:
4702:
4694:
4668:
4662:
4641:
4635:
4609:
4603:
4594:
4592:
4571:
4565:
4526:
4511:
4506:
4496:
4485:
4472:
4455:
4449:
4417:
4404:
4392:
4360:
4344:
4325:
4319:
4298:
4292:
4253:
4238:
4233:
4223:
4212:
4199:
4182:
4176:
4141:
4128:
4116:
4079:
4052:
4036:
4017:
4011:
3990:
3984:
3954:
3943:
3929:
3923:
3912:
3894:
3883:
3868:
3829:
3811:
3797:
3791:
3784:
3748:
3742:
3729:
3720:
3710:
3622:
3587:
3573:
3558:
3548:
3542:
3506:
3500:
3487:
3478:
3468:
3418:
3403:
3393:
3359:
3354:
3344:
3333:
3321:
3311:
3275:
3269:
3256:
3247:
3237:
3201:
3188:
3182:
3146:
3127:
3108:
3102:
3057:
3042:
3032:
2998:
2993:
2983:
2972:
2960:
2950:
2914:
2908:
2895:
2886:
2876:
2840:
2827:
2821:
2796:
2783:
2777:
2743:
2728:
2718:
2684:
2679:
2669:
2658:
2646:
2636:
2600:
2594:
2581:
2572:
2562:
2523:
2504:
2493:
2477:
2455:
2449:
2424:
2405:
2394:
2378:
2356:
2350:
2328:
2318:
2307:
2294:
2288:
2264:
2258:
2233:
2227:
2206:
2200:
2170:
2155:
2133:
2120:
2107:
2101:
2084:{\displaystyle a_{i}\leq X_{i}\leq b_{i}}
2075:
2062:
2049:
2043:
2015:
1996:
1983:
1977:
1916:
1910:
1891:
1879:
1862:
1854:
1843:
1802:
1768:
1736:
1719:
1703:
1680:
1651:
1619:
1602:
1586:
1563:
1534:
1503:
1473:
1467:
1447:
1362:
1348:
1317:
1292:
1280:
1246:
1237:
1228:
1198:
1173:
1161:
1153:
1115:
1113:
1084:
1064:
1055:One-sided Vysochanskij–Petunin inequality
1026:
1013:
971:
969:
928:
920:
873:
852:
832:
806:
804:
781:
745:
716:
707:
672:
646:
638:
606:
583:
566:
540:
532:
503:
475:
418:
380:
356:
280:
218:
195:
150:
127:
98:
74:
7616:. Springer Science & Business Media.
7580:Lois empiriques et distance de Prokhorov
7531:"Old and new concentration inequalities"
7404:European Journal of Operational Research
6476:{\displaystyle X_{1},X_{2},\dots ,X_{n}}
2024:{\displaystyle X_{1},X_{2},\dots ,X_{n}}
1438:The generic Chernoff bound requires the
7705:"Anti-concentration in most directions"
7375:
6485:independent and identically distributed
7028:{\displaystyle {\frac {1}{\sqrt {n}}}}
5701:This inequality is used to bound the
4814:Rademacher distribution#Bounds on sums
4106:. Then we have lower tail inequality:
840:{\displaystyle |X-\operatorname {E} |}
7113:, the following is true for at least
6393:Dvoretzky–Kiefer–Wolfowitz inequality
6387:Dvoretzky–Kiefer–Wolfowitz inequality
5833:{\displaystyle (p_{1},\ldots ,p_{k})}
5761:{\displaystyle (N_{1},\ldots ,N_{k})}
4969:having the same distribution for all
3684:{\displaystyle h(u)=(1+u)\log(1+u)-u}
3165:, is a special case of a function of
2185:{\displaystyle \forall i:c_{i}\leq C}
7:
7703:Rao, Anup; Yehudayoff, Amir (2018).
7485:Fan, X.; Grama, I.; Liu, Q. (2015).
1402:bound on the deviation probability.
765:{\displaystyle \operatorname {Std} }
7060:{\displaystyle \beta ,\delta >0}
4812:7. Similar bounds can be found in:
3979:For example, suppose the variables
7190:{\displaystyle x\in \{\pm 1\}^{n}}
5330:Bretagnolle–Huber–Carol Inequality
5325:Bretagnolle–Huber–Carol inequality
5187:
5184:
5181:
4905:{\displaystyle X_{1}'\dots X_{n}'}
3930:
3870:
2411:
2365:
2157:
2142:{\displaystyle c_{i}:=b_{i}-a_{i}}
1845:
1706:
1589:
1491:
854:
817:
657:
551:
456:
438:
400:{\displaystyle \operatorname {E} }
382:
309:
292:
283:
262:
247:
197:
153:
14:
7497:. Electron. J. Probab. 20: 1–22.
7491:Electronic Journal of Probability
4382:, we have upper tail inequality:
7148:{\displaystyle 2^{n(1-\delta )}}
6982:, on the other hand, provide an
6593:
6492:cumulative distribution function
6399:cumulative distribution function
4859:{\displaystyle X_{1}\dots X_{n}}
3216:{\displaystyle b_{i}-a_{i}<C}
7718:Sherstov, Alexander A. (2012).
6980:Anti-concentration inequalities
6975:Anti-concentration inequalities
6625:
6526:empirical distribution function
5321:A proof may be found in e.g.,.
1059:For a unimodal random variable
899:Vysochanskij–Petunin inequality
893:Vysochanskij–Petunin inequality
7443:. Cambridge University Press.
7140:
7128:
6865:
6859:
6850:
6844:
6749:
6743:
6669:
6663:
6554:
6548:
6302:
6272:
6115:
5827:
5795:
5755:
5723:
5623:
5592:
5469:
5424:
5404:
5346:
5302:
5293:
5289:
5284:
5278:
5270:
5261:
5255:
5249:
5246:
5206:
5203:
5197:
5191:
5154:
5062:
5054:
5048:
5037:
5005:
4731:
4718:
4703:
4699:
4610:
4595:
4534:
4465:
4429:
4397:
4350:
4337:
4261:
4192:
4156:
4121:
4042:
4029:
3962:
3936:
3902:
3876:
3749:
3721:
3672:
3660:
3651:
3639:
3633:
3627:
3507:
3479:
3276:
3248:
3152:
3120:
2915:
2887:
2601:
2573:
2529:
2516:
2483:
2470:
2430:
2417:
2384:
2371:
1924:
1900:
1873:
1863:
1855:
1851:
1825:
1813:
1728:
1712:
1697:
1685:
1611:
1595:
1580:
1568:
1485:
1479:
1338:
1332:
1308:
1302:
1270:
1264:
1219:
1213:
1189:
1183:
1147:
1138:
1132:
1120:
1007:
976:
911:and finite, non-zero variance
882:{\displaystyle \Phi (x)=x^{2}}
863:
857:
833:
829:
823:
807:
759:
753:
701:
698:
692:
673:
669:
663:
647:
643:
598:
592:
577:
567:
563:
557:
541:
537:
481:
472:
468:
462:
447:
444:
432:
426:
394:
388:
318:
312:
304:
301:
295:
289:
274:
271:
265:
256:
250:
244:
235:
223:
165:
159:
144:
132:
1:
7542:American Mathematical Society
7325:{\displaystyle \{\pm 1\}^{n}}
5709:Mason and van Zwet inequality
4623:{\displaystyle |X_{i}|\leq 1}
4099:{\displaystyle 1\leq i\leq n}
2862:. Hence, the general form of
2855:{\displaystyle S_{0}-E_{0}=0}
5947:{\displaystyle \delta >0}
1831:{\displaystyle Z\sim N(0,1)}
93:). Then, for every constant
7538:Complex Graphs and Networks
5988:{\displaystyle a,b,c>0,}
4650:{\displaystyle \sigma ^{2}}
2805:{\displaystyle S_{n}-E_{n}}
7851:
7835:Probabilistic inequalities
7416:10.1016/j.ejor.2021.02.041
6682:is the probability that a
6390:
5866:{\displaystyle p_{i}>0}
1949:
1790:
1786:
1440:moment generating function
1431:
1420:
1416:
1409:
1405:
1391:
896:
344:
340:
62:
58:
25:concentration inequalities
7676:The Annals of Probability
7385:The American Statistician
3173:is changed, the value of
498:Then, for every constant
7345:gap Hamming problem
7337:communication complexity
7296:is drawn uniformly from
6755:{\displaystyle F_{n}(x)}
5703:total variation distance
3698:Bernstein's inequalities
1394:Paley–Zygmund inequality
1388:Paley–Zygmund inequality
6404:Given a natural number
6014:{\displaystyle n\geq 1}
5895:{\displaystyle i<k.}
2812:is a special case of a
2772:2. The random variable
1098:{\displaystyle r\geq 0}
7689:10.1214/aop/1176992070
7529:; Lu, Linyuan (2010).
7326:
7290:
7265:
7191:
7149:
7107:
7087:
7086:{\displaystyle C>0}
7061:
7029:
7000:
6963:
6780:
6756:
6720:
6700:
6676:
6644:
6590:
6524:denote the associated
6518:
6477:
6418:
6375:
6268:
6216:
6186:
6147:
6073:
6015:
5989:
5954:there exist constants
5948:
5922:
5921:{\displaystyle C>0}
5896:
5867:
5834:
5782:
5762:
5716:Let the random vector
5690:
5590:
5544:
5476:
5411:
5312:
5242:
5164:
4983:
4963:
4936:
4935:{\displaystyle X_{i}'}
4906:
4860:
4819:Efron–Stein inequality
4801:
4678:
4651:
4624:
4581:
4549:
4501:
4376:
4308:
4276:
4228:
4100:
4068:
4000:
3970:
3928:
3849:
3685:
3611:
3436:
3349:
3225:McDiarmid's inequality
3217:
3159:
3075:
2988:
2856:
2806:
2761:
2674:
2550:Hoeffding's inequality
2536:
2509:
2437:
2410:
2338:
2323:
2274:
2243:
2216:
2186:
2143:
2085:
2025:
1960:McDiarmid's inequality
1952:Hoeffding's inequality
1937:
1832:
1777:
1754:
1666:
1665:{\displaystyle t<0}
1637:
1549:
1548:{\displaystyle t>0}
1523:
1456:
1378:
1099:
1073:
1042:
956:
883:
841:
790:
766:
731:
621:
518:
517:{\displaystyle a>0}
488:
401:
365:
347:Chebyshev's inequality
341:Chebyshev's inequality
331:
204:
181:
113:
112:{\displaystyle a>0}
83:
7327:
7291:
7266:
7192:
7150:
7108:
7088:
7062:
7030:
7001:
6964:
6917: for every
6781:
6757:
6721:
6701:
6677:
6645:
6570:
6519:
6517:{\displaystyle F_{n}}
6478:
6419:
6376:
6242:
6217:
6160:
6148:
6074:
6016:
5990:
5949:
5923:
5897:
5868:
5835:
5783:
5763:
5691:
5570:
5545:
5477:
5412:
5313:
5222:
5165:
4984:
4964:
4962:{\displaystyle X_{i}}
4937:
4912:are independent with
4907:
4861:
4802:
4679:
4677:{\displaystyle X_{i}}
4652:
4625:
4582:
4580:{\displaystyle X_{i}}
4550:
4481:
4377:
4309:
4307:{\displaystyle X_{i}}
4277:
4208:
4101:
4069:
4001:
3999:{\displaystyle X_{i}}
3971:
3908:
3850:
3686:
3612:
3437:
3329:
3218:
3160:
3097:3. The sum function,
3076:
2968:
2857:
2807:
2762:
2654:
2537:
2489:
2438:
2390:
2339:
2303:
2275:
2273:{\displaystyle V_{n}}
2244:
2242:{\displaystyle E_{n}}
2217:
2215:{\displaystyle S_{n}}
2187:
2144:
2086:
2026:
1938:
1833:
1778:
1755:
1667:
1638:
1550:
1524:
1457:
1412:Cantelli's inequality
1406:Cantelli's inequality
1379:
1100:
1074:
1043:
957:
884:
842:
791:
767:
732:
622:
519:
489:
402:
366:
332:
205:
203:{\displaystyle \Phi }
182:
114:
84:
7814:Karthik Sridharan, "
7566:. Springer: 208–240.
7513:10.1214/EJP.v20-3496
7300:
7280:
7206:
7159:
7117:
7097:
7071:
7039:
7010:
6990:
6798:
6770:
6730:
6710:
6690:
6675:{\displaystyle F(x)}
6657:
6535:
6501:
6428:
6408:
6231:
6157:
6083:
6025:
5999:
5958:
5932:
5906:
5877:
5844:
5792:
5772:
5720:
5559:
5486:
5421:
5343:
5177:
4996:
4973:
4946:
4916:
4870:
4830:
4693:
4661:
4634:
4591:
4564:
4391:
4318:
4291:
4115:
4078:
4010:
3983:
3867:
3709:
3621:
3467:
3452:Bennett's inequality
3236:
3181:
3101:
2875:
2820:
2776:
2561:
2448:
2349:
2287:
2257:
2226:
2199:
2154:
2100:
2042:
1976:
1964:Bennett's inequality
1842:
1801:
1767:
1679:
1650:
1562:
1533:
1466:
1446:
1112:
1083:
1063:
968:
919:
851:
803:
780:
744:
637:
531:
502:
417:
379:
355:
217:
194:
126:
97:
73:
45:law of large numbers
7761:2018arXiv180705202K
7724:Theory of Computing
7343:, in proofs of the
7093:such that, for any
5339:If a random vector
5115:
4931:
4901:
4885:
4657:is the variance of
4516:
4243:
3364:
3177:changes by at most
3003:
2689:
375:The expected value
65:Markov's inequality
59:Markov's inequality
7820:Cornell University
7769:10.1112/jlms.12192
7589:10.1007/BFb0064609
7387:, 48(2), pp. 88–91
7322:
7286:
7261:
7187:
7145:
7103:
7083:
7067:there exists some
7057:
7025:
6996:
6959:
6943:
6826:
6776:
6752:
6716:
6696:
6672:
6640:
6514:
6473:
6414:
6371:
6212:
6143:
6069:
6011:
5995:such that for all
5985:
5944:
5918:
5892:
5863:
5830:
5778:
5758:
5686:
5540:
5472:
5407:
5308:
5160:
5103:
4979:
4959:
4932:
4919:
4902:
4889:
4873:
4856:
4797:
4674:
4647:
4620:
4577:
4545:
4502:
4372:
4304:
4272:
4229:
4096:
4064:
3996:
3966:
3845:
3681:
3607:
3432:
3350:
3213:
3155:
3071:
2989:
2864:Azuma's inequality
2852:
2802:
2757:
2675:
2532:
2433:
2334:
2270:
2239:
2212:
2182:
2139:
2081:
2021:
1956:Azuma's inequality
1933:
1828:
1773:
1750:
1662:
1633:
1545:
1519:
1452:
1423:Gauss's inequality
1417:Gauss's inequality
1374:
1369:
1358:
1343:
1290:
1256:
1224:
1171:
1095:
1069:
1038:
952:
879:
837:
786:
774:standard deviation
762:
727:
617:
514:
484:
397:
361:
327:
200:
177:
109:
79:
21:probability theory
7656:10.3390/g13030044
7598:978-3-540-08761-8
7289:{\displaystyle Y}
7256:
7255:
7106:{\displaystyle k}
7023:
7022:
6999:{\displaystyle n}
6954:
6942:
6918:
6809:
6779:{\displaystyle x}
6719:{\displaystyle x}
6699:{\displaystyle X}
6568:
6417:{\displaystyle n}
6327:
5781:{\displaystyle n}
5220:
4982:{\displaystyle i}
4774:
4538:
4265:
3838:
3593:
3564:
3425:
3366:
3064:
3005:
2750:
2691:
1931:
1889:
1888:
1793:Mill's Inequality
1787:Mill's inequality
1776:{\displaystyle t}
1745:
1628:
1455:{\displaystyle X}
1365:
1357:
1342:
1289:
1255:
1231:
1223:
1170:
1118:
1072:{\displaystyle X}
1033:
974:
938:
937:
789:{\displaystyle X}
722:
630:or equivalently,
612:
364:{\displaystyle X}
322:
172:
82:{\displaystyle X}
7842:
7802:
7801:
7799:
7787:
7781:
7780:
7754:
7734:
7728:
7727:
7715:
7709:
7708:
7700:
7694:
7693:
7691:
7667:
7661:
7660:
7658:
7648:
7624:
7618:
7617:
7609:
7603:
7602:
7574:
7568:
7567:
7559:
7553:
7552:
7550:
7548:
7535:
7523:
7517:
7516:
7506:
7482:
7476:
7475:
7473:
7461:
7455:
7454:
7434:
7428:
7427:
7395:
7389:
7380:
7331:
7329:
7328:
7323:
7321:
7320:
7295:
7293:
7292:
7287:
7270:
7268:
7267:
7262:
7257:
7251:
7247:
7242:
7238:
7196:
7194:
7193:
7188:
7186:
7185:
7154:
7152:
7151:
7146:
7144:
7143:
7112:
7110:
7109:
7104:
7092:
7090:
7089:
7084:
7066:
7064:
7063:
7058:
7034:
7032:
7031:
7026:
7024:
7018:
7014:
7005:
7003:
7002:
6997:
6968:
6966:
6965:
6960:
6955:
6944:
6941:
6930:
6927:
6919:
6916:
6914:
6913:
6912:
6911:
6885:
6881:
6874:
6873:
6843:
6842:
6833:
6832:
6825:
6824:
6785:
6783:
6782:
6777:
6761:
6759:
6758:
6753:
6742:
6741:
6725:
6723:
6722:
6717:
6706:is smaller than
6705:
6703:
6702:
6697:
6686:random variable
6681:
6679:
6678:
6673:
6649:
6647:
6646:
6641:
6636:
6621:
6620:
6610:
6609:
6596:
6589:
6584:
6569:
6561:
6547:
6546:
6523:
6521:
6520:
6515:
6513:
6512:
6488:random variables
6482:
6480:
6479:
6474:
6472:
6471:
6453:
6452:
6440:
6439:
6423:
6421:
6420:
6415:
6380:
6378:
6377:
6372:
6367:
6366:
6339:
6335:
6328:
6326:
6325:
6324:
6311:
6310:
6309:
6300:
6299:
6284:
6283:
6270:
6267:
6256:
6221:
6219:
6218:
6213:
6196:
6195:
6185:
6174:
6152:
6150:
6149:
6144:
6118:
6113:
6112:
6078:
6076:
6075:
6070:
6068:
6067:
6043:
6042:
6020:
6018:
6017:
6012:
5994:
5992:
5991:
5986:
5953:
5951:
5950:
5945:
5927:
5925:
5924:
5919:
5901:
5899:
5898:
5893:
5872:
5870:
5869:
5864:
5856:
5855:
5839:
5837:
5836:
5831:
5826:
5825:
5807:
5806:
5787:
5785:
5784:
5779:
5767:
5765:
5764:
5759:
5754:
5753:
5735:
5734:
5695:
5693:
5692:
5687:
5682:
5681:
5680:
5679:
5656:
5655:
5643:
5639:
5626:
5621:
5620:
5605:
5604:
5595:
5589:
5584:
5549:
5547:
5546:
5541:
5530:
5529:
5511:
5510:
5498:
5497:
5481:
5479:
5478:
5473:
5468:
5467:
5449:
5448:
5436:
5435:
5416:
5414:
5413:
5408:
5403:
5402:
5384:
5383:
5371:
5370:
5358:
5357:
5317:
5315:
5314:
5309:
5301:
5300:
5288:
5287:
5241:
5236:
5221:
5213:
5190:
5169:
5167:
5166:
5161:
5153:
5152:
5134:
5133:
5111:
5099:
5098:
5074:
5073:
5058:
5057:
5036:
5035:
5017:
5016:
4988:
4986:
4985:
4980:
4968:
4966:
4965:
4960:
4958:
4957:
4941:
4939:
4938:
4933:
4927:
4911:
4909:
4908:
4903:
4897:
4881:
4865:
4863:
4862:
4857:
4855:
4854:
4842:
4841:
4806:
4804:
4803:
4798:
4775:
4772:
4770:
4769:
4762:
4757:
4756:
4721:
4716:
4715:
4706:
4683:
4681:
4680:
4675:
4673:
4672:
4656:
4654:
4653:
4648:
4646:
4645:
4629:
4627:
4626:
4621:
4613:
4608:
4607:
4598:
4586:
4584:
4583:
4578:
4576:
4575:
4554:
4552:
4551:
4546:
4544:
4540:
4539:
4537:
4530:
4515:
4510:
4500:
4495:
4477:
4476:
4460:
4459:
4450:
4422:
4421:
4409:
4408:
4381:
4379:
4378:
4373:
4365:
4364:
4349:
4348:
4330:
4329:
4313:
4311:
4310:
4305:
4303:
4302:
4281:
4279:
4278:
4273:
4271:
4267:
4266:
4264:
4257:
4242:
4237:
4227:
4222:
4204:
4203:
4187:
4186:
4177:
4146:
4145:
4133:
4132:
4105:
4103:
4102:
4097:
4073:
4071:
4070:
4065:
4057:
4056:
4041:
4040:
4022:
4021:
4005:
4003:
4002:
3997:
3995:
3994:
3975:
3973:
3972:
3967:
3965:
3961:
3960:
3959:
3958:
3927:
3922:
3901:
3900:
3899:
3898:
3854:
3852:
3851:
3846:
3844:
3840:
3839:
3837:
3833:
3816:
3815:
3805:
3801:
3796:
3795:
3785:
3763:
3759:
3752:
3747:
3746:
3734:
3733:
3724:
3696:5. The first of
3690:
3688:
3687:
3682:
3616:
3614:
3613:
3608:
3603:
3599:
3598:
3594:
3592:
3591:
3582:
3574:
3565:
3563:
3562:
3553:
3552:
3543:
3521:
3517:
3510:
3505:
3504:
3492:
3491:
3482:
3458:. It says that:
3441:
3439:
3438:
3433:
3431:
3427:
3426:
3424:
3423:
3422:
3409:
3408:
3407:
3394:
3372:
3368:
3367:
3365:
3363:
3358:
3348:
3343:
3327:
3326:
3325:
3312:
3290:
3286:
3279:
3274:
3273:
3261:
3260:
3251:
3222:
3220:
3219:
3214:
3206:
3205:
3193:
3192:
3164:
3162:
3161:
3156:
3151:
3150:
3132:
3131:
3113:
3112:
3088:supermartingales
3080:
3078:
3077:
3072:
3070:
3066:
3065:
3063:
3062:
3061:
3048:
3047:
3046:
3033:
3011:
3007:
3006:
3004:
3002:
2997:
2987:
2982:
2966:
2965:
2964:
2951:
2929:
2925:
2918:
2913:
2912:
2900:
2899:
2890:
2861:
2859:
2858:
2853:
2845:
2844:
2832:
2831:
2811:
2809:
2808:
2803:
2801:
2800:
2788:
2787:
2766:
2764:
2763:
2758:
2756:
2752:
2751:
2749:
2748:
2747:
2734:
2733:
2732:
2719:
2697:
2693:
2692:
2690:
2688:
2683:
2673:
2668:
2652:
2651:
2650:
2637:
2615:
2611:
2604:
2599:
2598:
2586:
2585:
2576:
2541:
2539:
2538:
2533:
2528:
2527:
2508:
2503:
2482:
2481:
2460:
2459:
2442:
2440:
2439:
2434:
2429:
2428:
2409:
2404:
2383:
2382:
2361:
2360:
2343:
2341:
2340:
2335:
2333:
2332:
2322:
2317:
2299:
2298:
2279:
2277:
2276:
2271:
2269:
2268:
2248:
2246:
2245:
2240:
2238:
2237:
2221:
2219:
2218:
2213:
2211:
2210:
2191:
2189:
2188:
2183:
2175:
2174:
2148:
2146:
2145:
2140:
2138:
2137:
2125:
2124:
2112:
2111:
2090:
2088:
2087:
2082:
2080:
2079:
2067:
2066:
2054:
2053:
2030:
2028:
2027:
2022:
2020:
2019:
2001:
2000:
1988:
1987:
1942:
1940:
1939:
1934:
1932:
1927:
1920:
1915:
1914:
1892:
1890:
1881:
1880:
1866:
1858:
1837:
1835:
1834:
1829:
1782:
1780:
1779:
1774:
1759:
1757:
1756:
1751:
1746:
1744:
1743:
1731:
1727:
1726:
1704:
1671:
1669:
1668:
1663:
1642:
1640:
1639:
1634:
1629:
1627:
1626:
1614:
1610:
1609:
1587:
1554:
1552:
1551:
1546:
1528:
1526:
1525:
1520:
1515:
1511:
1510:
1478:
1477:
1461:
1459:
1458:
1453:
1383:
1381:
1380:
1375:
1373:
1372:
1366:
1363:
1359:
1350:
1344:
1341:
1322:
1321:
1311:
1294:
1291:
1282:
1257:
1248:
1242:
1241:
1232:
1229:
1225:
1222:
1203:
1202:
1192:
1175:
1172:
1163:
1119:
1116:
1104:
1102:
1101:
1096:
1078:
1076:
1075:
1070:
1047:
1045:
1044:
1039:
1034:
1032:
1031:
1030:
1014:
997:
993:
975:
972:
961:
959:
958:
953:
939:
930:
929:
915:. Then, for any
888:
886:
885:
880:
878:
877:
846:
844:
843:
838:
836:
810:
795:
793:
792:
787:
771:
769:
768:
763:
736:
734:
733:
728:
723:
721:
720:
708:
676:
650:
626:
624:
623:
618:
613:
611:
610:
601:
584:
570:
544:
523:
521:
520:
515:
493:
491:
490:
485:
480:
479:
406:
404:
403:
398:
370:
368:
367:
362:
336:
334:
333:
328:
323:
321:
307:
281:
209:
207:
206:
201:
186:
184:
183:
178:
173:
168:
151:
118:
116:
115:
110:
88:
86:
85:
80:
7850:
7849:
7845:
7844:
7843:
7841:
7840:
7839:
7825:
7824:
7811:
7806:
7805:
7789:
7788:
7784:
7736:
7735:
7731:
7717:
7716:
7712:
7702:
7701:
7697:
7669:
7668:
7664:
7626:
7625:
7621:
7611:
7610:
7606:
7599:
7576:
7575:
7571:
7561:
7560:
7556:
7546:
7544:
7533:
7525:
7524:
7520:
7484:
7483:
7479:
7463:
7462:
7458:
7451:
7436:
7435:
7431:
7397:
7396:
7392:
7381:
7377:
7372:
7312:
7298:
7297:
7278:
7277:
7216:
7212:
7204:
7203:
7177:
7157:
7156:
7120:
7115:
7114:
7095:
7094:
7069:
7068:
7037:
7036:
7008:
7007:
6988:
6987:
6977:
6934:
6903:
6889:
6834:
6808:
6804:
6796:
6795:
6768:
6767:
6733:
6728:
6727:
6708:
6707:
6688:
6687:
6655:
6654:
6601:
6591:
6538:
6533:
6532:
6504:
6499:
6498:
6483:be real-valued
6463:
6444:
6431:
6426:
6425:
6406:
6405:
6395:
6389:
6346:
6316:
6312:
6301:
6291:
6275:
6271:
6241:
6237:
6229:
6228:
6187:
6155:
6154:
6104:
6081:
6080:
6053:
6034:
6023:
6022:
5997:
5996:
5956:
5955:
5930:
5929:
5904:
5903:
5902:Then for every
5875:
5874:
5847:
5842:
5841:
5817:
5798:
5790:
5789:
5770:
5769:
5745:
5726:
5718:
5717:
5711:
5671:
5657:
5647:
5612:
5596:
5569:
5565:
5557:
5556:
5521:
5502:
5489:
5484:
5483:
5459:
5440:
5427:
5419:
5418:
5394:
5375:
5362:
5349:
5341:
5340:
5327:
5292:
5273:
5175:
5174:
5144:
5119:
5084:
5065:
5043:
5027:
5008:
4994:
4993:
4971:
4970:
4949:
4944:
4943:
4914:
4913:
4868:
4867:
4846:
4833:
4828:
4827:
4821:
4773: for
4748:
4740:
4707:
4691:
4690:
4664:
4659:
4658:
4637:
4632:
4631:
4599:
4589:
4588:
4567:
4562:
4561:
4468:
4461:
4451:
4445:
4441:
4413:
4400:
4389:
4388:
4356:
4340:
4321:
4316:
4315:
4294:
4289:
4288:
4195:
4188:
4178:
4172:
4168:
4137:
4124:
4113:
4112:
4076:
4075:
4048:
4032:
4013:
4008:
4007:
3986:
3981:
3980:
3950:
3939:
3890:
3879:
3865:
3864:
3807:
3806:
3787:
3786:
3780:
3776:
3738:
3725:
3719:
3715:
3707:
3706:
3619:
3618:
3583:
3575:
3569:
3554:
3544:
3538:
3534:
3496:
3483:
3477:
3473:
3465:
3464:
3414:
3410:
3399:
3395:
3389:
3385:
3328:
3317:
3313:
3307:
3303:
3265:
3252:
3246:
3242:
3234:
3233:
3197:
3184:
3179:
3178:
3142:
3123:
3104:
3099:
3098:
3053:
3049:
3038:
3034:
3028:
3024:
2967:
2956:
2952:
2946:
2942:
2904:
2891:
2885:
2881:
2873:
2872:
2836:
2823:
2818:
2817:
2792:
2779:
2774:
2773:
2739:
2735:
2724:
2720:
2714:
2710:
2653:
2642:
2638:
2632:
2628:
2590:
2577:
2571:
2567:
2559:
2558:
2519:
2473:
2451:
2446:
2445:
2420:
2374:
2352:
2347:
2346:
2324:
2290:
2285:
2284:
2260:
2255:
2254:
2229:
2224:
2223:
2202:
2197:
2196:
2166:
2152:
2151:
2129:
2116:
2103:
2098:
2097:
2071:
2058:
2045:
2040:
2039:
2011:
1992:
1979:
1974:
1973:
1970:
1950:Main articles:
1948:
1906:
1893:
1840:
1839:
1799:
1798:
1795:
1789:
1765:
1764:
1732:
1715:
1705:
1677:
1676:
1648:
1647:
1615:
1598:
1588:
1560:
1559:
1531:
1530:
1499:
1495:
1469:
1464:
1463:
1444:
1443:
1436:
1430:
1428:Chernoff bounds
1425:
1419:
1414:
1408:
1396:
1390:
1368:
1367:
1360:
1313:
1312:
1295:
1277:
1276:
1233:
1226:
1194:
1193:
1176:
1154:
1110:
1109:
1081:
1080:
1061:
1060:
1057:
1022:
1018:
983:
979:
966:
965:
917:
916:
901:
895:
869:
849:
848:
801:
800:
778:
777:
742:
741:
712:
635:
634:
602:
585:
529:
528:
500:
499:
471:
415:
414:
377:
376:
353:
352:
349:
343:
308:
282:
215:
214:
192:
191:
152:
124:
123:
95:
94:
71:
70:
67:
61:
29:random variable
17:
12:
11:
5:
7848:
7846:
7838:
7837:
7827:
7826:
7823:
7822:
7810:
7809:External links
7807:
7804:
7803:
7782:
7745:(3): 757–777.
7729:
7710:
7695:
7682:(3): 871–884.
7662:
7619:
7604:
7597:
7569:
7554:
7518:
7477:
7456:
7449:
7429:
7410:(1): 374–377.
7390:
7374:
7373:
7371:
7368:
7366:inequalities.
7319:
7315:
7311:
7308:
7305:
7285:
7274:
7273:
7272:
7271:
7260:
7254:
7250:
7245:
7241:
7237:
7234:
7231:
7228:
7225:
7222:
7219:
7215:
7211:
7184:
7180:
7176:
7173:
7170:
7167:
7164:
7142:
7139:
7136:
7133:
7130:
7127:
7123:
7102:
7082:
7079:
7076:
7056:
7053:
7050:
7047:
7044:
7021:
7017:
6995:
6976:
6973:
6972:
6971:
6970:
6969:
6958:
6953:
6950:
6947:
6940:
6937:
6933:
6925:
6922:
6910:
6906:
6902:
6899:
6896:
6892:
6888:
6884:
6880:
6877:
6872:
6867:
6864:
6861:
6858:
6855:
6852:
6849:
6846:
6841:
6837:
6831:
6823:
6819:
6816:
6812:
6807:
6803:
6775:
6764:average number
6751:
6748:
6745:
6740:
6736:
6715:
6695:
6671:
6668:
6665:
6662:
6651:
6650:
6639:
6635:
6631:
6628:
6624:
6619:
6616:
6613:
6608:
6604:
6600:
6595:
6588:
6583:
6580:
6577:
6573:
6567:
6564:
6559:
6556:
6553:
6550:
6545:
6541:
6511:
6507:
6470:
6466:
6462:
6459:
6456:
6451:
6447:
6443:
6438:
6434:
6413:
6391:Main article:
6388:
6385:
6384:
6383:
6382:
6381:
6370:
6365:
6362:
6359:
6356:
6353:
6349:
6345:
6342:
6338:
6334:
6331:
6323:
6319:
6315:
6308:
6304:
6298:
6294:
6290:
6287:
6282:
6278:
6274:
6266:
6263:
6260:
6255:
6252:
6249:
6245:
6240:
6236:
6211:
6208:
6205:
6202:
6199:
6194:
6190:
6184:
6181:
6178:
6173:
6170:
6167:
6163:
6142:
6139:
6136:
6133:
6130:
6127:
6124:
6121:
6117:
6111:
6107:
6103:
6100:
6097:
6094:
6091:
6088:
6066:
6063:
6060:
6056:
6052:
6049:
6046:
6041:
6037:
6033:
6030:
6010:
6007:
6004:
5984:
5981:
5978:
5975:
5972:
5969:
5966:
5963:
5943:
5940:
5937:
5917:
5914:
5911:
5891:
5888:
5885:
5882:
5862:
5859:
5854:
5850:
5829:
5824:
5820:
5816:
5813:
5810:
5805:
5801:
5797:
5777:
5757:
5752:
5748:
5744:
5741:
5738:
5733:
5729:
5725:
5710:
5707:
5699:
5698:
5697:
5696:
5685:
5678:
5674:
5670:
5667:
5664:
5660:
5654:
5650:
5646:
5642:
5638:
5635:
5632:
5629:
5625:
5619:
5615:
5611:
5608:
5603:
5599:
5594:
5588:
5583:
5580:
5577:
5573:
5568:
5564:
5539:
5536:
5533:
5528:
5524:
5520:
5517:
5514:
5509:
5505:
5501:
5496:
5492:
5482:and satisfies
5471:
5466:
5462:
5458:
5455:
5452:
5447:
5443:
5439:
5434:
5430:
5426:
5406:
5401:
5397:
5393:
5390:
5387:
5382:
5378:
5374:
5369:
5365:
5361:
5356:
5352:
5348:
5326:
5323:
5319:
5318:
5307:
5304:
5299:
5295:
5291:
5286:
5283:
5280:
5276:
5272:
5269:
5266:
5263:
5260:
5257:
5254:
5251:
5248:
5245:
5240:
5235:
5232:
5229:
5225:
5219:
5216:
5211:
5208:
5205:
5202:
5199:
5196:
5193:
5189:
5186:
5183:
5159:
5156:
5151:
5147:
5143:
5140:
5137:
5132:
5129:
5126:
5122:
5118:
5114:
5110:
5106:
5102:
5097:
5094:
5091:
5087:
5083:
5080:
5077:
5072:
5068:
5064:
5061:
5056:
5053:
5050:
5046:
5042:
5039:
5034:
5030:
5026:
5023:
5020:
5015:
5011:
5007:
5004:
5001:
4978:
4956:
4952:
4930:
4926:
4922:
4900:
4896:
4892:
4888:
4884:
4880:
4876:
4853:
4849:
4845:
4840:
4836:
4820:
4817:
4810:
4809:
4808:
4807:
4796:
4793:
4790:
4787:
4784:
4781:
4778:
4768:
4765:
4761:
4755:
4751:
4747:
4743:
4739:
4736:
4733:
4730:
4727:
4724:
4720:
4714:
4710:
4705:
4701:
4698:
4671:
4667:
4644:
4640:
4619:
4616:
4612:
4606:
4602:
4597:
4574:
4570:
4558:
4557:
4556:
4555:
4543:
4536:
4533:
4529:
4525:
4522:
4519:
4514:
4509:
4505:
4499:
4494:
4491:
4488:
4484:
4480:
4475:
4471:
4467:
4464:
4458:
4454:
4448:
4444:
4440:
4437:
4434:
4431:
4428:
4425:
4420:
4416:
4412:
4407:
4403:
4399:
4396:
4371:
4368:
4363:
4359:
4355:
4352:
4347:
4343:
4339:
4336:
4333:
4328:
4324:
4301:
4297:
4285:
4284:
4283:
4282:
4270:
4263:
4260:
4256:
4252:
4249:
4246:
4241:
4236:
4232:
4226:
4221:
4218:
4215:
4211:
4207:
4202:
4198:
4194:
4191:
4185:
4181:
4175:
4171:
4167:
4164:
4161:
4158:
4155:
4152:
4149:
4144:
4140:
4136:
4131:
4127:
4123:
4120:
4095:
4092:
4089:
4086:
4083:
4063:
4060:
4055:
4051:
4047:
4044:
4039:
4035:
4031:
4028:
4025:
4020:
4016:
3993:
3989:
3964:
3957:
3953:
3949:
3946:
3942:
3938:
3935:
3932:
3926:
3921:
3918:
3915:
3911:
3907:
3904:
3897:
3893:
3889:
3886:
3882:
3878:
3875:
3872:
3858:
3857:
3856:
3855:
3843:
3836:
3832:
3828:
3825:
3822:
3819:
3814:
3810:
3804:
3800:
3794:
3790:
3783:
3779:
3775:
3772:
3769:
3766:
3762:
3758:
3755:
3751:
3745:
3741:
3737:
3732:
3728:
3723:
3718:
3714:
3694:
3693:
3692:
3691:
3680:
3677:
3674:
3671:
3668:
3665:
3662:
3659:
3656:
3653:
3650:
3647:
3644:
3641:
3638:
3635:
3632:
3629:
3626:
3606:
3602:
3597:
3590:
3586:
3581:
3578:
3572:
3568:
3561:
3557:
3551:
3547:
3541:
3537:
3533:
3530:
3527:
3524:
3520:
3516:
3513:
3509:
3503:
3499:
3495:
3490:
3486:
3481:
3476:
3472:
3445:
3444:
3443:
3442:
3430:
3421:
3417:
3413:
3406:
3402:
3398:
3392:
3388:
3384:
3381:
3378:
3375:
3371:
3362:
3357:
3353:
3347:
3342:
3339:
3336:
3332:
3324:
3320:
3316:
3310:
3306:
3302:
3299:
3296:
3293:
3289:
3285:
3282:
3278:
3272:
3268:
3264:
3259:
3255:
3250:
3245:
3241:
3212:
3209:
3204:
3200:
3196:
3191:
3187:
3154:
3149:
3145:
3141:
3138:
3135:
3130:
3126:
3122:
3119:
3116:
3111:
3107:
3092:submartingales
3084:
3083:
3082:
3081:
3069:
3060:
3056:
3052:
3045:
3041:
3037:
3031:
3027:
3023:
3020:
3017:
3014:
3010:
3001:
2996:
2992:
2986:
2981:
2978:
2975:
2971:
2963:
2959:
2955:
2949:
2945:
2941:
2938:
2935:
2932:
2928:
2924:
2921:
2917:
2911:
2907:
2903:
2898:
2894:
2889:
2884:
2880:
2851:
2848:
2843:
2839:
2835:
2830:
2826:
2799:
2795:
2791:
2786:
2782:
2770:
2769:
2768:
2767:
2755:
2746:
2742:
2738:
2731:
2727:
2723:
2717:
2713:
2709:
2706:
2703:
2700:
2696:
2687:
2682:
2678:
2672:
2667:
2664:
2661:
2657:
2649:
2645:
2641:
2635:
2631:
2627:
2624:
2621:
2618:
2614:
2610:
2607:
2603:
2597:
2593:
2589:
2584:
2580:
2575:
2570:
2566:
2543:
2542:
2531:
2526:
2522:
2518:
2515:
2512:
2507:
2502:
2499:
2496:
2492:
2488:
2485:
2480:
2476:
2472:
2469:
2466:
2463:
2458:
2454:
2443:
2432:
2427:
2423:
2419:
2416:
2413:
2408:
2403:
2400:
2397:
2393:
2389:
2386:
2381:
2377:
2373:
2370:
2367:
2364:
2359:
2355:
2344:
2331:
2327:
2321:
2316:
2313:
2310:
2306:
2302:
2297:
2293:
2280:its variance:
2267:
2263:
2251:expected value
2236:
2232:
2222:be their sum,
2209:
2205:
2193:
2192:
2181:
2178:
2173:
2169:
2165:
2162:
2159:
2149:
2136:
2132:
2128:
2123:
2119:
2115:
2110:
2106:
2095:
2078:
2074:
2070:
2065:
2061:
2057:
2052:
2048:
2018:
2014:
2010:
2007:
2004:
1999:
1995:
1991:
1986:
1982:
1947:
1944:
1930:
1926:
1923:
1919:
1913:
1909:
1905:
1902:
1899:
1896:
1887:
1884:
1878:
1875:
1872:
1869:
1865:
1861:
1857:
1853:
1850:
1847:
1827:
1824:
1821:
1818:
1815:
1812:
1809:
1806:
1791:Main article:
1788:
1785:
1772:
1761:
1760:
1749:
1742:
1739:
1735:
1730:
1725:
1722:
1718:
1714:
1711:
1708:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1661:
1658:
1655:
1646:and for every
1644:
1643:
1632:
1625:
1622:
1618:
1613:
1608:
1605:
1601:
1597:
1594:
1591:
1585:
1582:
1579:
1576:
1573:
1570:
1567:
1544:
1541:
1538:
1518:
1514:
1509:
1506:
1502:
1498:
1493:
1490:
1487:
1484:
1481:
1476:
1472:
1451:
1434:Chernoff bound
1432:Main article:
1429:
1426:
1421:Main article:
1418:
1415:
1410:Main article:
1407:
1404:
1392:Main article:
1389:
1386:
1385:
1384:
1371:
1361:
1356:
1353:
1347:
1340:
1337:
1334:
1331:
1328:
1325:
1320:
1316:
1310:
1307:
1304:
1301:
1298:
1288:
1285:
1279:
1278:
1275:
1272:
1269:
1266:
1263:
1260:
1254:
1251:
1245:
1240:
1236:
1227:
1221:
1218:
1215:
1212:
1209:
1206:
1201:
1197:
1191:
1188:
1185:
1182:
1179:
1169:
1166:
1160:
1159:
1157:
1152:
1149:
1146:
1143:
1140:
1137:
1134:
1131:
1128:
1125:
1122:
1094:
1091:
1088:
1068:
1056:
1053:
1049:
1048:
1037:
1029:
1025:
1021:
1017:
1012:
1009:
1006:
1003:
1000:
996:
992:
989:
986:
982:
978:
951:
948:
945:
942:
936:
933:
927:
924:
897:Main article:
894:
891:
876:
872:
868:
865:
862:
859:
856:
835:
831:
828:
825:
822:
819:
816:
813:
809:
785:
761:
758:
755:
752:
749:
738:
737:
726:
719:
715:
711:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
675:
671:
668:
665:
662:
659:
656:
653:
649:
645:
642:
628:
627:
616:
609:
605:
600:
597:
594:
591:
588:
582:
579:
576:
573:
569:
565:
562:
559:
556:
553:
550:
547:
543:
539:
536:
513:
510:
507:
496:
495:
483:
478:
474:
470:
467:
464:
461:
458:
455:
452:
449:
446:
443:
440:
437:
434:
431:
428:
425:
422:
408:
396:
393:
390:
387:
384:
360:
345:Main article:
342:
339:
338:
337:
326:
320:
317:
314:
311:
306:
303:
300:
297:
294:
291:
288:
285:
279:
276:
273:
270:
267:
264:
261:
258:
255:
252:
249:
246:
243:
240:
237:
234:
231:
228:
225:
222:
199:
188:
187:
176:
171:
167:
164:
161:
158:
155:
149:
146:
143:
140:
137:
134:
131:
108:
105:
102:
78:
63:Main article:
60:
57:
33:expected value
15:
13:
10:
9:
6:
4:
3:
2:
7847:
7836:
7833:
7832:
7830:
7821:
7817:
7813:
7812:
7808:
7798:
7793:
7786:
7783:
7778:
7774:
7770:
7766:
7762:
7758:
7753:
7748:
7744:
7740:
7733:
7730:
7725:
7721:
7714:
7711:
7706:
7699:
7696:
7690:
7685:
7681:
7677:
7673:
7666:
7663:
7657:
7652:
7647:
7642:
7638:
7634:
7630:
7623:
7620:
7615:
7608:
7605:
7600:
7594:
7590:
7586:
7582:
7581:
7573:
7570:
7565:
7558:
7555:
7543:
7539:
7532:
7528:
7522:
7519:
7514:
7510:
7505:
7500:
7496:
7492:
7488:
7481:
7478:
7472:
7467:
7460:
7457:
7452:
7450:0-521-83540-2
7446:
7442:
7441:
7433:
7430:
7425:
7421:
7417:
7413:
7409:
7405:
7401:
7394:
7391:
7388:
7386:
7379:
7376:
7369:
7367:
7365:
7361:
7360:Paley–Zygmund
7357:
7352:
7350:
7346:
7342:
7338:
7333:
7317:
7309:
7306:
7283:
7258:
7252:
7248:
7243:
7239:
7235:
7232:
7226:
7223:
7220:
7213:
7202:
7201:
7200:
7199:
7198:
7182:
7174:
7171:
7165:
7162:
7137:
7134:
7131:
7125:
7121:
7100:
7080:
7077:
7074:
7054:
7051:
7048:
7045:
7042:
7019:
7015:
6993:
6985:
6981:
6974:
6956:
6951:
6948:
6945:
6938:
6935:
6931:
6923:
6920:
6908:
6904:
6900:
6897:
6894:
6890:
6886:
6882:
6878:
6875:
6862:
6856:
6853:
6847:
6839:
6835:
6817:
6814:
6805:
6794:
6793:
6792:
6791:
6790:
6787:
6773:
6765:
6746:
6738:
6734:
6713:
6693:
6685:
6666:
6660:
6637:
6629:
6626:
6622:
6614:
6611:
6606:
6602:
6586:
6581:
6578:
6575:
6571:
6565:
6562:
6557:
6551:
6543:
6539:
6531:
6530:
6529:
6527:
6509:
6505:
6496:
6493:
6489:
6486:
6468:
6464:
6460:
6457:
6454:
6449:
6445:
6441:
6436:
6432:
6411:
6402:
6400:
6394:
6386:
6368:
6363:
6360:
6357:
6354:
6351:
6347:
6343:
6340:
6336:
6332:
6329:
6321:
6317:
6313:
6306:
6296:
6292:
6288:
6285:
6280:
6276:
6264:
6261:
6258:
6253:
6250:
6247:
6243:
6238:
6227:
6226:
6225:
6224:
6223:
6209:
6206:
6203:
6200:
6197:
6192:
6188:
6182:
6179:
6176:
6171:
6168:
6165:
6161:
6137:
6134:
6131:
6128:
6125:
6122:
6119:
6109:
6105:
6095:
6092:
6089:
6086:
6064:
6061:
6058:
6054:
6050:
6047:
6044:
6039:
6035:
6031:
6028:
6008:
6005:
6002:
5982:
5979:
5976:
5973:
5970:
5967:
5964:
5961:
5941:
5938:
5935:
5915:
5912:
5909:
5889:
5886:
5883:
5880:
5860:
5857:
5852:
5848:
5822:
5818:
5814:
5811:
5808:
5803:
5799:
5775:
5750:
5746:
5742:
5739:
5736:
5731:
5727:
5714:
5708:
5706:
5704:
5683:
5676:
5672:
5668:
5665:
5662:
5658:
5652:
5648:
5644:
5640:
5636:
5633:
5630:
5627:
5617:
5613:
5609:
5606:
5601:
5597:
5586:
5581:
5578:
5575:
5571:
5566:
5555:
5554:
5553:
5552:
5551:
5537:
5534:
5531:
5526:
5522:
5518:
5515:
5512:
5507:
5503:
5499:
5494:
5490:
5464:
5460:
5456:
5453:
5450:
5445:
5441:
5437:
5432:
5428:
5399:
5395:
5391:
5388:
5385:
5380:
5376:
5372:
5367:
5363:
5359:
5354:
5350:
5337:
5335:
5331:
5324:
5322:
5305:
5297:
5281:
5274:
5267:
5264:
5258:
5252:
5243:
5238:
5233:
5230:
5227:
5223:
5217:
5214:
5209:
5200:
5194:
5173:
5172:
5171:
5157:
5149:
5145:
5141:
5138:
5135:
5130:
5127:
5124:
5120:
5116:
5112:
5108:
5104:
5100:
5095:
5092:
5089:
5085:
5081:
5078:
5075:
5070:
5066:
5059:
5051:
5044:
5040:
5032:
5028:
5024:
5021:
5018:
5013:
5009:
5002:
4999:
4990:
4976:
4954:
4950:
4928:
4924:
4920:
4898:
4894:
4890:
4886:
4882:
4878:
4874:
4851:
4847:
4843:
4838:
4834:
4826:Suppose that
4824:
4818:
4816:
4815:
4794:
4791:
4788:
4785:
4782:
4779:
4776:
4766:
4763:
4759:
4753:
4749:
4745:
4741:
4737:
4734:
4728:
4725:
4722:
4712:
4708:
4689:
4688:
4687:
4686:
4685:
4669:
4665:
4642:
4638:
4617:
4614:
4604:
4600:
4572:
4568:
4541:
4531:
4527:
4523:
4520:
4517:
4512:
4507:
4503:
4497:
4492:
4489:
4486:
4482:
4478:
4473:
4469:
4462:
4456:
4452:
4446:
4442:
4438:
4435:
4432:
4426:
4423:
4418:
4414:
4410:
4405:
4401:
4387:
4386:
4385:
4384:
4383:
4369:
4366:
4361:
4357:
4353:
4345:
4341:
4334:
4331:
4326:
4322:
4299:
4295:
4268:
4258:
4254:
4250:
4247:
4244:
4239:
4234:
4230:
4224:
4219:
4216:
4213:
4209:
4205:
4200:
4196:
4189:
4183:
4179:
4173:
4169:
4165:
4162:
4159:
4153:
4150:
4147:
4142:
4138:
4134:
4129:
4125:
4111:
4110:
4109:
4108:
4107:
4093:
4090:
4087:
4084:
4081:
4061:
4058:
4053:
4049:
4045:
4037:
4033:
4026:
4023:
4018:
4014:
3991:
3987:
3977:
3955:
3951:
3947:
3944:
3940:
3933:
3924:
3919:
3916:
3913:
3909:
3905:
3895:
3891:
3887:
3884:
3880:
3873:
3861:
3841:
3834:
3830:
3826:
3823:
3820:
3817:
3812:
3808:
3802:
3798:
3792:
3788:
3781:
3777:
3773:
3770:
3767:
3764:
3760:
3756:
3753:
3743:
3739:
3735:
3730:
3726:
3716:
3705:
3704:
3703:
3702:
3701:
3699:
3678:
3675:
3669:
3666:
3663:
3657:
3654:
3648:
3645:
3642:
3636:
3630:
3624:
3604:
3600:
3595:
3588:
3584:
3579:
3576:
3570:
3566:
3559:
3555:
3549:
3545:
3539:
3535:
3531:
3528:
3525:
3522:
3518:
3514:
3511:
3501:
3497:
3493:
3488:
3484:
3474:
3463:
3462:
3461:
3460:
3459:
3457:
3453:
3448:
3428:
3419:
3415:
3411:
3404:
3400:
3396:
3390:
3386:
3382:
3379:
3376:
3373:
3369:
3360:
3355:
3351:
3345:
3340:
3337:
3334:
3330:
3322:
3318:
3314:
3308:
3304:
3300:
3297:
3294:
3291:
3287:
3283:
3280:
3270:
3266:
3262:
3257:
3253:
3243:
3232:
3231:
3230:
3229:
3228:
3226:
3210:
3207:
3202:
3198:
3194:
3189:
3185:
3176:
3172:
3168:
3147:
3143:
3139:
3136:
3133:
3128:
3124:
3117:
3114:
3109:
3105:
3095:
3093:
3089:
3067:
3058:
3054:
3050:
3043:
3039:
3035:
3029:
3025:
3021:
3018:
3015:
3012:
3008:
2999:
2994:
2990:
2984:
2979:
2976:
2973:
2969:
2961:
2957:
2953:
2947:
2943:
2939:
2936:
2933:
2930:
2926:
2922:
2919:
2909:
2905:
2901:
2896:
2892:
2882:
2871:
2870:
2869:
2868:
2867:
2865:
2849:
2846:
2841:
2837:
2833:
2828:
2824:
2815:
2797:
2793:
2789:
2784:
2780:
2753:
2744:
2740:
2736:
2729:
2725:
2721:
2715:
2711:
2707:
2704:
2701:
2698:
2694:
2685:
2680:
2676:
2670:
2665:
2662:
2659:
2655:
2647:
2643:
2639:
2633:
2629:
2625:
2622:
2619:
2616:
2612:
2608:
2605:
2595:
2591:
2587:
2582:
2578:
2568:
2557:
2556:
2555:
2554:
2553:
2551:
2546:
2524:
2520:
2513:
2510:
2505:
2500:
2497:
2494:
2490:
2486:
2478:
2474:
2467:
2464:
2461:
2456:
2452:
2444:
2425:
2421:
2414:
2406:
2401:
2398:
2395:
2391:
2387:
2379:
2375:
2368:
2362:
2357:
2353:
2345:
2329:
2325:
2319:
2314:
2311:
2308:
2304:
2300:
2295:
2291:
2283:
2282:
2281:
2265:
2261:
2252:
2234:
2230:
2207:
2203:
2179:
2176:
2171:
2167:
2163:
2160:
2150:
2134:
2130:
2126:
2121:
2117:
2113:
2108:
2104:
2096:
2093:
2092:almost surely
2076:
2072:
2068:
2063:
2059:
2055:
2050:
2046:
2038:
2037:
2036:
2034:
2016:
2012:
2008:
2005:
2002:
1997:
1993:
1989:
1984:
1980:
1969:
1965:
1961:
1957:
1953:
1945:
1943:
1928:
1921:
1917:
1911:
1907:
1903:
1897:
1894:
1885:
1882:
1876:
1870:
1867:
1859:
1848:
1822:
1819:
1816:
1810:
1807:
1804:
1794:
1784:
1770:
1747:
1740:
1737:
1733:
1723:
1720:
1716:
1709:
1700:
1694:
1691:
1688:
1675:
1674:
1673:
1659:
1656:
1653:
1630:
1623:
1620:
1616:
1606:
1603:
1599:
1592:
1583:
1577:
1574:
1571:
1558:
1557:
1556:
1542:
1539:
1536:
1516:
1512:
1507:
1504:
1500:
1496:
1488:
1482:
1474:
1470:
1462:, defined as
1449:
1441:
1435:
1427:
1424:
1413:
1403:
1401:
1395:
1387:
1354:
1351:
1345:
1335:
1329:
1326:
1323:
1318:
1314:
1305:
1299:
1296:
1286:
1283:
1273:
1267:
1261:
1258:
1252:
1249:
1243:
1238:
1234:
1216:
1210:
1207:
1204:
1199:
1195:
1186:
1180:
1177:
1167:
1164:
1155:
1150:
1144:
1141:
1135:
1129:
1126:
1123:
1108:
1107:
1106:
1092:
1089:
1086:
1066:
1054:
1052:
1035:
1027:
1023:
1019:
1015:
1010:
1004:
1001:
998:
994:
990:
987:
984:
980:
964:
963:
962:
949:
946:
943:
940:
934:
931:
925:
922:
914:
910:
906:
900:
892:
890:
874:
870:
866:
860:
826:
820:
814:
811:
797:
783:
775:
756:
750:
747:
724:
717:
713:
709:
704:
695:
689:
686:
683:
680:
677:
666:
660:
654:
651:
633:
632:
631:
614:
607:
603:
595:
589:
586:
580:
574:
571:
560:
554:
548:
545:
527:
526:
525:
511:
508:
505:
476:
465:
459:
453:
450:
441:
435:
429:
423:
420:
413:
409:
391:
385:
374:
373:
372:
358:
348:
324:
315:
298:
286:
277:
268:
259:
253:
238:
232:
229:
226:
213:
212:
211:
174:
169:
162:
156:
147:
141:
138:
135:
122:
121:
120:
106:
103:
100:
92:
91:almost surely
76:
66:
56:
53:
51:
46:
41:
38:
34:
30:
26:
22:
7785:
7742:
7738:
7732:
7713:
7698:
7679:
7675:
7665:
7636:
7632:
7622:
7613:
7607:
7579:
7572:
7563:
7557:
7545:. Retrieved
7537:
7521:
7494:
7490:
7480:
7459:
7439:
7432:
7407:
7403:
7393:
7384:
7378:
7353:
7349:graph theory
7340:
7334:
7275:
6983:
6979:
6978:
6788:
6763:
6683:
6652:
6494:
6403:
6396:
5715:
5712:
5700:
5338:
5328:
5320:
4991:
4825:
4822:
4811:
4587:are i.i.d.,
4559:
4286:
3978:
3862:
3859:
3695:
3455:
3449:
3446:
3174:
3170:
3166:
3096:
3085:
2771:
2547:
2544:
2194:
2032:
1971:
1796:
1762:
1645:
1437:
1399:
1397:
1058:
1050:
912:
908:
904:
902:
798:
739:
629:
497:
350:
189:
68:
54:
42:
36:
24:
18:
7797:0909.2586v1
6984:upper bound
6528:defined by
6079:satisfying
3700:says that:
2552:says that:
7752:1807.05202
7646:2101.02841
7547:August 14,
7527:Chung, Fan
7471:2102.07234
7370:References
7364:Khintchine
7356:Rademacher
7155:values of
6497:(·). Let
5840:such that
4314:satisfies
2814:martingale
1364:otherwise.
494:is finite.
407:is finite.
7818:" —
7639:(3): 44.
7504:1311.6273
7424:0377-2217
7307:±
7244:≤
7230:⟩
7218:⟨
7172:±
7166:∈
7138:δ
7135:−
7049:δ
7043:β
6949:
6924:≥
6921:ε
6905:ε
6895:−
6887:≤
6879:ε
6854:−
6818:∈
6630:∈
6612:≤
6572:∑
6458:…
6364:λ
6358:−
6341:≤
6333:λ
6286:−
6262:−
6244:∑
6222:we have
6207:δ
6204:−
6198:≤
6180:−
6162:∑
6135:−
6129:≤
6123:≤
6087:λ
6062:−
6048:…
6029:λ
6006:≥
5936:δ
5812:…
5740:…
5673:ε
5663:−
5645:≤
5637:ε
5628:≥
5607:−
5572:∑
5516:⋯
5454:…
5389:…
5265:−
5224:∑
5210:≤
5139:…
5093:−
5079:…
5022:…
4887:…
4844:…
4792:σ
4786:≤
4780:≤
4746:−
4735:≤
4729:σ
4723:≥
4639:σ
4615:≤
4524:λ
4483:∑
4453:λ
4447:−
4439:
4433:≤
4427:λ
4411:−
4332:≤
4251:λ
4210:∑
4180:λ
4174:−
4166:
4160:≤
4154:λ
4151:−
4135:−
4091:≤
4085:≤
4059:−
4046:−
4024:≥
3948:⋅
3934:
3910:∏
3888:⋅
3874:
3824:⋅
3782:−
3774:
3736:−
3676:−
3658:
3540:−
3532:
3523:≤
3494:−
3391:−
3383:
3331:∑
3309:−
3301:
3263:−
3223:. Hence,
3195:−
3137:…
3030:−
3022:
2970:∑
2948:−
2940:
2902:−
2834:−
2790:−
2716:−
2708:
2699:≤
2656:∑
2634:−
2626:
2617:≤
2588:−
2514:
2491:∑
2468:
2415:
2392:∑
2369:
2305:∑
2177:≤
2158:∀
2127:−
2069:≤
2056:≤
2006:…
1904:−
1898:
1886:π
1877:≤
1849:
1808:∼
1710:
1701:≤
1692:≤
1593:
1584:≤
1575:≥
1346:−
1330:
1300:
1262:
1244:≥
1230:for
1211:
1181:
1151:≤
1142:≥
1127:−
1090:≥
1024:λ
1011:≤
1005:σ
1002:λ
999:≥
991:μ
988:−
947:…
923:λ
855:Φ
821:
815:−
751:
705:≤
690:
684:⋅
678:≥
661:
655:−
590:
581:≤
572:≥
555:
549:−
460:
454:−
442:
424:
386:
310:Φ
293:Φ
287:
278:≤
263:Φ
260:≥
248:Φ
230:≥
198:Φ
157:
148:≤
139:≥
7829:Category
7777:54065186
7362:and the
5113:′
4929:′
4899:′
4883:′
4006:satisfy
412:variance
37:equality
7757:Bibcode
6762:is the
944:1.63299
772:is the
7775:
7595:
7447:
7422:
7347:) and
7276:where
6726:, and
6684:single
6424:, let
5550:then
4074:, for
3617:where
2816:, and
1966:, and
1838:. Then
740:where
7792:arXiv
7773:S2CID
7747:arXiv
7641:arXiv
7633:Games
7534:(PDF)
7499:arXiv
7466:arXiv
6789:Then
6490:with
5170:Then
1400:lower
847:with
7593:ISBN
7549:2018
7445:ISBN
7420:ISSN
7341:e.g.
7078:>
7052:>
6876:>
6330:>
6153:and
6090:>
6021:and
5977:>
5939:>
5928:and
5913:>
5884:<
5873:for
5858:>
5788:and
4992:Let
4942:and
4630:and
4424:>
4148:<
3765:<
3754:>
3512:>
3374:<
3292:<
3281:>
3208:<
3090:and
3013:<
2931:<
2920:>
2606:>
2253:and
2249:its
2195:Let
1972:Let
1868:>
1797:Let
1657:<
1540:>
1079:and
926:>
903:Let
509:>
410:The
104:>
69:Let
50:mean
7765:doi
7684:doi
7651:doi
7585:doi
7509:doi
7412:doi
7408:295
6811:sup
6653:So
6099:min
4560:If
4436:exp
4287:If
4163:exp
3771:exp
3655:log
3529:exp
3450:4.
3380:exp
3298:exp
3019:exp
2937:exp
2705:exp
2623:exp
2548:1.
2511:Var
2465:Var
1895:exp
1442:of
1327:Var
1297:Var
1259:Var
1208:Var
1178:Var
776:of
748:Std
687:Std
587:Var
421:Var
19:In
7831::
7771:.
7763:.
7755:.
7743:99
7741:.
7722:.
7680:15
7678:.
7674:.
7649:.
7637:13
7635:.
7631:.
7591:.
7540:.
7536:.
7507:.
7495:20
7493:.
7489:.
7418:.
7406:.
7402:.
7351:.
7332:.
7210:Pr
7197::
6946:ln
6802:Pr
6786:.
6401:.
6235:Pr
5705:.
5563:Pr
4989:.
4866:,
4697:Pr
4395:Pr
4119:Pr
3976:.
3713:Pr
3471:Pr
3240:Pr
2879:Pr
2565:Pr
2462::=
2363::=
2301::=
2114::=
2035::
1962:,
1958:,
1954:,
1683:Pr
1672::
1566:Pr
1555::
1489::=
1117:Pr
973:Pr
889:.
796:.
641:Pr
535:Pr
524:,
371::
242:Pr
221:Pr
130:Pr
119:,
52:.
23:,
7800:.
7794::
7779:.
7767::
7759::
7749::
7726:.
7692:.
7686::
7659:.
7653::
7643::
7601:.
7587::
7551:.
7515:.
7511::
7501::
7474:.
7468::
7453:.
7426:.
7414::
7339:(
7318:n
7314:}
7310:1
7304:{
7284:Y
7259:,
7253:n
7249:C
7240:)
7236:k
7233:=
7227:Y
7224:,
7221:x
7214:(
7183:n
7179:}
7175:1
7169:{
7163:x
7141:)
7132:1
7129:(
7126:n
7122:2
7101:k
7081:0
7075:C
7055:0
7046:,
7020:n
7016:1
6994:n
6957:.
6952:2
6939:n
6936:2
6932:1
6909:2
6901:n
6898:2
6891:e
6883:)
6871:)
6866:)
6863:x
6860:(
6857:F
6851:)
6848:x
6845:(
6840:n
6836:F
6830:(
6822:R
6815:x
6806:(
6774:x
6750:)
6747:x
6744:(
6739:n
6735:F
6714:x
6694:X
6670:)
6667:x
6664:(
6661:F
6638:.
6634:R
6627:x
6623:,
6618:}
6615:x
6607:i
6603:X
6599:{
6594:1
6587:n
6582:1
6579:=
6576:i
6566:n
6563:1
6558:=
6555:)
6552:x
6549:(
6544:n
6540:F
6510:n
6506:F
6495:F
6469:n
6465:X
6461:,
6455:,
6450:2
6446:X
6442:,
6437:1
6433:X
6412:n
6369:.
6361:c
6355:k
6352:b
6348:e
6344:a
6337:)
6322:i
6318:p
6314:n
6307:2
6303:)
6297:i
6293:p
6289:n
6281:i
6277:N
6273:(
6265:1
6259:k
6254:1
6251:=
6248:i
6239:(
6210:,
6201:1
6193:i
6189:p
6183:1
6177:k
6172:1
6169:=
6166:i
6141:}
6138:1
6132:k
6126:i
6120:1
6116:|
6110:i
6106:p
6102:{
6096:n
6093:C
6065:1
6059:k
6055:p
6051:,
6045:,
6040:1
6036:p
6032:,
6009:1
6003:n
5983:,
5980:0
5974:c
5971:,
5968:b
5965:,
5962:a
5942:0
5916:0
5910:C
5890:.
5887:k
5881:i
5861:0
5853:i
5849:p
5828:)
5823:k
5819:p
5815:,
5809:,
5804:1
5800:p
5796:(
5776:n
5756:)
5751:k
5747:N
5743:,
5737:,
5732:1
5728:N
5724:(
5684:.
5677:2
5669:M
5666:2
5659:e
5653:n
5649:2
5641:)
5634:M
5631:2
5624:|
5618:i
5614:p
5610:M
5602:i
5598:Z
5593:|
5587:n
5582:1
5579:=
5576:i
5567:(
5538:,
5535:M
5532:=
5527:n
5523:Z
5519:+
5513:+
5508:2
5504:Z
5500:+
5495:1
5491:Z
5470:)
5465:n
5461:p
5457:,
5451:,
5446:2
5442:p
5438:,
5433:1
5429:p
5425:(
5405:)
5400:n
5396:Z
5392:,
5386:,
5381:3
5377:Z
5373:,
5368:2
5364:Z
5360:,
5355:1
5351:Z
5347:(
5306:.
5303:]
5298:2
5294:)
5290:)
5285:)
5282:i
5279:(
5275:X
5271:(
5268:f
5262:)
5259:X
5256:(
5253:f
5250:(
5247:[
5244:E
5239:n
5234:1
5231:=
5228:i
5218:2
5215:1
5207:)
5204:)
5201:X
5198:(
5195:f
5192:(
5188:r
5185:a
5182:V
5158:.
5155:)
5150:n
5146:X
5142:,
5136:,
5131:1
5128:+
5125:i
5121:X
5117:,
5109:i
5105:X
5101:,
5096:1
5090:i
5086:X
5082:,
5076:,
5071:1
5067:X
5063:(
5060:=
5055:)
5052:i
5049:(
5045:X
5041:,
5038:)
5033:n
5029:X
5025:,
5019:,
5014:1
5010:X
5006:(
5003:=
5000:X
4977:i
4955:i
4951:X
4925:i
4921:X
4895:n
4891:X
4879:1
4875:X
4852:n
4848:X
4839:1
4835:X
4795:.
4789:2
4783:k
4777:0
4767:n
4764:4
4760:/
4754:2
4750:k
4742:e
4738:2
4732:]
4726:k
4719:|
4713:n
4709:S
4704:|
4700:[
4670:i
4666:X
4643:2
4618:1
4611:|
4605:i
4601:X
4596:|
4573:i
4569:X
4542:)
4535:)
4532:3
4528:/
4521:M
4518:+
4513:2
4508:i
4504:a
4498:n
4493:1
4490:=
4487:i
4479:+
4474:n
4470:V
4466:(
4463:2
4457:2
4443:(
4430:]
4419:n
4415:E
4406:n
4402:S
4398:[
4370:M
4367:+
4362:i
4358:a
4354:+
4351:)
4346:i
4342:X
4338:(
4335:E
4327:i
4323:X
4300:i
4296:X
4269:)
4262:)
4259:3
4255:/
4248:M
4245:+
4240:2
4235:i
4231:a
4225:n
4220:1
4217:=
4214:i
4206:+
4201:n
4197:V
4193:(
4190:2
4184:2
4170:(
4157:]
4143:n
4139:E
4130:n
4126:S
4122:[
4094:n
4088:i
4082:1
4062:M
4054:i
4050:a
4043:)
4038:i
4034:X
4030:(
4027:E
4019:i
4015:X
3992:i
3988:X
3963:]
3956:i
3952:X
3945:t
3941:e
3937:[
3931:E
3925:n
3920:1
3917:=
3914:i
3906:=
3903:]
3896:n
3892:S
3885:t
3881:e
3877:[
3871:E
3842:)
3835:3
3831:/
3827:t
3821:C
3818:+
3813:n
3809:V
3803:2
3799:/
3793:2
3789:t
3778:(
3768:2
3761:]
3757:t
3750:|
3744:n
3740:E
3731:n
3727:S
3722:|
3717:[
3679:u
3673:)
3670:u
3667:+
3664:1
3661:(
3652:)
3649:u
3646:+
3643:1
3640:(
3637:=
3634:)
3631:u
3628:(
3625:h
3605:,
3601:]
3596:)
3589:n
3585:V
3580:t
3577:C
3571:(
3567:h
3560:2
3556:C
3550:n
3546:V
3536:[
3526:2
3519:]
3515:t
3508:|
3502:n
3498:E
3489:n
3485:S
3480:|
3475:[
3456:C
3429:)
3420:2
3416:C
3412:n
3405:2
3401:t
3397:2
3387:(
3377:2
3370:)
3361:2
3356:i
3352:c
3346:n
3341:1
3338:=
3335:i
3323:2
3319:t
3315:2
3305:(
3295:2
3288:]
3284:t
3277:|
3271:n
3267:E
3258:n
3254:S
3249:|
3244:[
3211:C
3203:i
3199:a
3190:i
3186:b
3175:f
3171:i
3167:n
3153:)
3148:n
3144:X
3140:,
3134:,
3129:1
3125:X
3121:(
3118:f
3115:=
3110:n
3106:S
3068:)
3059:2
3055:C
3051:n
3044:2
3040:t
3036:2
3026:(
3016:2
3009:)
3000:2
2995:i
2991:c
2985:n
2980:1
2977:=
2974:i
2962:2
2958:t
2954:2
2944:(
2934:2
2927:]
2923:t
2916:|
2910:n
2906:E
2897:n
2893:S
2888:|
2883:[
2850:0
2847:=
2842:0
2838:E
2829:0
2825:S
2798:n
2794:E
2785:n
2781:S
2754:)
2745:2
2741:C
2737:n
2730:2
2726:t
2722:2
2712:(
2702:2
2695:)
2686:2
2681:i
2677:c
2671:n
2666:1
2663:=
2660:i
2648:2
2644:t
2640:2
2630:(
2620:2
2613:]
2609:t
2602:|
2596:n
2592:E
2583:n
2579:S
2574:|
2569:[
2530:]
2525:i
2521:X
2517:[
2506:n
2501:1
2498:=
2495:i
2487:=
2484:]
2479:n
2475:S
2471:[
2457:n
2453:V
2431:]
2426:i
2422:X
2418:[
2412:E
2407:n
2402:1
2399:=
2396:i
2388:=
2385:]
2380:n
2376:S
2372:[
2366:E
2358:n
2354:E
2330:i
2326:X
2320:n
2315:1
2312:=
2309:i
2296:n
2292:S
2266:n
2262:V
2235:n
2231:E
2208:n
2204:S
2180:C
2172:i
2168:c
2164::
2161:i
2135:i
2131:a
2122:i
2118:b
2109:i
2105:c
2094:.
2077:i
2073:b
2064:i
2060:X
2051:i
2047:a
2033:i
2017:n
2013:X
2009:,
2003:,
1998:2
1994:X
1990:,
1985:1
1981:X
1929:t
1925:)
1922:2
1918:/
1912:2
1908:t
1901:(
1883:2
1874:)
1871:t
1864:|
1860:Z
1856:|
1852:(
1846:P
1826:)
1823:1
1820:,
1817:0
1814:(
1811:N
1805:Z
1771:t
1748:.
1741:a
1738:t
1734:e
1729:]
1724:X
1721:t
1717:e
1713:[
1707:E
1698:)
1695:a
1689:X
1686:(
1660:0
1654:t
1631:,
1624:a
1621:t
1617:e
1612:]
1607:X
1604:t
1600:e
1596:[
1590:E
1581:)
1578:a
1572:X
1569:(
1543:0
1537:t
1517:.
1513:]
1508:X
1505:t
1501:e
1497:[
1492:E
1486:)
1483:t
1480:(
1475:X
1471:M
1450:X
1355:3
1352:1
1339:)
1336:X
1333:(
1324:+
1319:2
1315:r
1309:)
1306:X
1303:(
1287:3
1284:4
1274:,
1271:)
1268:X
1265:(
1253:3
1250:5
1239:2
1235:r
1220:)
1217:X
1214:(
1205:+
1200:2
1196:r
1190:)
1187:X
1184:(
1168:9
1165:4
1156:{
1148:)
1145:r
1139:]
1136:X
1133:[
1130:E
1124:X
1121:(
1093:0
1087:r
1067:X
1036:.
1028:2
1020:9
1016:4
1008:)
995:|
985:X
981:|
977:(
950:,
941:=
935:3
932:8
913:σ
909:μ
905:X
875:2
871:x
867:=
864:)
861:x
858:(
834:|
830:]
827:X
824:[
818:E
812:X
808:|
784:X
760:]
757:X
754:[
725:,
718:2
714:a
710:1
702:)
699:]
696:X
693:[
681:a
674:|
670:]
667:X
664:[
658:E
652:X
648:|
644:(
615:,
608:2
604:a
599:]
596:X
593:[
578:)
575:a
568:|
564:]
561:X
558:[
552:E
546:X
542:|
538:(
512:0
506:a
482:]
477:2
473:)
469:]
466:X
463:[
457:E
451:X
448:(
445:[
439:E
436:=
433:]
430:X
427:[
395:]
392:X
389:[
383:E
359:X
325:.
319:)
316:a
313:(
305:)
302:)
299:X
296:(
290:(
284:E
275:)
272:)
269:a
266:(
257:)
254:X
251:(
245:(
239:=
236:)
233:a
227:X
224:(
175:.
170:a
166:)
163:X
160:(
154:E
145:)
142:a
136:X
133:(
107:0
101:a
77:X
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.