In probability theory, a Chernoff bound is an exponentially decreasing upper bound on the tail of a random variable based on its moment generating function...

sequence of random matrices. Analogous to the well-known Chernoff bound for sums of scalars, a bound on the following is sought for a given parameter t: Pr...

matrix theory, where he has established a family of results, collectively called matrix concentration inequalities, that includes the matrix Chernoff...

apply a Chernoff concentration bound for 1 k ∑ i Q i 2 {\textstyle {\frac {1}{k}}\sum _{i}Q_{i}^{2}} around 1. This requires upper-bounding the cumulant...

{\displaystyle K^{*}(q)={\frac {1}{2}}(q-k+k\ln {\frac {k}{q}})} , the standard Chernoff bound yields ln ⁡ P r ( X ≥ ( 1 + ϵ ) k ) ≤ − k 2 ( ϵ − ln ⁡ ( 1 + ϵ ) ) ln...

Ahmadi-Javid, which is an upper bound for the value at risk (VaR) and the conditional value at risk (CVaR), obtained from the Chernoff inequality. The EVaR can...

2 {\displaystyle \|X+Y\|_{vp}^{2}\leq (\|X\|_{vp}+\|Y\|_{vp})^{2}} (Chernoff bound) If X {\textstyle X} is subgaussian, then P r ( X ≥ t ) ≤ e − t 2 2...

the ratio of independent normal and gamma-difference random variables. Chernoff's distribution The exponentially modified Gaussian distribution, a convolution...

In probability theory, Markov's inequality gives an upper bound on the probability that a non-negative random variable is greater than or equal to some...

with Markov's inequality to bound the upper tail of a real random variable X. This statement is also called the Chernoff bound. Since x ↦ e x t {\displaystyle...

{\displaystyle \left\lceil \log {\frac {n}{\log(d/\lambda )}}\right\rceil .} The Chernoff bound states that, when sampling many independent samples from a random variable...

achieve any desired probability of correctness less than 1, using the Chernoff bound. The complexity class is unchanged by allowing error as high as 1/2...

fair Cheeger bound Chemometrics Chernoff bound – a special case of Chernoff's inequality Chernoff face Chernoff's distribution Chernoff's inequality Chi...

special cases of the Bernstein inequalities are also known as the Chernoff bound, Hoeffding's inequality and Azuma's inequality. The martingale case...

Uniform integrability Markov's inequality Chebyshev's inequality = Chernoff bound Chernoff's inequality Bernstein inequalities (probability theory) Hoeffding's...

{\mu }}-{\sqrt {\lambda }})^{2}}} The upper bound is proved using a standard Chernoff bound. The lower bound can be proved by noting that P ( X − Y ≥ 0...

X j {\displaystyle X_{j}} are independent random variables, by the Chernoff bound, for every a > 0 {\displaystyle a>0} : P r o b [ | c i | ≥ a ] ≤ 2 exp...

Burkholder–Davis–Gundy inequalities Cantelli's inequality Chebyshev's inequality Chernoff's inequality Chung–Erdős inequality Concentration inequality Cramér–Rao...

Genealogy Project Andrews, George E.; Babu, G. J.; Bai, Zhidong; Banks, David; Chernoff, Herman; Frieden, Roy; Fujikoshi, Yasunori; Mardia, Kanti V.; De Braganca...

1-e^{-2\gamma ^{2}k},} where γ = 1/2 - ε - δ. This follows by applying the Chernoff bound. With the advent of quantum computing, there has been a significant...

is the constant from the first theorem above, and hence 30.2211 works. Chernoff's inequality Edgeworth series List of inequalities List of mathematical...

Chebyshev in 1867. Chernoff bound, a bound on the tail distribution of sums of independent random variables, named for Herman Chernoff but due to Herman...

 132–140. doi:10.1145/28395.28410. ISBN 0897912217. Gillman, D. (1998). "A Chernoff Bound for Random Walks on Expander Graphs". SIAM Journal on Computing. 27...

272 (52): 32830–5. doi:10.1074/jbc.272.52.32830. PMID 9407060. Zhang B, Chernoff J, Zheng Y (April 1998). "Interaction of Rac1 with GTPase-activating proteins...

is greater than k, then reject. If we don't reject for any i, accept. Chernoff bounds then show that for a sufficiently large universal constant C, we...

on February 15, 2010. Retrieved April 10, 2010. Linsker R, Garwin RL, Chernoff H, Horowitz P, Ramsey NF (2005). "Synchronization of the acoustic evidence...

Mathematics Journal. 6 (4): 885–893. doi:10.1512/iumj.1957.6.56050. MR 0096113. Chernoff, Paul R. "Andy Gleason and Quantum Mechanics" (PDF). Notices of the AMS...

inequality / (F:R) Bernstein inequalities / (F:R) Bhatia–Davis inequality Chernoff bound / (F:B) Doob's martingale inequality / (FU:R) Dudley's theorem / Gau...

relative to the sizes of the sets, this difference is negligible. By standard Chernoff bounds for sampling without replacement, this estimator has expected error...

mid-1980s, the Airy function was found to be intimately connected to Chernoff's distribution. The Airy function also appears in the definition of Tracy–Widom...