For one proposal, $P(Y=x,\text{accept})=q(x)\tilde{p}(x)/(M\tilde{q}(x))=\tilde{p}(x)/(M{Z}_q)$. Summing gives total acceptance probability $a=Z_p/(M{Z}_q)>0$. Conditioning on acceptance therefore gives $P(Y=x\mid \text{accept})=\tilde{p}(x)/Z_p=p(x)$.

The first accepted result has this law too: the probability of $k-1$ failures followed by acceptance at $x$ is $(1-a{)}^{k-1}\tilde{p}(x)/(M{Z}_q)$. Sum the geometric series over $k\ge 1$ to obtain $\boxed{P(X=x)=p(x)}$. Positive acceptance probability also proves almost-sure termination.

Let $Z_p={\sum }_x\tilde{p}(x)$ and $Z_q={\sum }_x\tilde{q}(x)$, both finite and positive as required for normalization. A sufficient envelope condition is $\boxed{M\ge \underset{x\in \Omega }{\sup }\tilde{p}(x)/\tilde{q}(x)}$ with finite $M>0$. Use independent proposals and independent uniforms on each trial. This guarantees an acceptance probability in $[0,1]$ for every state. Choose the smallest certified upper bound on that ratio, since increasing $M$ decreases the overall acceptance rate. The ratio must be bounded for this particular proposal to admit such an envelope.

For an $m\times n$ rectangle, let $S_j$ be the symbols absent from column $j$. Each has size $n-m$. Across all columns, each symbol is absent exactly $n-m$ times, because it appears once in each existing row. For any set $J$ of columns, count incidences between those columns and their missing symbols. There are $|J|(n-m)$ incidences, while each distinct symbol in the union contributes at most $n-m$. Therefore $|{\bigcup }_{j\in J}{S}_j|\ge |J|$.

Hall's theorem supplies distinct representatives, one per column, forming an additional row with all $n$ symbols. This extends the rectangle without any column repetition. Repeat with $m+1$ rows, then successively until there are $n$ rows. Hence every finite latin rectangle extends to a Latin square by adding the required rows.

The missing sets in the five columns are $\{4,5\}$, $\{1,3\}$, $\{4,5\}$, $\{2,3\}$ and $\{1,2\}$. One choice of distinct representatives is $(4,1,5,3,2)$, giving the fourth row. Each column then has exactly one missing number, producing the fifth row $(5,3,4,2,1)$. A completed square isEvery row and column contains each number from one to five once. The construction explicitly chooses from the missing sets, so it preserves all entries of the given rectangle.

Form a bipartite graph with left labels $1,\dots ,m$, right set $E$, and an edge $i-e$ exactly when $e\in S_i$. A matching covering all left labels is precisely a choice of distinct representatives. Its neighborhood condition isThus this is necessary and sufficient. The underlying set $E$ may be infinite; only the number of sets to be represented is finite.

A complete matching from $V_1$ to $V_2$ is a set of edges with no shared endpoints that contains an edge incident to every vertex of $V_1$. The theorem in (i) gives the necessary and sufficient conditionThe intended setting is a finite left vertex set; no condition that every vertex of $V_2$ be used is imposed.

Use the equivalent bipartite formulation: the left set has $m$ vertices and a matching must cover it. Necessity is immediate, since distinct matched partners for any left subset must all lie in its neighborhood.

For sufficiency, induct on $m$. The cases zero and one are immediate from the neighborhood condition. If a nonempty proper left subset $A$ satisfies $|N(A)|=|A|$, induction matches $A$ into $N(A)$. For the remaining left vertices and remaining right vertices, any subset $B$ has at least $|B|$ available neighbors: applying Hall's inequality to $A\cup B$ and removing the $|A|$ possible neighbors in $N(A)$ proves this. Induction supplies the second matching, and the two combine.

If no nonempty proper subset has equality, all such subsets have at least one extra neighbor. Choose any left vertex and one of its neighbors and match them. After deleting the pair, each nonempty subset of the remaining left side originally was proper and had at least $|B|+1$ neighbors; losing the chosen right vertex leaves at least $|B|$. Induction completes the matching. Thusis sufficient as well as necessary. If the right set is infinite, any subset with infinitely many neighbors automatically meets the finite inequalities, and the same finite-left induction applies.

Proceed column by column. At stage $j=1,\dots ,n-2$, consider the entries below the diagonal in column $j$, indexed $j+1,\dots ,n$. If this tail is nonzero, part (c) provides a Householder matrix sending it to a multiple of its first coordinate vector. Embed this matrix as an orthogonal matrix acting identically on coordinates $1,\dots ,j$, and apply the similarity transformation $A\mapsto Q_j^{T}A{Q}_j$. The tail's entries below row $j+1$ become zero. Symmetry is preserved, so the corresponding entries in row $j$ vanish too. If the tail is already zero, use the identity transformation.

Earlier reduced columns remain unchanged in their required zero positions: all their entries in the newly mixed tail coordinates were already zero, and the first $j$ coordinates are fixed. Thus each stage preserves the previous zeros while creating the next ones. After $n-2$ stages, all entries at distance greater than one from the diagonal vanish. With the product $Q=Q_1\cdots Q_{n-2}$ one has $Q^{T}Q=I$ andThis constructive reduction uses only reflections on successive trailing subspaces.

