Markov's inequality: if $X\ge 0$ and $a>0$, then $\mathbb{P}(X\ge a)\le \mathbb{E}[X]/a$. Pointwise,Taking expected values, using their monotonicity and the identity $\mathbb{E}[1_E]=\mathbb{P}(E)$, gives $\mathbb{E}[X]\ge a\mathbb{P}(X\ge a)$. Division by the positive threshold proves the inequality. If the expectation is infinite, the extended-valued bound remains true but uninformative.

Differentiate the probability generating function equation:At $s=1$, $G_N(1)=1$, givingThe derivative is finite because $p<1/2$ and the explicit square root has no singularity at $s=1$. Alternatively, the expected population in generation $t$ is $(2p{)}^t$, so the expected number of splits in that generation is $p(2p{)}^t$. Summing this nonnegative geometric series gives the same answer without initially assuming a finite expected value.

If the initial individual has no offspring, $N=0$. If it splits, count that one event and the splitting events in its two independent descendant trees. Thuswhere $N_1,N_2$ are independent copies of $N$. Taking the probability generating function givesFor $0<s\le 1$, the quadratic equation has two algebraic branches. A probability generating function must remain finite at $s=0$, where it equals $\mathbb{P}(N=0)=q$, so the admissible branch isThe rationalized formula is also defined directly at zero. At $s=1$, $\sqrt{1-4pq}=q-p$, so $G_N(1)=1$, consistent with almost-sure finiteness. Extinction occurs after a finite number of generations almost surely, and each generation is finite, which justifies that finiteness claim for the number of splitting events in a binary branching process.

This is a Galton-Watson process with offspring count $0$ with probability $q=1-p$ and $2$ with probability $p$. The descendants of distinct initial individuals evolve independently, sofor every finite initial size $i$. Conditioning on the first individual's outcome and applying the law of total probability givesThe equation factors asIts roots are $1$ and $q/p$. Since $p<1/2$, the second root exceeds one and cannot be a probability. Therefore ${\alpha }_1=1$ and ${\alpha }_i=1$ for every finite initial size. The population reaches the absorbing state zero almost surely; no choice between two admissible fixed-point probabilities remains in this subcritical case.

Let $D$ denote the selected die. Bayes' theorem givesOnly the first roll is conditioned on here; the second outcome has not been observed.

The two outcomes are not independent. Conditional on the selected die, the rolls are independent, but sharing the unknown die creates statistical dependence. Each nonfavored face has probability $(1-1/2)/5=1/10$.

The unconditional marginal distribution assigns the following probability to a $1$ on either roll:However, by the law of total probability,Thus the joint probability does not factor into the two marginals. Conditional independence given a shared latent choice does not imply unconditional independence.

Let $I_B$ be the indicator that black bead $B$ belongs to the white bead's connected component. The number of such black beads is ${\sum }_B{I}_B$. By linearity of expectation, no independence between these indicators is needed.

For $n=7$, the six oriented distances $1,\dots ,6$ give respective probabilitiesTheir sum is $2$, the expected number of black beads in the white component. As a check, summing the formula from (i) and using ${\sum }_{k=1}^{n-1}\left(\genfrac{}{}{0ex}{}{k}{3}\right)=\left(\genfrac{}{}{0ex}{}{n}{4}\right)$ gives the general value $2\left(\genfrac{}{}{0ex}{}{n}{4}\right)/\left(\genfrac{}{}{0ex}{}{n}{3}\right)=(n-3)/2$, again equal to $2$ when $n=7$.

View the necklace as a cycle graph. Between the white bead and $B$ there are two edge-disjoint paths, containing $k$ and $n-k$ links. The beads remain connected if and only if at least one of these paths is uncut.

There are $\left(\genfrac{}{}{0ex}{}{n}{3}\right)$ equally likely cut sets. Keeping the $k$-link path uncut requires all three cuts to be among its $n-k$ complementary links, giving $\left(\genfrac{}{}{0ex}{}{n-k}{3}\right)$ choices. Keeping the other path uncut gives $\left(\genfrac{}{}{0ex}{}{k}{3}\right)$ choices. These two events are disjoint because three links are cut and they cannot all lie in both complementary paths. ThereforeUse $\left(\genfrac{}{}{0ex}{}{a}{3}\right)=0$ for $0\le a<3$. The answer is unchanged by exchanging $k$ and $n-k$, so either orientation around the necklace gives the same value. This is the connectivity calculation for random cuts of a cycle.

For $W=\max \{U,V\}$ and $0\le w\le 1$, independence gives the cumulative distribution functionThe cumulative distribution function is zero below $0$ and one above $1$. Differentiating on the interior givesup to irrelevant endpoint values. There are no endpoint atoms. This maximum is an order statistic.

Split the unit square into $v\le u$ and $v>u$. The maximum is $u$ on the first triangle and $v$ on the second, soThe shared boundary has zero probability, so it is not counted twice in this joint density calculation.

By independence, the joint probability density is the product of the two uniform distribution densities:Changing its values on the boundary does not affect any probability or expected value.

For $q>1$, decreasing the second parameter by one gives another valid beta distribution density andNormalization therefore givesThe restriction $q>1$ is essential for this finite expected value; when $q=1$, the singularity near $1$ instead makes the expectation infinite.

Multiplying the beta distribution density by $x$ gives a constant multiple of the normalized density with parameters $(p+1,q)$:Integrating and using the fact that the latter probability density function integrates to one givesThis is a normalization-ratio argument, requiring no explicit integration of the polynomial density.

