Thursday 27 August 2026

Part (a): the pigeonhole

Work with cumulative counts. Set $a_0=0$ and $a_i=t_1+\cdots +t_i$. Because every $t_i\ge 1$, the sequence is strictly increasing:

$$0=a_0<a_1<a_2<\cdots <a_{30}\le 44.$$

The number of trades on days $i+1,\dots ,j$ is exactly $a_j-a_i$, so we must produce a pair with $a_j-a_i=15$.

Consider the two families of integers

$$a_1,a_2,\dots ,a_{30}\text{and}{a}_1+15,a_2+15,\dots ,a_{30}+15.$$

That is $60$ integers in total. Each lies in $\{1,2,\dots ,59\}$: the first family because $1\le a_i\le 44$, the second because $16\le a_i+15\le 59$. Sixty integers into $59$ boxes: by the pigeonhole principle two of them coincide.

The step a candidate skips is checking which two collide. The $a_i$ are pairwise distinct, and the $a_i+15$ are pairwise distinct, so no collision happens inside a single family. The equal pair must therefore be cross-family:

$$a_j=a_i+15\text{for some }i<j,$$

and the days $i+1,\dots ,j$ total exactly 15 trades. $∎$

Part (b): the sharp threshold

Avoiding a 15-block means choosing $0=a_0<a_1<\cdots <a_{30}=N$ (where $N$ is the total) so that no two of these 31 values differ by exactly 15. Equivalently, we want a subset $S\subseteq \{0,1,\dots ,N\}$ with $|S|=31$, containing $0$ and $N$, and free of any pair at distance 15.

Partition $\{0,1,\dots ,N\}$ by residue mod 15. Within one residue class the elements form a chain $r,r+15,r+30,\dots$, and "distance exactly 15" is precisely adjacency along this chain. A distance-15-free selection is thus an independent set in a path, whose maximum size for a path on $L$ vertices is $\lceil L/2\rceil$. Hence the largest distance-15-free subset of $\{0,\dots ,N\}$ has size ${\sum }_r\lceil L_r/2\rceil$.

Write $N+1=15q+s$ with $0\le s<15$; then $s$ residue classes have length $q+1$ and the other $15-s$ have length $q$, giving maximum free size

$$s\lceil \frac{q+1}{2}\rceil +(15-s)\lceil \frac{q}{2}\rceil .$$

For $N=59$ we have $N+1=60=15·4$, so $q=4$, $s=0$, and the maximum free size is $15·2=30<31$. The same computation gives $\le 30$ for every $N\le 59$, so a 15-block is forced for all totals up to 59.

For $N=60$ we have $N+1=61=15·4+1$, so $q=4$, $s=1$, and the maximum free size is

$$1·\lceil \frac{5}{2}\rceil +14·\lceil \frac{4}{2}\rceil =3+28=31.$$

So $N=60$ is exactly the first total that permits a counterexample. An explicit one: take the cumulative set

$$\{0,1,\dots ,14\}\cup \{30,31,\dots ,44\}\cup \{60\},$$

which has $15+15+1=31$ elements, none differing by 15. Its consecutive differences are the daily trade counts:

$$\underset{14}{\underbrace{1,1,\dots ,1}},16,\underset{14}{\underbrace{1,1,\dots ,1}},16,$$

i.e. 14 days of one trade, one day of 16, 14 more days of one trade, one final day of 16 — that is $30$ days and $60$ trades. Any window sum equals a difference of two cumulative values, and no two differ by 15, so no block totals 15.

Answer. (a) Such a 15-trade block must exist. (b) The smallest total permitting no 15-block is $\boxed{60}$.

Closing note

The crude argument in (a) only certifies the conclusion up to a total of $2·30-15-1=44$, and it is tempting to declare $44$ the threshold and hunt for a counterexample at $45$. There is none: the residue/independent-set count shows the true guarantee extends all the way to $59$. The pigeonhole bound is correct but not tight — a useful reminder that surviving the pigeon count is sufficient, not necessary.

1. The score

For a single observation, ${\ell }_i=\frac{1}{\varphi }(y_i{\theta }_i-b({\theta }_i))+c(y_i,\varphi )$, so $$\frac{\partial {\ell }_i}{\partial {\beta }_j}=\frac{1}{\varphi }(y_i-b^{\prime }({\theta }_i))\frac{\partial {\theta }_i}{\partial {\beta }_j}=\frac{1}{\varphi }(y_i-{\mu }_i)\frac{\partial {\theta }_i}{\partial {\beta }_j}.$$ Chain the dependence ${\theta }_i\mapsto {\mu }_i\mapsto {\eta }_i\mapsto \beta$. Since ${\displaystyle \frac{d{\mu }_i}{d{\theta }_i}}=b^{″}({\theta }_i)=V({\mu }_i)$, we have ${\displaystyle \frac{d{\theta }_i}{d{\mu }_i}}={\displaystyle \frac{1}{V({\mu }_i)}}$, and ${\displaystyle \frac{\partial {\eta }_i}{\partial {\beta }_j}}=x_{ij}$. Hence $$\frac{\partial {\theta }_i}{\partial {\beta }_j}=\frac{1}{V({\mu }_i)}\frac{d{\mu }_i}{d{\eta }_i}{x}_{ij}.$$ Summing over $i$ gives $$U(\beta )=\frac{1}{\varphi }\sum _i\frac{y_i-{\mu }_i}{V({\mu }_i)}\frac{d{\mu }_i}{d{\eta }_i}{x}_i.$$ This is the standard GLM estimating equation: a covariate-weighted sum of residuals, with the weight $\frac{1}{V({\mu }_i)}\frac{d{\mu }_i}{d{\eta }_i}$ absorbing both the variance and the link.

