Суммы, произведения и смена порядка

Σ — это цикл

$$\sum_{\htmlData{k=i}{i} = \htmlData{k=lo}{1}}^{\htmlData{k=hi}{n}} \htmlData{k=term}{a_i}$$

Дословный перевод:

total = 0
for i in range(1, n + 1):
    total += a[i]

Единственное расхождение — верхний предел включительный, в отличие от range. Это источник постоянных ошибок на единицу при переносе формул в код.

∑ 4 i = 1 i * i

верхний предел

4

1 * 1 1 +2 * 2 4 +3 * 3 9 +4 * 4 16 = 30

Соглашения, которые стоит знать:

• пустая сумма равна нулю: если верхний предел меньше нижнего, результат $0$ (для $\prod$ — единица). Это не произвол: ноль нейтрален относительно сложения, единица — относительно умножения;
• индекс — связанная переменная: $\sum_i a_i$ и $\sum_j a_j$ — одно и то же;
• предел часто опускают, когда он ясен из контекста: $\sum_i x_i$ означает «по всем допустимым $i$».

Что можно выносить

Константу — то, что не зависит от индекса — можно вынести за знак суммы:

$\sum_{i} c \cdot a_i = c \sum_i a_i$

А вот это уже неверно и является самой частой ошибкой:

$\sum_i a_i b_i \ne \left(\sum_i a_i\right)\left(\sum_i b_i\right)$

Слева $n$ произведений, справа — $n^2$. Проверьте на $a = b = (1, 1)$: слева $2$, справа $4$.

Логарифм превращает произведение в сумму:

$\log \prod_i p_i = \sum_i \log p_i$

Это единственная причина, по которой в машинном обучении работают с log-likelihood, а не с likelihood: произведение тысячи вероятностей уходит в машинный ноль, сумма логарифмов — нет.

Двойные суммы

$\sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij}$

Вложенный цикл. Порядок сложения не влияет на результат при конечном числе слагаемых, поэтому

$\sum_{i} \sum_{j} a_{ij} = \sum_{j} \sum_{i} a_{ij}$

Смена порядка суммирования — рабочий приём, который в выводах используют постоянно. Обычно его применяют, чтобы внутренняя сумма превратилась во что-то известное.

Пример из блока 1. Скалярное произведение через матрицу:

$\mathbf{x}^\top A \mathbf{y} = \sum_i \sum_j x_i A_{ij} y_j$

Здесь $x_i$ не зависит от $j$, поэтому его можно вынести из внутренней суммы:

$= \sum_i x_i \left( \sum_j A_{ij} y_j \right) = \sum_i x_i (A\mathbf{y})_i = \mathbf{x}^\top (A \mathbf{y})$

Три строки, и получена ассоциативность — просто перегруппировкой.

Осторожно с бесконечными суммами. Для бесконечных рядов менять порядок можно не всегда: при условной сходимости перестановкой слагаемых можно получить любую сумму (теорема Римана). В статьях это условие обычно подразумевают выполненным и не оговаривают.

Когда пределы зависят друг от друга

$\sum_{i=1}^{n} \sum_{j=i}^{n} a_{ij}$

Внутренний предел зависит от внешнего — суммирование идёт по верхнему треугольнику. При смене порядка пределы приходится пересчитывать:

$\sum_{i=1}^{n}\sum_{j=i}^{n} a_{ij} = \sum_{j=1}^{n}\sum_{i=1}^{j} a_{ij}$

Проверять такие переходы проще всего рисунком: нарисуйте квадрат $n \times n$ и заштрихуйте область, по которой идёт суммирование. Оба способа обхода должны покрывать одну и ту же область.

Произведение

$\prod$ работает так же, с умножением вместо сложения:

∏ 5 i = 1 i

верхний предел

5

1 1 ·2 2 ·3 3 ·4 4 ·5 5 = 120

Это факториал. И заодно демонстрация того, почему пустое произведение равно единице: $0! = 1$ — не исключение из правила, а прямое следствие соглашения.