27.09.2019 17:21
GodCoder 6 4800 Источник

Вступление


Бывало когда-нибудь такое, что вы хотите просуммировать какой-то бесконечный ряд, но не можете подобрать частичную сумму ряда? Вы все ещё не пользовались дискретной производной? Тогда мы идём к вам!

Определение


Дискретной производной последовательности $a_n$ назовем такую последовательность $\Delta a_n$, что для любых натуральных $n>1$ выполняется:

$\Delta a_n = a_n - a_{n-1}$



Рассмотрим примеры:

  • $a_n = 1\\ \Delta a_n = a_n - a_{n-1} = 1 - 1 = 0$

  • $a_n = n\\ \Delta a_n = a_n - a_{n-1} = n - (n - 1) = 1$

  • $a_n = n^2\\ a_n = n^2 - (n - 1)^2 = n^2 - (n^2 - 2n + 1) = 2n-1$

  • $a_n = n^3\\ \Delta{a_n} = n^3 - (n - 1)^3 = 3n^2 - 3n + 1$

  • $a_n = k^n\\ \Delta{a_n} = k^n - k^{n-1} = k^{n-1}(k-1)$


Ну, суть вы поняли. Чем-то напоминает производную функции, правда? Мы поняли как вычислять дискретные производные «простейших» последовательностей. Кхм, но что делать с суммой, разностью, произведением и частным последовательностей? У «обычной» производной есть некоторые правила дифференцирования. Давайте-ка придумаем для дискретной!

Сначала рассмотрим сумму. Логично, что сумма последовательностей это тоже какая-то последовательность. Попробуем найти производную по определению:

$\Delta{(a_n + b_n)} = a_n + b_n - (a_{n - 1} + b_{n - 1}) = \\ =a_n - a_{n - 1} + b_n - b_{n - 1} = \Delta{a_n} + \Delta{b_n}$


Феноменально! Мы получили, что производная суммы последовательностей есть сумма производных этих последовательностей!спасибо, кэп
Попробуем доказать тоже самое с разностью

$\Delta{(a_n - b_n)} = a_n - b_n - (a_{n - 1} - b_{n - 1}) = \\ =a_n - a_{n - 1} -( b_n - b_{n - 1}) = \Delta{a_n} - \Delta{b_n}$


А мы переходим к произведению!
Аналогично, найдем по определению:

$\Delta{(a_nb_n)} = a_nb_n - a_{n-1}b_{n-1} = \\ =a_nb_n-a_{n}b_{n-1} + a_nb_{n-1} - a_{n-1}b_{n-1} = \\ =a_n(b_n - b_{n-1}) + b_{n-1}(a_n - a_{n-1}) = \\ =a_n\Delta{b_n} + b_{n-1}\Delta{a_n}$


Круто, правда? Рассмотрим частное:

$\Delta(\frac{a_n}{b_n}) = \frac{a_n}{b_n} - \frac{a_{n - 1}}{b_{n-1}}= \frac{a_nb_{n-1}-a_{n-1}b_n}{b_nb_{n-1}} =\\ =\frac{a_nb_{n-1}-a_nb_n+a_nb_n-a_{n-1}b_n}{b_nb_{n-1}}=\\ =\frac{b_n\Delta{a_n}-a_n\Delta{b_n}}{b_nb_{n-1}}$


Cool...

Но это все производная. Может, есть и дискретная первообразная? Оказывается, есть!

Еще определения


Дискретной первообразной последовательности $a_n$ называют такую последовательность $A_n$ что для любых натуральных $n>1$ выполняется:

$a_n = \Delta A_n$


  • $a_n = 1\\ \Delta A_n = a_n \iff A_n = n$

  • $a_n = n\\ n = \frac{2n-1}{2}+\frac{1}{2} = \frac{\Delta n^2 + \Delta n}{2} = \frac{\Delta (n^2 + n)}{2}\\ \Delta A_n = a_n \iff A_n = \frac{n^2+n}{2}$