2. Canonical link: the Hessian loses its randomness

With ${\theta }_i={\eta }_i=x_i^{\top }\beta$, $$\ell (\beta )=\frac{1}{\varphi }\sum _i(y_i{x}_i^{\top }\beta -b(x_i^{\top }\beta ))+\text{const}.$$ Differentiate once: $U(\beta )=\frac{1}{\varphi }{\sum }_i(y_i-b^{\prime }({\eta }_i))x_i=\frac{1}{\varphi }{\sum }_i(y_i-{\mu }_i)x_i$ (consistent with Part 1, since for the canonical link $\frac{d\mu }{d\eta }=b^{″}=V$). Differentiate again: $${\nabla }^2\ell (\beta )=-\frac{1}{\varphi }\sum _i{b}^{″}({\eta }_i)x_i{x}_i^{\top }.$$

The step a candidate can miss: the data $y_i$ have disappeared from the Hessian. Two consequences.

• $b^{″}>0$ by strict convexity, so each $b^{″}({\eta }_i)x_i{x}_i^{\top }⪰0$, hence ${\nabla }^2\ell ⪯0$: the log-likelihood is concave, and any stationary point is a global maximum.
• The observed information $-{\nabla }^2\ell$ is nonrandom given the design, so it equals its own expectation, the Fisher information: $J(\beta )=I(\beta )=\frac{1}{\varphi }{\sum }_i{b}^{″}({\eta }_i)x_i{x}_i^{\top }$.

Newton–Raphson updates with the observed Hessian; Fisher scoring updates with the expected one. When the two coincide, so do the iterations. This is exactly the algebraic content of "the canonical link makes Fisher scoring the same as Newton–Raphson."

3. Gamma with log link: the two informations diverge

(a) Here $V(\mu )={\mu }^2$ and ${\mu }_i=e^{{\eta }_i}$, so $\frac{d{\mu }_i}{d{\eta }_i}={\mu }_i$. Plugging into Part 1, $$U(\beta )=\frac{1}{\varphi }\sum _i\frac{y_i-{\mu }_i}{{\mu }_i^2}{\mu }_i{x}_i=\frac{1}{\varphi }\sum _i(\frac{y_i}{{\mu }_i}-1)x_i.$$ Since $y_i/{\mu }_i=y_i{e}^{-{\eta }_i}$, we have $\partial (y_i/{\mu }_i)/\partial {\beta }_k=-y_i{e}^{-{\eta }_i}{x}_{ik}=-(y_i/{\mu }_i)x_{ik}$, so $${\nabla }^2\ell (\beta )=-\frac{1}{\varphi }\sum _i\frac{y_i}{{\mu }_i}{x}_i{x}_i^{\top },J(\beta )=\frac{1}{\varphi }\sum _i\frac{y_i}{{\mu }_i}{x}_i{x}_i^{\top }.$$ Now the $y_i$ remain. Taking expectations, $𝔼[y_i/{\mu }_i]=1$, so $$I(\beta )=\frac{1}{\varphi }\sum _i{x}_i{x}_i^{\top },$$ which depends only on the design — not on $\beta$ at all, a pleasant surprise specific to the Gamma–log combination.

(b) Write $r_i:=y_i/{\widehat{\mu }}_i-1=(0.2,-0.4,0.2)$. The score equations $U(\widehat{\beta })=0$ read ${\sum }_i{r}_i{x}_i=0$, i.e. $$\sum _i{r}_i=0.2-0.4+0.2=0,\sum _i{z}_i{r}_i=(-1)(0.2)+0+(1)(0.2)=0.$$ Both hold, so the configuration is a legitimate MLE.

The gap is $$J(\widehat{\beta })-I(\widehat{\beta })=\frac{1}{\varphi }\sum _i{r}_i{x}_i{x}_i^{\top },x_i{x}_i^{\top }=\left(\begin{array}{cc}1& z_i\\ z_i& z_i^2\end{array}\right).$$ Entrywise: the $(1,1)$ entry is ${\sum }_i{r}_i=0$; the $(1,2)$ entry is ${\sum }_i{r}_i{z}_i=0$ (these are exactly the two score equations); the $(2,2)$ entry is $$\sum _i{r}_i{z}_i^2=(0.2)(1)+(-0.4)(0)+(0.2)(1)=0.4.$$ Therefore $$\boxed{J(\widehat{\beta })-I(\widehat{\beta })=\frac{1}{\varphi }\left(\begin{array}{cc}0& 0\\ 0& 0.4\end{array}\right)}$$ nonzero, so observed and expected information genuinely differ at the MLE.

Closing note

The instructive point is why the discrepancy survives at the optimum. The score equations force only the first-moment combinations ${\sum }_i{r}_i{x}_i$ to vanish; the informations differ through the second-moment combination ${\sum }_i{r}_i{x}_i{x}_i^{\top }$, and the $z^2$ direction is not among the constraints the score imposes. So the tempting reflex "observed information equals Fisher information at the MLE" is a canonical-link artifact (Part 2), not a general fact. For a non-canonical link the two coincide in expectation but not in realization, which is precisely why Fisher scoring and Newton–Raphson take different steps — and why standard-error formulas must state which information matrix they use.