Estimating variance with $\gcd$ in it

Question

This is a continuation from Wilf's exercise on codewords (although this question is (mostly) independent from the previous question).

---

Question:

Suppose $n \in \mathbb{N}$ so that it can be written as $n = 2^\alpha n''$, with $n''$ being odd and consider the formula:

$$\beta_r = \frac{1}{2n} \sum _{j=1} ^{n''} 2^{2^\alpha \gcd(j,n'')} \exp \left(-\frac{2\pi i j}{n''} r\right)$$

Wilf's generatingfunctionology (Chapter 2, Ex 25e, first part of exercise):

Use Parseval's identity and the result of part (d) to find the variance of the occupancy numbers $\beta_0, ..., \beta_{2n - 1}$.

Given $N = \beta_0 + \beta_1 + ... + \beta_{2n - 1} = 2^n$.

Being unfamiliar with this theorem, I have read Parseval's identity from different websites (with different versions?), but am uncertain how this can be used since they seem to have it with infinite sums/integrals, whereas the question is made up of finite sums.

---

EDIT:

I figured the first part of the exercise in the answer, which gives variance to be: $$\sigma^2 = \frac{1}{4n^2}\sum _{j=1}^{n'' -1}\left( 2^{2^\alpha \gcd(j, n'') } \right)^2$$

This leaves the 2nd part:

Wilf's generatingfunctionology (Chapter 2, Ex 25e, second part of exercise):

Make an estimate that showsthat the variance is in some sense very small, so that this coloring scheme is shown to distribute codewords into color classes very uniformly.

And would like to ask again on how you would make an estimate with a function like $\gcd$ in it?

Answer 1

It appears I was reading the question wrong, and it wanted to calculate the sample mean & variance, not variance related to discrete random variables.

Since $N= \sum _{r = 0}^{2n-1} \beta_r = 2^n$, we already have $\mu = \frac{2^n}{2n}$.

To calculate sample variance, use the formula:

$$\sigma^2 = \frac{1}{2n} \sum_r {(\beta_r - \mu)^2} = \frac{1}{2n}\left(\sum_r \beta_r^2\right) -\mu^2 \tag{1}$$

To calculate the first term, note that if we let: $$ \textbf{x} = \left( 2^{2^\alpha \gcd(1,n'')}, 2^{2^\alpha \gcd(2,n'')}, ..., 2^{2^\alpha \gcd(n,n'')} \right)$$

$$f_t = \frac{1}{\sqrt{n''}}\left( e^{2\pi i \frac{t}{n''}}, e^{4\pi i \frac{t}{n''}}, ..., e^{2n''\pi i \frac{t}{n''}} \right)$$

So that:$$\beta_r = \frac{\sqrt{n''}}{2n}\langle \mathbf{x}, f_r \rangle$$

Then $\{ f_0, f_1, ..., f_{n'' - 1} \}$ forms an orthonormal basis in $\mathbb{C}^{n''}$ with the standard inner product. Using Parseval's identity for Hilbert spaces:

$$\begin{align}\sum_{r=0}^{n'' - 1} \beta_r ^2 &= \sum_{r=0}^{n'' - 1} |\beta_r|^2 \\ &= \frac{n''}{4n^2}\sum_{r=0}^{n'' - 1} |\langle \mathbf{x}, f_r \rangle|^2 = \frac{n''}{4n^2}\langle \mathbf{x}, \mathbf{x} \rangle \\ &= \frac{n''}{4n^2}\sum _{j=1}^{n''}\left( 2^{2^\alpha \gcd(j, n'') } \right)^2 \end{align}$$

And note that from the first term in $(1)$, we use the fact that $cn'' + r \equiv r \mod n''$ given $r = 0, ..., n'' - 1$: $$\sum_{r=0}^{2^{\alpha + 1}n''-1} \beta_r^2 = \sum_{c=0}^{2^{\alpha +1} - 1}\sum_{r=0}^{n''-1} \beta_{cn'' + r}^2 = \sum_{c=0}^{2^{\alpha +1} - 1}\sum_{r=0}^{n''-1} \beta_{r}^2 = 2^{\alpha +1}\sum_{r=0}^{n''-1} \beta_{r}^2$$

Putting these together, we have: $$\begin{align} \sigma^2 &= \frac{1}{4n^2}\sum _{j=1}^{n''}\left( 2^{2^\alpha \gcd(j, n'') } \right)^2 - \frac{2^{2n}}{4n^2} \\ &= \frac{1}{4n^2}\sum _{j=1}^{n'' -1}\left( 2^{2^\alpha \gcd(j, n'') } \right)^2 \tag{2} \end{align}$$

---

For the second part of the question, using an inequality for sums of squares and another inequality yields:

$$\frac{1}{n'' - 1} (\beta_0 - \mu)^2 \leq \sigma^2 \leq (\beta_0 - \mu)^2$$

Note that $\beta_0 / \mu \approx 1$, especially for large $n$:

$$ \begin{align} \frac{\beta_0}{\mu} &= \sum_{j=1}^{n''} 2^{2^\alpha (\gcd(j,n'') - n'')} \\ &= 1 + \sum_{j=1}^{n'' - 1} 2^{2^\alpha (\gcd(j,n'') - n'')} \\ &\leq 1 + \sum_{j=1}^{n'' - 1} 2^{2^\alpha (\frac{n''}{3} - n'')} \tag{3} \\ &= 1 +(n''-1){2^{-2n/3}} \approx 1 \end{align} $$

In $(3)$, use the fact that $\gcd(j,n'') \neq n''$ if $j = 1,...,n''-1$ and so the next largest value (assuming $n''>1$ and odd) is $\gcd(j,n'') \leq n''/3$. Note the above inequality remains true even if $n'' = 1$.

And in the other direction:

$$ \begin{align} \frac{\beta_0}{\mu} &= 1 + \sum_{j=1}^{n''-1} 2^{2^\alpha (\gcd(j,n'')-n'')} \\ &\geq 1 + \sum_{j=1}^{n'' - 1} 2^{2^\alpha (-n'')} \\ &= 1 +(n''-1){2^{-n}} \approx 1 \end{align} $$

Also, $\beta_0/\mu \leq 1.5$. So in relative magnitude, $\beta_0 \approx \mu$ as $n$ increases and in this respect, the variance is small in this relative sense (although not in absolute sense).