Insert the Poisson distribution probability generating function into the preceding bound:For fixed , differentiate the exponent with respect to . Its derivative is , and its second derivative is , so its unique minimum occurs at . At that value,ConsequentlyThis Chernoff bound remains valid for noninteger positive thresholds ; the event is then the same as exceeding or equalling its integer ceiling.
Because , the function is increasing and nonnegative. Thus . Applying Markov's inequality to the nonnegative random variable , whose expected value is finite by assumption, yieldsUnder the usual probability generating function convention takes nonnegative integer values. The argument itself works for any real random variable if is understood as the finite expected value .
Conditioning on has positive probability exactly when for an integer . This is the same event as . The addition of independent Poisson random variables gives a Poisson distribution with parameter for the sum. Therefore, for ,Thus . The case is a constant zero random variable. For even, nonpositive, or noninteger , the conditioning event has zero probability, so an event-conditional probability distribution is not specified by the quotient formula. This is a two-component case of Poisson-multinomial conditioning.
For , independence givesThe initial factor accounts for the shift by one; substituting accounts for doubling the random variable. Its support consists of positive odd integers.
By the definition of a probability generating function and the power series for the exponential function,The series is absolutely convergent for every finite real ; in particular the expression is finite for all , as needed for the later tail estimate.
The independent random variables have a product joint probability mass function. For integers ,It is zero for all other pairs. The factors are the respective Poisson distribution masses, with the product justified by independence.
A general-purpose high-dimensional choice is Monte Carlo integration. Draw independent vectors uniformly from the unit cube and evaluate . The cube has volume , so its integral is the expected value of . The iterative estimator isThe integrand is continuous on a compact set, hence bounded with finite variance. The strong law of large numbers gives almost sure convergence, and the square root of the mean squared error is exactly , where . Thus the standard stochastic accuracy rate is ; the dimension affects the variance and evaluation cost, not this exponent.
There is also an important structure-specific improvement here: is a separable integrand. The Fubini theorem reduces the requested value exactly toOne can therefore replace high-dimensional sampling by one-dimensional composite Simpson's rule calculations. For each factor use even , , andthen iterate and form the sum of the products. These smooth factors give deterministic discretization error for fixed centres. Thus Monte Carlo integration is a valid generic answer, while exploiting separability is the more efficient specialized alternative; a large dimension alone does not force a tensor-product grid.
Let be the weighted average on the right, and define and as in part (i). Their explicit gradient identity isTherefore the displayed equation is exactly the stationary point equation for the strongly convex . It has one solution, which is the unique minimizer from part (i). Reuse the BFGS iteration, withThe gradient is explicit, the weights can again be scaled by their largest exponent, and the usual full-memory BFGS assumptions give local superlinear convergence.
Simply setting is not automatically a convergent fixed-point iteration. Differentiating the normalized weights giveswhose operator norm need not be below . For example, in one dimension with centres , and : the desired fixed point is locally repelling for that naive iteration. If exact second derivatives are affordable, multivariable Newton iteration on is another valid choice, with Jacobian matrix as given above and local quadratic convergence.
Here a dense -by- matrix has entries, about GB even with eight-byte storage per entry. Use limited-memory BFGS on the negative of the objective, or equivalently its positive-definite approximate-metric form of gradient ascent. It stores only a fixed small number of vector pairs, costing memory rather than .
Let and put . Direct use of the chain rule givesIf denotes the positive-definite inverse-Hessian matrix approximation for , the iteration iswith a line search increasing and the usual safeguarded limited-memory updates. No exact Hessian matrix is required. With fixed memory and the usual bounded-metric and line search hypotheses, expect local linear convergence near a nondegenerate strict maximum; fixed-memory limited-memory BFGS does not generally inherit the superlinear theorem for full-memory BFGS.
Unlike the preceding objective, is not generally a concave function. Thus this is a method for finding a local maximum; comparison of different converged candidates or a global search is needed to certify a global maximum for arbitrary centres. The symbolic problem supplies no assumption that would justify an unconditional global-convergence claim.[ref]
Quasi-Newton Methods by NEOS Guide. Final paragraphs: storing only recent secant vectors, linear-in-dimension memory, and the L-BFGS implementation
Past exam of the year 1 of the computer science course of the University of Oxford 2021 Discrete mathematics, continuous mathematics, and probability 6 b i Solution Created 2026-10-25 Updated 2026-10-31
A practical choice is a BFGS method, using exact gradients and a line search. At dimension , its -by- inverse-Hessian matrix approximation is small, whereas forming a million rank-one contributions to the exact Hessian matrix is expensive. If , the explicit derivatives areThe positive-definite Hessian matrix and coercivity show that the objective has one global minimizer.
For numerical stability one can minimize instead, which has exactly the same minimizer. Put , , and . Then the logarithmic gradient of an exponential squared-distance sum givesEvaluate the weights as to avoid floating-point overflow. A quasi-Newton method step iswhere is the positive-definite inverse-Hessian matrix approximation updated by BFGS, and is chosen by a line search, for example one satisfying the Wolfe conditions. Under the standard smoothness and nondegeneracy assumptions at this strongly convex minimizer, full-memory BFGS has local superlinear convergence. An exact Newton's method in optimization would have local quadratic convergence, but pays for those much more expensive exact second derivatives.[ref]
Quasi-Newton Methods by NEOS Guide. Opening construction and BFGS update: approximate Hessians from gradients; dense update cost of order d squared
Differentiate the column gradient . The Jacobian matrix product rule gives one term from differentiating the scalar exponential function and one from differentiating , whose Jacobian matrix is the identity matrix:In particular, for any nonzero vector ,Thus the Hessian matrix is positive definite everywhere. This calculation proves strict convexity and supplies the derivatives needed for sums of these terms.
Write . The squared Euclidean norm is , whose gradient is . The chain rule for the exponential function therefore gives the column gradientThe row derivative, if that convention is used for , is its transpose.
Check each partial order axiom. For every , and , so is a reflexive relation. If both and , the first coordinates satisfy and the second coordinates satisfy . Therefore and , which proves is an antisymmetric relation.
Finally, if and , then and . Hence , making a transitive relation. All three axioms hold, so is a partial order. It is a product order, with the usual order on the first coordinate and the reversed order on the second.
Take and . Their first coordinates are equal, so both and hold, although . Thus is not an antisymmetric relation, and hence it is not a partial order. The failure arises because its comparisons ignore the second coordinate entirely.
The contrapositive is that an integer perfect square has residue or modulo . Let for an integer . If is an even number, then . If is an odd number, then . These exhaust the possible parities of an integer. Thus a residue of or excludes being a perfect square, as required by the contrapositive.
Suppose, for a proof by contradiction, that an integer is both an even number and an odd number. Then and for some integers . Subtracting yields . The left side is an integer, while is not. This contradiction proves that no integer is both even and odd.
For , both sides are . Assuming the formula through , adding the next term givesThe last expression is the required formula at , completing mathematical induction. The partial fraction decompositionprovides a second explanation: this is a telescoping sum.
For the base case , the product is . Assume the identity holds for some . Multiplying by the next factor givesThis is the desired expression with replaced by , so mathematical induction proves the identity for every . The factorization also explains the cancellation as a telescoping product.
Take . These are four distinct positive integers and . Their products are and , whose difference is , so . Here the correct reduced modulus is , and indeed . The example illustrates why cancelling a noninvertible factor may change the modulus in modular arithmetic.
Let , , and . The preceding part gives . The integer congruence on the left is equivalent toBy Euclid's lemma, coprimality of and makes this equivalent to . The reverse implication is also immediate by multiplying a divisibility relation by . ThereforeThis is cancellation of a common factor in a congruence. The printed equality sign in the right-hand expression is interpreted as equality of residue classes, hence the displayed integer congruence. Ordinary equality of the integers would be false: the following example has .
There are unlisted articles, also show them or only show them.