С этим понятно. Го придумаем аналог Ньютона-Лейбница!

$\sum_{i=1}^{n}a_i = a_1 + a_2+a_3+...+a_n=\\ =A_1 - A_0 + A_2 - A_1 +... +A_n - A_{n-1}=\\ =A_{n} - A_0$


Да ладно! Вот это прикол совпадение! А теперь то же самое покрасивее:

$\sum_{i=1}^n a_ = \sum_{i=1}^n \Delta A_i = A_i\bigg|_{1}^{n}$


И обобщим на множество натуральных чисел от $a$ до $b$:

$\sum_{i=a}^{b}f(i) = F_i\bigg|_a^b$


Применение


Кто помнит ту самую формулу для суммы ряда квадратов натуральных чисел от $1$ до $n$? А вот и я не помню. Давайте-ка ее выведем!
Но для начала надо найти первообразную для последовательности $a_i = i^2$:

$i^2 = (3i^2-3i+1)\frac{1}{3} + i - \frac{1}{3} = (3i^2-3i+1)\frac{1}{3} + i - \frac{1}{3} =\\ =\frac{1}{3}\Delta i^3 + \frac{1}{2}\Delta(i^2 + i) - \frac{1}{3}\Delta i = \\ =\Delta\frac{2i^3 + 3i^2+3i-2i}{6}=\Delta\frac{2i^3+3i^2+i}{6}$


А теперь, собственно, сама сумма:

$\sum_{i=1}^{n}i^2 = \frac{2i^3+3i^2+i}{6}\bigg|_0^n = \frac{2n^3+3n^2+n}{6} $


Как насчет суммы кубов?

Сначала вычислим

$\Delta i^4 = i^4 - (i-1)^4=i^4-(i^4 - 4 i^3 + 6i^2-4i+1) = 4i^3 - 6i^2 +4i-1$


Первообразная для $i^3$:

$ i^3 = \frac{1}{4}(4i^3-6i^2+4i-1)+\frac{3}{2}i^2-i+\frac{1}{4}=\\ =\frac{\Delta i^4}{4}+\frac{3}{2}\Delta{\frac{2i^3+3i^2+i}{6}}-\Delta{\frac{i^2+i}{2}}+\frac{\Delta{i}}{4}=\\ =\Delta{\frac{i^4+2i^3+3i^2+i-2i^2-2i+i}{4}}=\Delta{\frac{i^4+2i^3+i^2}{4}}=\\ =\Delta{\bigg(\frac{i(i+1)}{2}\bigg)^2}\\ \sum_{i=1}^{n}i^3=\bigg(\frac{i(i+1)}{2}\bigg)^2\bigg|_0^n = \bigg(\frac{n(n+1)}{2}\bigg)^2$



Кхм, казалось бы, ничего сложного…

Для продвинутых


Не всегда так просто найти интеграл, правда? Что мы делаем в трудных случаях? Правильно, интегрируем по частям. Быть может, есть аналог? Не буду вас томить, он есть, и сейчас мы его выведем.

Допустим, надо вычислить сумму ряда

$p = const\\\sum_{i=1}^{n}ip^{i}=?$

Что делать? Вряд ли вы сможете так просто подобрать дискрентную первообразную к последовательности. Давайте смотреть.

Мы уже знаем, что:

$\Delta{(f(n)g(n))} = f(n)\Delta{g(n)} + g(n-1)\Delta f(n)$


Тогда

$\sum_{i=a}^{b}\Delta (f(i)g(i)) = \sum_{i=a}^b f(i)\Delta g(i) + \sum_{i=a}^{b}g(i-1)\Delta f(i)\iff \\ \iff\sum_{i=a}^b f(i)\Delta g(i) = \sum_{i=a}^{b}\Delta (f(i)g(i)) -\sum_{i=a}^{b}g(i-1)\Delta f(i)$


А теперь один нетривиальный шаг:

