$1+x\le \exp (x)$ for every real $x$, hence $(1-p{)}^m\le \exp (-mp)$

Depends on

• The real exponential function and the number $e$ by a power series
• The exponential is positive and satisfies $\exp(-x)=1/\exp(x)$
• The exponential function is smooth and $(\exp)'=\exp$
• The exponential function is strictly increasing
• The exponential addition formula $\exp(x+y)=\exp(x)\exp(y)$
• The mean value theorem, as the case $g(x) = x$ of Cauchy's: for $f$ continuous on $[a,b]$ with $a < b$ and differentiable on $(a,b)$ there is $c \in (a,b)$ with $f(b) - f(a) = f'(c)(b-a)$
• Integer powers $a^m$
• Monotonicity of $x \mapsto x^n$ and of $n \mapsto a^n$

Used by

• A sample-size consequence for compression schemes Corollary
• The symmetric Lovász Local Lemma under ep(d+1)≤1 Corollary
• A bounded continuous normalized function that is not of positive type Counterexample
• A Hopf--Lax solution with a forming corner from smooth data Example
• A parameter ledger for the high-girth, high-chromatic alteration proof Example
• A stable coupled model has an unstable explicit fast microstep Example
• Fixed-time error slopes for Euler, midpoint, and classical RK4 Example
• Heat and Poisson semigroups as Fourier multipliers Example
• Hilbert transform of the line Poisson kernel Example
• Too few sweeps lower the order from Gauss collocation Example
• A binomial-sum bound for compression sample sizes Lemma
• Finite geometric error bound from a one-step recurrence Lemma
• Gaussian decay gives an entire Fourier-Laplace transform and its growth bound Lemma
• Logarithmic L-r covering bound for VC classes of sets Lemma
• One-step stability of frozen-slow Euler with fast microsteps Lemma
• ℙ(α(G(n,p))≥ s)leC(n, s)(1-p)^C(s, 2)≤ nˢ exp(-pC(s, 2)) for s≤ n Lemma
• The improper integral of e^-x² over ℝ is finite and positive Lemma
• The sine integral under Countable Choice: uniform bounds and the value pi/2 Lemma
• Trace-norm continuity, growth and multiplicativity of the local determinant Lemma
• A conditional binomial error bound for Parareal Theorem
• A k-uniform hypergraph is 2-colourable when every edge meets at most d other edges and e(d+1)≤2ᵏ⁻¹ Theorem
• A square-root global error bound for projected Euler with certified projection tolerances Theorem
• Adaptive conditional failure budgets compose by a union bound Theorem
• An n-vertex graph of minimum degree δ>1 has a dominating set of size at most n(log(δ+1)+1)/(δ+1) Theorem
• Bernstein inequality for bounded independent sums Theorem
• Correctness and cost of the linear-combination sampler Theorem
• Euler–Maruyama uniform moments and interpolation increments Theorem
• Every finite family with the Erdős–Hajnal property is viral Theorem
• Exp3 expected regret under bandit feedback Theorem
• Expected generalization of nonconvex stochastic gradient training Theorem
• Finite-class realizable PAC bound Theorem
• Finite-state killed projection has an exact lost-mass certificate Theorem
• Fixed-matrix global orders and certified-action error propagation Theorem
• For all positive k,ℓ, some finite graph has girth greater than ℓ and chromatic number greater than k Theorem
• Forward Euler has first-order global error and preserves a margin tube for the regularized SPH ODE Theorem
• Hedge's second-order and static-regret bounds Theorem
• If k≥1 and n≥3k² 2ᵏ, an n-vertex tournament with property Sₖ exists Theorem
• Realizable sample complexity for finite-VC classes Theorem
• Rosenbrock–Euler has a first-order global error bound on a common tube Theorem
• Sauer–Shelah growth bound for indexed samples Theorem

…and 2 more results.

Dependency tree · two levels

46 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

• J. Matousek and J. Vondrak, The Probabilistic Method, Chapter 4 (standard reference, not scraped)