Choose $c=-{\mathrm{sgn}}_{+}(x_1)\Vert x\Vert$, with ${\mathrm{sgn}}_{+}(0)=1$, and put $v=x-c{e}_1$. The opposite sign choice guarantees $v\ne 0$, even if $x$ is already parallel to $e_1$. Since $c^2=\Vert x{\Vert }^2$,Consequently $H_{v}x=x-2v(v^{T}x)/(v^{T}v)=x-v$, yieldingThe sign choice also avoids cancellation in constructing $v$ numerically.

If $x\in S_v$, then $v^{T}x=0$ and $Px=0$, so $\boxed{H_{v}x=x}$. For arbitrary $x$, $v^{T}P=v^T$, givingThus the Householder map fixes the hyperplane orthogonal to $v$ and reverses the component in its normal direction: it is a reflection, not merely an arbitrary orthogonal map.

Set $P=v{v}^T/(v^{T}v)$. Since $v\ne 0$, it is well defined, symmetric and idempotent: $P^T=P$, $P^2=P$. Therefore $H_{v,\alpha }=I-\alpha P$ is symmetric, andBecause $P\ne 0$, this equals $I$ exactly when $\alpha (\alpha -2)=0$. Hence $\boxed{H_{v,\alpha }\text{ orthogonal}⟺\alpha \in \{0,2\}}$.

Every derivative of order $n+1$ of $\sin 2x$ has magnitude at most $2^{n+1}$. Pair the symmetric nodes $a=i/n$ and $1-a$. For $0\le x,a\le 1$,If there is an unpaired middle node, its factor has magnitude at most $1/2$. Thus the full nodal product is at most $2^{-(n+1)}$, giving the stronger bound $\Vert f-p_n{\Vert }_{\infty }\le 1/(n+1)!$. In particular this implies the requestedThe bound tends to zero by factorial growth, so $\boxed{p_n\to f\text{ uniformly on }[0,1]}$. This conclusion uses smoothness of this particular function and does not assert uniform convergence of equispaced interpolation for arbitrary continuous data.

If $x$ is a node, both sides vanish and any $\xi \in (a,b)$ works. Otherwise put $\omega (t)={\prod }_i(t-x_i)$ and $C=(f(x)-p_n(x))/\omega (x)$. The function $H(t)=f(t)-p_n(t)-C\omega (t)$ has $n+2$ distinct zeros, at the nodes and at $x$. Repeated application of Rolle's theorem gives an interior point $\xi$ where $H^{(n+1)}(\xi )=0$. As $p_n^{(n+1)}=0$ and ${\omega }^{(n+1)}=(n+1)!$, this gives $C=f^{(n+1)}(\xi )/(n+1)!$. ThereforeThe distinct nodes and $n\ge 1$ ensure $a<b$, so the interior point is meaningful.

Multiplying the Vandermonde matrix $A_n$ by a coefficient vector $(c_0,\dots ,c_n{)}^T$ evaluates the polynomial ${\sum }_j{c}_j{x}^j$ at all nodes. If the result is zero, part (a)'s uniqueness for the zero interpolation data forces every coefficient to be zero. Thus the square matrix has trivial kernel and is invertible. Equivalently the interpolation map is a linear bijection between two spaces of dimension $n+1$.

Interpolation means $p_n(x_i)=f(x_i)$ for every node. Define the cardinal polynomials ${\ell }_i(x)={\prod }_{j\ne i}(x-x_j)/(x_i-x_j)$, which are well defined because the nodes are distinct. They have degree $n$ and satisfy ${\ell }_i(x_j)={\delta }_{ij}$. Hencebelongs to ${\Pi }_n$ and interpolates. If two polynomials in ${\Pi }_n$ interpolate the same data, their difference has $n+1$ distinct zeros but degree at most $n$, so it is zero. This proves uniqueness. The phrase “of degree $n$” denotes membership in ${\Pi }_n$ here: the actual degree may be smaller, for example for constant data.

With one parameter fitted to the grouped cells, the reference degrees of freedom are $10-1-1=8$. The table already gives a deviance of $8.29$ at $0.93$, so the minimized deviance is no larger than that; its direct grouped minimum is about $7.76$. Either is below the supplied critical value $15.51$. Therefore do not reject the fitted grouped log-series model at level five percent. The estimate being profiled in this test is the grouped-likelihood estimate described above, not the different full-data score estimate.

For the specified parameter there is no fitted parameter, so the null reference has $10-1=9$ degrees of freedom. The given deviance is $15.59$, below the supplied five-percent critical value $16.92$. Hence do not reject the fixed log-series model at level five percent. The parameter is fixed in this test, so subtracting an additional degree of freedom would be inappropriate.

Put $D^{\ast }=D-A$. By (i), $D^{\ast }X=0$. Thus $D^{\ast }{A}^T=D^{\ast }X(X^{T}X{)}^{-1}=0$, and its transpose vanishes too. Expanding $D{D}^T=(D^{\ast }+A)(D^{\ast }+A{)}^T$ yieldsThe covariance difference is positive semidefinite. In particular its $i$th diagonal entry is ${\sigma }^2{\sum }_j(D_{ij}^{\ast }{)}^2\ge 0$, proving the requested componentwise variance inequalities. Prefer $\boxed{{\hat{\theta }}_1}$ within the class of linear unbiased estimators, since it has the least variance and the same expectation. A tie is possible if the first row of $D^{\ast }$ is zero. This is the Gauss-Markov theorem conclusion; no normal-distribution assumption on the errors is required.

Unbiasedness as an estimator of the parameter means $DX\theta =\theta$ for every $\theta \in {\mathbb{R}}^p$, rather than just one particular value. Thus $(DX-I_p)\theta =0$ for every vector, forcing $\boxed{DX=I_p}$. Conversely that identity plainly suffices for unbiasedness.