$\sum_{i=a}^{b}\Delta (f(i)g(i)) = f(a)g(a)-f(a-1)g(a-1)+f(a+1)g(a+1) - f(a)g(a)+\\ + ... + f(b)g(b)-f(b-1)g(b-1) = f(b)g(b)-f(a-1)g(a-1)$


Подставим в полученное до этого равенство:

$\sum_{i=a}^b f(i)\Delta g(i) = f(b)g(b)-f(a-1)g(a-1) -\sum_{i=a}^{b}g(i-1)\Delta f(i)$


Финита ля комедия.

Найдем ту самую сумму:

$\sum_{i=1}^n{ip^{i}} = S_n\\ p^i = \Delta{\frac{p^{i+1}}{p-1}}\\ S_n = \sum_{i=1}^n i\Delta{\frac{p^{i+1}}{p-1}} \\$


Кому-то может показаться, будто формула стала еще более громоздкой, и мы только усложнили себе работу. Но это не так. Пусть $f(i) = i, g(i) = \frac{p^{i+1}}{p-1}$, тогда:

$\sum_{i=1}^n f(i)\Delta g(i) = f(n)g(n)-f(0)g(0) -\sum_{i=1}^{n}g(i-1)\Delta f(i) = \\ =n\frac{p^{n+1}}{p-1} - 0 -\sum_{i=1}^{n}\frac{p^{i}}{p-1} = n\frac{p^{n+1}}{p-1}-\bigg(\frac{1}{p-1}\sum_{i=1}^{n}p^i\bigg)=\\ = n\frac{p^{n+1}}{p-1}-\bigg(\frac{1}{p-1}\sum_{i=1}^{n}\Delta{\frac{p^{i+1}}{p-1}}\bigg) = \\ = n\frac{p^{n+1}}{p-1}-\bigg(\frac{p^{n+1}-p}{(p-1)^2}\bigg) = \frac{np^{n+2}-(n+1)p^{n+1}+p}{(p-1)^2}$



Прикольная задачка


Предлагаю попрактиковаться с этим на примере задачки с отбора в Tinkoff Generation на курсы по Machine Learning. Вот сама задачка:

Вы устали решать задачки с отборов на курсы Tinkoff Generation и решили устроить перерыв, посмотрев несколько серий нового сериала, о котором все говорят.

Вы начинаете смотреть все серии, начиная с первой. Каждая серия длится один час. После просмотра очередной серии, вы с постоянной вероятностью ?ppp? начинаете смотреть следующую, иначе ваш перерыв заканчивается, и вы возвращаетесь к работе.

Голод, сон и прочие нужды вас не останавливают, а в сериале бесконечное количество серий; в теории, ваш перерыв может длиться бесконечно.

Сколько в среднем будет длиться ваш перерыв?

Строго говоря, здесь нам нужно найти математическое ожидание. Давайте разбираться.

Решение


Вероятность того, что перерыв будет длиться 1 час, равна:

$P(1) = 1 - p$


2 часа

$P(2) = p(1-p)\\...$


n часов:

$P(n) = p^{n-1}(1-p)$


Тогда математическое ожидание равно:

$E[X] = \lim\limits_{n \to \infty}{\sum_{i=1}^ni*P(i)}=\lim\limits_{n \to \infty}{\sum_{i=1}^ni*(1-p)p^{i-1}}=\\ =(1-p)\lim\limits_{n \to \infty}{\sum_{i=1}^ni*p^{i-1}}$


Знакомо, правда?

Мы уже находили, что

$\sum_{i=1}^nip^{i}=\frac{np^{n+2}-(n+1)p^{n+1}+p}{(p-1)^2}$


тогда совсем очевиден нужный нам ряд:

$\sum_{i=1}^nip^{i-1} =\frac{1}{p}\sum_{i=1}^nip^{i}= \frac{np^{n+1}-(n+1)p^n+1}{(p-1)^2}$


И задача сводится к нахождению предела последовательности

$\lim\limits_{n\to\infty}\frac{np^{n+1}-(n+1)p^n+1}{(p-1)^2}$


где $p<1$, так как $p$ — вероятность события.
Докажем теперь, что

