inequality_draft.ipynb

Kernel: Python 2 (SageMath)

Inequality proof

The setting in Silverman's book is the following: Let ${\bf{s}} = c_1c_2c_3\dots c_n$ be a string of n alphabetic characters and let $F_i$ be the frequency with which letter i appears in the string $\bf{s}$.

Also, define $IndCon({\bf{s}}) := \frac{1}{n\left(n-1\right)} \sum_{i=0}^{25} F_i \left(F_i -1\right)$.

Our setting will be a slightly more general. Instead of 25 letters, we assume there are $k$ letters. We would like to prove that (for $k \geq 1$) $$\begin{alignat}{2} \frac{1}{n\left(n-1\right)} &\sum_{i=0}^{\color{red}k} F_i \left(F_i -1\right) &&\geq \frac{1}{n\left(n-1\right)} \sum_{i=0}^{\color{red}k} \frac{n}{k} \left(\frac{n}{k} -1\right) = \frac{k}{n\left(n-1\right)} \frac{n}{k} \left(\frac{n}{k} -1\right) \\ \Leftrightarrow &\sum_{i=0}^{\color{red}k} F_i \left(F_i -1\right) &&\geq k \frac{n}{k} \left(\frac{n}{k} -1\right) \end{alignat}$$

The Left Hand side of the inequality corresponds to an arbitary distribution while the Right Hand side corresponds to the unifrom distribuation in which each letter occurs with an equal probability (completely random text).

Roughly Speaking

Let's see what happens in an extreme case. If $F_1 = n$ and $F_i = 0,\ i \not = 1$ then what we want to show is $n\left(n-1\right) \geq k \frac{n}{k} \left(\frac{n}{k} -1\right)$

Since $n \approx n-1$ we may repalce $n-1$ with $n$, so, the last inequality becomes $n^2 \geq k \frac{n^2}{k^2} \Leftrightarrow 1 \geq \frac{k}{k^2} = \frac{1}{k} \Leftrightarrow k\cdot 1 \geq 1$.

Proof

Two letters (Prerequisite: Caculus I)

If the minimu value of the function $f\left(F_1, F_2\right) = F_1\left(F_1 -1\right) + F_2\left(F_2 -1\right)$, where $F_1 + F_2 = n{\bf,} \ F_i \in [1, n]$, occurs at $F_1 = F_2 = \frac{n}{2}$ then we are done.

From the relation $F_1 + F_2 = n$ we can consider $f$ as a function in one variable, i.e. $f(F_1) = F_1\left(F_1 -1\right) + \left(n- F_1\right) \left(n - F_1 -1\right)$ It is easier to deal with functions of one variable instead of two.

From Calculus I we know $f$ attains the minimum value at the boundary points or on the critical points.

Finding the critical points

$\frac{d}{dF_1} f = F_1 + F_1 -1 -\left(n- F_1 -1\right) - \left(n- F_1 \right) = 4F_1 - 2n \Rightarrow 0 = \frac{d}{dF_1} f \Leftrightarrow 4F_1 -2n = 0 \Leftrightarrow F_1 = \frac{n}{2}$. Thus,there is, only, one critical poitn $F_1 = \frac{n}{2}$

Computing the global minimum/maximum

$F_1$	0	$\frac{n}{2}$	n
$f(F_1)$	$n\left(n-1\right)$	$2\cdot \frac{n}{2}\left(\frac{n-2}{2}\right)$	$n\left(n-1\right)$

As we can see the least value in the above table is $2\cdot \frac{n}{2}\left(\frac{n-2}{2}\right)$ which corresponds to $F_1 = F_2 = \frac{n}{2}$, as required!

Three letters or more (Calculus III)

Let $f\left(F_1, F_2, \dots , F_k\right) = \sum_i F_i\left(F_i -1\right)$ subjects to $g\left(F_1, F_2, \dots, F_k\right) = \left(\sum_i F_i\right) -n$

We are interested in finding points that maximize/minimize $f$. As in the case Two letters, if we show that the minimum occurs at $F_1 = F_2 = \dots = F_k$ then we are done.

Recall: The method of Lagrange multipliers find the maximum/minimum when the gradient of a specific function equals to zero. Below a break down of the of the method which can be implemented in SageMath

1. Compute $\nabla \cdot \left( f-\lambda g\right) = \frac{\partial}{\partial F_1}\left( f-\lambda g\right) dF_1 + \frac{\partial}{\partial F_2}\left( f-\lambda g\right) dF_2 + \dots + \frac{\partial}{\partial F_k}\left( f-\lambda g\right) dF_k$ where $\lambda$ is an extra variable.

2. Since $dF_i$s are linearly independent then $\nabla \cdot \left( f-\lambda g\right) = 0 \Leftrightarrow \frac{\partial}{\partial F_1}\left( f-\lambda g\right) = 0$ for each $i$

3. Solve these equations to find the critical points

4. Substitute each critical point $\left(x_1, x_2, \dots, x_k\right)$ in $f$ i.e. compute $f\left(x_1, x_2, \dots, x_k\right)$ then record it in some set, say $M$. The maximum or minimum value of $f$ subjects to the constraint $g$ must be in $M$

1: For each variable $F_1, F_2, \dots, F_k$ we have $\frac{\partial}{\partial F_i} f = F_i + F_i -1 = 2F_i -1$ and $\frac{\partial}{\partial F_i} \lambda \cdot g = \lambda$

2: $$\begin{alignat}{2} &2F_1-1 - \lambda = 0 \Rightarrow F_1 = \frac{1+\lambda}{2}\\ &2F_2-1 - \lambda = 0 \Rightarrow F_2 = \frac{1+\lambda}{2}\\ &\vdots \\ &2F_k-1 - \lambda = 0 \Rightarrow F_k = \frac{1+\lambda}{2}\\ & \sum_i F_i = n \end{alignat}$$

3: Hence, $F_i = F_j$ for all $i, j$. . If we find the value of $F_1$ then we found all $F_i$s value, since they are equal to each other. Using the last result, $\sum_i F_i = F_1 \sum_i 1 = n \Rightarrow F_1= F_2= \dots= F_k = \frac{n}{k}$

4: $f\left(\frac{n}{k},\frac{n}{k}, \dots, \frac{n}{k}\right) = k \frac{n}{k} \left(\frac{n}{k} -1\right) = n \left(\frac{n}{k} -1\right)$. We know that $n \left(\frac{n}{k} -1\right)$ is an extreme value, but we don't know whether it is a minimum value or not. Let us plug in $f$ with any other point. For instance, $F_1 = n, F_i = 0, i\not = j$ then it is clear that $n\left(n-1\right) \geq n \left(\frac{n}{k} -1\right) \Leftrightarrow n\geq \frac{n}{k}$ since it is an extreme point then it must be the minimum of $f$ under the constraint $g$

We found that the minimum value $n \left(\frac{n}{k} -1\right)$ occurs at $F_1 = F_2 = \dots = F_k$ Q.E.D