At $d=10^6$, gradient descent remains a plausible large-scale choice; dense Newton method and full-memory BFGS are generally impractical. A dense $d\times d$ double-precision matrix alone contains $10^{12}$ entries, about $8$ TB. Dense factorization also has order $10^{18}$ arithmetic work. Full BFGS avoids factorization but retains quadratic storage and update work, so it does not solve that scaling problem.

Gradient descent uses linear working storage in $d$, though the cost of reading the data and evaluating the gradient is still $O(nd)$ for dense $A$. Sparsity or streaming can be important. Limited-memory BFGS, a distinct limited-memory variant, stores only a fixed number $m$ of recent update pairs and uses $O(md)$ storage and update work, making it a realistic alternative to full BFGS.^[ref]

The available Hessian matrix factorization also permits a matrix-free Hessian-vector product:It costs $O(nd)$ for dense data without forming $H$. A suitable iterative, safeguarded Newton method can exploit this structure, so the conclusion rules out the dense implementation rather than every possible second-order algorithm.

These methods seek a local solution and require convergence checks appropriate to nonconvex optimization. The formula does not even ensure a finite minimizer exists: with one positive coefficient and nonzero $\mathbf{a}$, the positive exponential loss approaches zero along an unbounded direction without attaining it. Dimension alone cannot supply a convergence guarantee.

At $d=1000$, gradient descent and full BFGS are practical candidates; a dense Newton method can also be feasible, but its extra work and indefinite curvature need attention. The number of examples $n$, data sparsity and conditioning still matter.

For dense $A$, a gradient evaluation costs $O(nd)$ arithmetic, with $O(d)$ working storage beyond the data and accumulation buffers. Gradient descent is inexpensive per iteration and, with an appropriate line search, follows a descent direction, but poor conditioning can make it slow.

Forming the Hessian matrix explicitly costs $O(n{d}^2)$ arithmetic, and a dense Newton method solve costs $O(d^3)$. A $1000$-square double-precision matrix uses about $8$ MB, so storage alone is manageable, but repeated factorization may be expensive. Because the Hessian matrix can be indefinite or singular, an unmodified Newton step need not decrease the loss; a modified Hessian, damping or a trust region is appropriate.

Full BFGS uses gradients and an $O(d^2)$ curvature approximation, avoiding explicit second derivatives. Its rank-two updates and direction calculation cost $O(d^2)$ per step and require roughly the same matrix storage. A positive-definite initial approximation with safeguarded curvature updates and a suitable line search preserves descent directions. For this scale it is often a good compromise, without guaranteeing a global minimum.^[ref]

Differentiating the gradient term by term gives the Hessian matrixTake row $i$ of $A$ to be ${\mathbf{a}}_i^{\mathsf{T}}$. ThenIndeed, entry $(j,k)$ of this product is ${\sum }_i{\Delta }_{ii}{a}_{ij}{a}_{ik}$, exactly the entry of the displayed sum of outer products. Explicitly,These coefficients may have either sign, so a positive-definite Hessian matrix cannot be assumed. This is an instance of the Hessian of a sum of functions of linear forms.

Use a column gradient. By the multivariable chain rule,The scalar coefficients multiply the constant vectors ${\mathbf{a}}_i$. In particular $f^{\prime }(t)=-t{e}^{-t^2/2}$, although explicit differentiation of $f$ is not required.

About five steps are certified by the uniform worst-case estimate; the actual iteration reaches double-precision accuracy in about four. Put $K=15/14$. The initial enclosure gives $e_0=|x_0-r|<1/5$, and repeated squaring yieldsFor $k=4$ this is about $1.84\times 10^{-11}$, while for $k=5$ it is below $4\times 10^{-22}$. Thus five ideal-arithmetic steps push this bound well below the approximately $10^{-16}$ relative resolution of double-precision floating-point format.

The bound is conservative. Factoring $f(x)=(x^2+1)(x^4-6x^2+6)$ identifiesHigh-precision evaluation of the actual successive errors gives approximately $7.40\times 10^{-2}$, $3.56\times 10^{-3}$, $9.91\times 10^{-6}$, $7.73\times 10^{-11}$ and $4.70\times 10^{-21}$. Thus the fourth step would already exceed double-precision accuracy in exact arithmetic. In floating-point evaluation, cancellation in the residual and other roundoff errors prevent the subsequent theoretical digits from being realized.

On $I=[1,7/5]$, $f^{\prime }<0$ and $f^{\prime \prime }<0$, since $x^2<2$. Hence $|f^{\prime }|$ increases and has minimum $|f^{\prime }(1)|=14$. Alsowith equality at $x=1$. Therefore

There is a unique root $r$ in $I$: $f(1)=2>0$, $f(7/5)=-5.678464<0$, and the function is strictly decreasing. Moreover $f(6/5)=-1.382016<0$, so $r<6/5=x_0$.

It remains to justify that the iteration stays where the error estimate applies. Because $f$ is a concave function, its graph lies below each tangent line. At any $x\in [r,6/5]$, the tangent has nonpositive value $f(x)$ at $x$, negative slope, and nonnegative value at $r$. Its zero $N(x)=x-f(x)/f^{\prime }(x)$ therefore satisfiesBy mathematical induction, the Newton root-finding iteration stays in $[r,6/5]$ and decreases to some limit $L\ge r$. Continuity in $x_{k+1}-x_k=-f(x_k)/f^{\prime }(x_k)$ implies $f(L)=0$, so uniqueness gives $L=r$.

Now the supplied error bound applies at every step:This proves at least quadratic convergence, with an invariant interval and a nonvanishing derivative explicitly established.

The Newton root-finding iteration isIt is defined when $x_k\notin \{0,\pm \sqrt{10/3}\}$. Finding an exact zero of a function is a stopping condition, rather than a reason to continue dividing.