$\lim\limits_{n\to\infty}np^{n+1}=0, \space \lim\limits_{n\to\infty}p^n(n+1) = 0$


  • $f(x) = p^{x+1}x, \space x \in \!R\\ p = \frac{1}{q}, \space 0< p< 1 \iff q>1\\ \lim\limits_{x\to\infty}{f(x)} = \lim\limits_{x\to\infty}{p^{x+1}x} = \lim\limits_{x\to\infty}{\frac{x}{q^{x+1}}} = \\ = \lim\limits_{x\to\infty}{\frac{x'}{(q^{x+1})'}} = \lim\limits_{x\to\infty}{\frac{1}{q^{x+1}\ln q}} = 0\\ \lim\limits_{x\to\infty}f(x) = 0 \implies\lim\limits_{n\to\infty}f(n) \iff \lim\limits_{n\to\infty}np^{n+1} = 0$


  • $f(x) = p^{x}(x+1), \space x \in \!R\\ p = \frac{1}{q}, \space 0< p< 1 \iff q>1\\ \lim\limits_{x\to\infty}{f(x)} = \lim\limits_{x\to\infty}{p^{x}(x+1)} = \lim\limits_{x\to\infty}{\frac{x+1}{q^{x}}} = \\ = \lim\limits_{x\to\infty}{\frac{(x+1)'}{(q^{x})'}} = \lim\limits_{x\to\infty}{\frac{1}{q^{x}\ln q}} = 0\\ \lim\limits_{x\to\infty}f(x) = 0 \implies\lim\limits_{n\to\infty}f(n) \iff \lim\limits_{n\to\infty}(n+1)p^{n} = 0$



Теперь легко понять, что

$\lim\limits_{n\to\infty}\frac{np^{n+1}-(n+1)p^n+1}{(p-1)^2} = \frac{1}{(p-1)^2}$


И

$E[X] = (1-p)\lim\limits_{n\to\infty}\sum_{i=1}^n{ip^{i-1}} = (1-p)\frac{1}{(p-1)^2} = \frac{1}{1-p}$



Some up


Фух… Это было easy-peasy жестко, даже для меня, дорогие читатели. Список достижений за сегодня:

  1. Мы поняли, что такое дискретная производная
  2. Вывели свойственные ей правила дифференцирования
  3. Мы поняли, что такое дискретная первообразная
  4. Мы вывели аналог формулы Ньютона-Лейбница
  5. Вывели аналог интегрирования по частям
  6. Решили сложную задачку с отбора на Tinkoff Generation курсы по ML

Неплохо для начала, а вы как считаете?

Жду ваших замечаний в комментах, коршуны самые внимательные!

Комментарии (6)


  1. Griboks
    27.09.2019 21:56
    #20682219
    +1

    И задача сводится к нахождению предела последовательности

    Честно говоря, я проверил вашу формулу на миллионе итераций, и она даже близко не дала мат. ожидание.


    1. nitrosbase
      28.09.2019 00:41
      #20682697

      Вы, возможно, предполагали, что первая серия тоже будет посмотрена с вероятностью p, а не безусловно. У вас при p=1/3 получается 0.5 или 1.5?


      GodCoder, задачу на суммирование б/у геометрической прогрессии нельзя называть «сложной».


      1. GodCoder Автор
        28.09.2019 07:09
        #20683027

        1.5


      1. Griboks
        28.09.2019 10:17
        #20683235

        Действительно, не заметил, что автор решал другую задачу. Проверил его — всё сошлось. GodCoder, извиняюсь, если задел ваши чувства.


  1. Refridgerator
    27.09.2019 22:38
    #20682361
    -2

    В примерах я ожидал увидеть что-то типа {1,2,3,0} -> {1,1,-3}. Но не увидел. Поэтому до сих пор не уверен, что правильно понял посыл статьи.


  1. excoder
    28.09.2019 00:30
    #20682683
    +1

    Лучшее по этой теме: Кнут, Конкретная математика.