7 февраля 2016 в 15:34

Продолжение задачи о конфетах (или еще раз о Центральной Предельной Теореме)

Недавно viktorpanasiuk опубликовал задачу о конфетах, которая «зацепила» многих (в частности, koldyr опубликовал на Хабре свое аналитическое решение), в том числе и меня. Задача практическая, от инженера-кондитера, формулировалась так: «Найти максимально допустимое отклонение массы конфеты при ее производстве, чтобы нетто коробки, состоящей из n=12 штук их, не выходило за пределы M=310±7 грамм в 90% случаев. Закон распределения считать нормальным».

Автор решил задачу, исходя из предположения о нормальном распределении конфет по массе, и нашел среднюю массу конфеты (очевидно, равную µ=M/n=25.83 г) и стандартное отклонение σ=1.23 г. Использование метода Монте-Карло, т.е. генерация N*n случайных чисел с гауссовым распределением конфет со средним µ и стандартным отклонением σ, подтверждает правильность решения. Распределение масс коробок является гауссовым, и его параметры близки к найденным аналитически (расчеты в Mathcad Express в форматах MCDX и XPS прилагаются). На левом графике показана гистограмма плотности распределения (по массе) конфет, а на правом — соответственно, распределения коробок.



В финале процитированной статьи автор упоминает о немного измененной (на практике, более актуальной) задаче определения границ массы отдельной конфеты, при выходе за которые эту (чересчур большую или маленькую) конфету нужно отбросить, чтобы коробки удовлетворяли исходным условиям (310±7 г в 90% случаев). На мой взгляд, исходная статья уже содержит решение, надо лишь посмотреть на нее немного с другой точки зрения.

Чтобы сделать финальный шаг в рассуждениях, вспомним еще раз центральную предельную теорему (ЦПТ), которую можно интерпретировать так (см., например, Википедию), что сумма n независимых одинаково распределённых случайных величин (с одинаковыми или примерно одинаковыми средним и дисперсией) имеет распределение, близкое к нормальному. Обратите внимание: в условии теоремы предположений о характере распределений исходных случайных величин нет! Статистика конфет, таким образом, может быть любой, а их числа в коробке n=12, как показывает опыт, достаточно, чтобы можно было говорить о нормализации суммарного веса.

Давайте, ради того, чтобы убедиться в нормализации массы коробки, выберем модель равномерного распределения отдельных конфет по массе. Сложив 12 независимых псевдослучайных чисел и повторив этот вычислительный эксперимент N раз, убедимся в том, что гистограмма плотности распределения коробок конфет неплохо описывается нормальным законом (график справа), в то время, как распределение каждой из 12 конфет, действительно, равномерное (левый график):



Если подобрать границы отбраковки слишком больших и слишком мелких конфет таким образом, чтобы стандартное отклонение массы конфет составило те же σ=1.23 г, то, согласно ЦПТ, дисперсия коробки (суммы n=12 конфет) составит нужное значение σ2*n.

Это и есть искомый алгоритм. Предположим, у нас есть конфетная машина, которая отрегулирована на среднюю массу конфеты µ. Далее мы можем, контролируя выборочное значение дисперсии конфет, сужать допустимый интервал, вне которого конфета отбраковывается. Независимо от характера распределения, выбор такого интервала, который обеспечит стандартное отклонение массы конфеты σ=1.23, решит поставленную задачу (благодаря нормализации веса коробки, в силу ЦПТ).
Автор: @polybook
Нерепетитор.ру
рейтинг 62,08

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

  • 0
    Какие-то у вас получаются завышенные оценки, что в той статье, что в этой. Если обратиться к неравенству Чебышева, то вероятность уклонения на некоторую величину a от мат ожидания (вне зависимости от характера распределения):
    P(|X-m| >= a) <= s^2 / a ^2


    По условию задачи P = 1 — 0.9 = 0.1, a = 7 гр, получаем СКО
    s <= sqrt(4.9) ~ 2.214 гр


    Соответсвенно СКО для 1 конфеты будет в sqrt(n) раз меньше (где n = 12) по правилу сложения дисперсий независимых величин.

    Т.е. СКО для 1 конфеты должно быть в пределе 0.64 гр вне зависимости от формы функции распределения.
    • 0
      Да нет, все правильно. Если взять Ваше пороговое СКО конфеты=0.64 г (СКО коробки=2.214), то Монте-Карло дает около 0.1...0.2% плохих коробок т.е. Р=0.001.

      А неравенство Чебышева, конечно, выполнено, т.к. 0.001 <= s^2 / a ^2=0.1
      • 0
        Да совершенно верно, я как-то проглядел что в условии распределение нормальное -)))
  • +1
    А что делать с «отброшенными» конфетами? Перерабатывать? Или съедать силами сотрудников фабрики? :)

    Мне, как неспециалисту в промышленном кондитерском деле, приходит в голову такая идея:
    На выходе из конвеера, изготавливающего единичную конфету, эта конфета взвешивается на точных весах и отправляется в один из 10 лотков (от самых легких и до самых тяжелых). Робот-фасовщик забирает конфеты из лотков таким образом, чтобы суммарная масса оказывалась такой, какой надо. Если в каком-то лотке конфеты кончились, «импровизирует», пытаясь создать как можно более близкую к эталону массу. Алгоритм в любом случае несложный. И, как мне кажется, эффективный. Возможно, правда, это — оверинжениринг в данной задаче…
  • 0
    Вы серьезно пишите, что дисперсия суммы доказывается через ЦПТ?
    • 0
      Я ничего не доказываю, а просто решаю задачу. И логика такова:
      — независимо от статистики конфет, ЦПТ дает право полагать, что статистика суммы — Гауссова.
      — автор задачи нашел S — искомую дисперсию массы для коробки. И отсюда — оценку для искомой дисперсии конфеты S/12.
      • 0
        Нет, не дает. Скорость сходимости может разная. Если 3й момент конечен, то скорость сходимости не хуже, чем 1/sqrt(n) (что вообще говоря достаточно медленно). Если 3й момент бесконечен, то может быть и медленнее.

        В то же время, сумма независимых распределений заведомо распределена нормально, так что, если масса конфеты распределена нормально — достаточно взять дисперсию, при которой 95% квантиль нормального распределения равен 7, поделить ее на число конфет и получить допустимую дисперсию массы конфеты.

        Правда, не очень понятно, что такое «максимальное отклонение массы конфеты». Если масса конфеты с вероятностью 1 не превосходит какой-то константы C — то где тут вообще нормальное распределение?
        • 0
          1. Вы правы — много факторов влияют на численный эксперимент, и интересно проследить — как именно (для того я и выкладываю расчеты в Маткаде, чтобы любой, кто интересуется, мог идти дальше.

          2. Именно! Вы дали, как мне представляется, лаконичное решение, поиску которого посвящены обе статьи:
          сумма независимых распределений заведомо распределена нормально, так что, если масса конфеты распределена нормально — достаточно взять дисперсию, при которой 95% квантиль нормального распределения равен 7, поделить ее на число конфет и получить допустимую дисперсию массы конфеты.
          Но посмотрите на комменты к первой статье (а ее автор сначала выложил саму задачу без решения, чтобы читатели могли ее сами решить).

          3. Тоже согласен, изначально сформулировано неоднозначно. Но смысл интуитивно понятен: что надо делать, чтобы 90% коробок было в пределах M=310±7 г.

          • 0
            3. Что нужно сделать как раз понятно. Непонятно, какая величина распределена нормально.
            • 0
              Нормально распределена масса коробки из 12 конфет. Неважно, как распределены по массе сами конфеты — в силу ЦПТ масса коробки будет иметь гауссово распределение.
              • 0
                Если масса коробки распределена нормально (с ненулевой дисперсией), то у нас есть ненулевая вероятность получить отрицательную массу коробки. Ооок.

                Более того, если мы ограничиваем руками массу конфеты, то сумма конечного числа таких масс никак не может иметь нормальное распределение.

                Как распределены по массе сами конфеты — важно. Не надо пихать ЦПТ туда, где ей не место.
              • 0
                Пусть масса одной конфеты распределена дискретно и принимает значение 1 с вероятностью 0.9 и значение 748/3 с вероятностью 0.1. Очевидно, что матожидание веса коробки из 12 конфет равно 310. При этом ни одна комбинация из 12 конфет не даст 310. Вывод — распределение веса конфет важно.
        • +1
          Правда, не очень понятно, что такое «максимальное отклонение массы конфеты». Если масса конфеты с вероятностью 1 не превосходит какой-то константы C — то где тут вообще нормальное распределение?

          Интересно, что примерно такое же замечание о некорректной формулировке автор исходной задачи получил в первые часы после публикации. Я в какой-то момент перестал следить за развитием, но, кажется, автор так и не понял, в чём тут проблема.
          • 0
            Я тоже согласен, что формулировка некорректная. Но автор первой статьи честно сказал — задача из реальной жизни. А в ней такое сплошь и рядом. Практический смысл задачи прозрачный: как технологу обеспечить попадание 90% продукции в диапазон 310±7 г. Да и механизм управления этим вполне ясен — отбраковывать слишком большие и слишком маленькие конфеты.
            • 0
              Извините, в реальной жизни не бывает нормального распределения. Нормальное распределение бывает в *формализации*. А если формальная формулировка некорректна, то можно строго доказать, что ответ — 42.
              • 0
                В реальной жизни, может, и не бывает, но, как модель, его очень широко используют.
                • 0
                  Тогда нужно четко прописывать, какие предположения мы делаем о реальных объектах. И следить, чтобы эти предположения не конфликтовали друг с другом.

                  И желательно в качестве предположений брать непосредственно то, что эмпирически обосновано. Например, что массы конфет распределены независимо, одинаково и их распределение удовлетворяет каким-то свойствам. Из этого можно дальше что-то выводить теоретически.

                  Постулировать что-то сразу про сумму распределений, конечно, тоже можно (формальному аппарату можно скармливать любые входные данные), но это как минимум странно.
  • 0
    Мной была предпринята попытка получить аналитическое решение. Но его, к сожалению, никто не прокомментировал.
    • 0
      Прозевал Вашу прекрасную статью! Если я правильно понял, Вы доказали, что, если выкидывать конфеты, отличающиеся от 310/12 больше, чем на σ0*sqrt(3)=2.12 г, то 90% коробок будет в пределах 310±7. Независимо от распределения конфет.

      Не врубился с ходу в Вашу математику, но похоже, Вы совершенно правы. Я когда брал равномерное распределение конфет, то выходило (по Монте-Карло), что, если оставлять только конфеты 310/12±2.13 г, то СКО конфет будет ровно σ0)=1.23 г. Соответственно, это дает нужную дисперсию коробки.

      Я проверял только на равномерном и нормальном распределении конфет (две картинки в моей статье и два кейса в файле с расчетами). А что будет, если еще какое-нибудь распределение попробовать? По-Вашему, надо обрезать по тому же уровню 2.12*σ0?
    • 0
      Прокомментирую тут.
      Пусть масса коробки — нормально распределенная случайная величина. Пусть массы конфет это одинаковые независимые в совокупности абсолютно непрерывные случайные величины


      Если масса коробки — это сумма масс конфет (не вчитывался, но кажется имеется в виду именно это), то из этих предположений уже следует, что массы конфет — это нормально распределенные с. в. (так как их характеристические функции — это корень из характеристической функции массы коробки).
      • 0
        Безусловно вы правы. Но квантиль надо откуда-то взять. В условиях задачи предложение считать массу коробки нормальной мне кажется вполне разумным.
        • 0
          Вы оба сейчас ошибаетесь. ЦПТ говорит о том, что при достаточно большом числе слагаемых сумму с.в. с (почти) любым распределением можно считать распределенной нормально. Ровно про это моя статья (можно поиграться в Маткаде).

          Почему рассуждения про х.ф. неверны — с ходу не скажу. Возможно потому, что вы решаете уравнение 12-й степени, и корень из х.ф. массы коробки — это только одно из возможных решений (не забывайте о том, что х.ф. комплексная).
          • 0
            Как минимум, в формулировке ЦПТ нет слова «можно».

            Да, функциональное уравнение f^12 = g (g — хар. функция нормального распределения) имеет бесконечно много решений. Но оно имеет только 12 непрерывных решений (т.к. g не обращается в 0), и только одно из них является хар. функцией какого-либо распределения, т.к. хар. функция в нуле должна обращаться в единицу.
            • 0
              Слово «можно» — это мостик между строгой теорией (n=бесконечность) и практикой (n=12).

              Думаю, что не только 12 непрерывных решений, а бесконечное число. Это типичная некорректная обратная задача. По самой постановке, х.ф. g задана с погрешностью (мы же изучаем выборки, где ошибки принципиально присутствуют). Поэтому для восстановления f нужны какие-то регуляризирующие идеи (в частности, гипотезы о нормальности или равномерности распределения конфет).
              • 0
                Если формальная задача некорректна, то ответ 42 на нее ничуть не хуже любого другого.

                Если мы предположили, что сумма распределена нормально (условие на математический объект), и что случайные величины распределены одинаково и независимо (опять же, условие на математический объект), то из этого уже строго выводится, что слагаемые распределены нормально.

                Зачем вообще вводить предположения о функции распределения суммы? Для использования ЦПТ нам в любом случае нужны условия на распределения конфет. Кажется гораздо более разумным при формализации сделать предположения о распределении массы конфет, а дальше уже аккуратно проверять условия ЦПТ, оценивать скорость сходимости, сравнивать распределение суммы с нормальным распределением и т.д.

                Пуанкаре как-то заметил с сарказмом, что все верят в универсальность нормального распределения: физики верят, потому что думают, что математики доказали его логическую необходимость, а математики верят, так как считают, что физики проверили это лабораторными экспериментами.
        • 0
          А почему тогда не взять в качестве квантиля 42?
          • 0
            Потому, что ЦПТ нам дает обоснование нормального закона распределения массы коробки. Поэтому (еще раз Вас процитирую)
            достаточно взять дисперсию, при которой 95% квантиль нормального распределения равен 7, поделить ее на число конфет и получить допустимую дисперсию массы конфеты.

            Требовать нормальности распределения конфет нет необходимости в силу ЦПТ (конечно с оговорками на погрешность из-за того, что 12 меньше бесконечности, из-за несовершенности датчика случайных чисел и т.д.)
            • 0
              Это при условии, что масса конфеты распределена нормально.
              (и это получается дисперсия, а не «максимально допустимое отклонение», которое вообще непонятно что такое)
            • +1
              Я Вам выше привёл пример распределения масс конфет, при котором Вы никогда не получите нужную массу коробки. И ЦПТ при фиксированном n=12 тут не поможет.
              • 0
                Ну, мы же решаем конкретную практическую задачу. Ваш пример хорош, как математическая умозрительная иллюстрация. Но понятно, что в реальной жизни распределение конфет по массам непрерывное.
                • 0
                  Ну возьмите то же самое распределение, и размажьте вероятности с точек на отрезки длины 10^-10. Получится непрерывное распределение, с теми же особенностями.
          • 0
            Формальная задача не некорректна. (Некорректной я назвал задачу восстановления распределения конфет по известному распределению массы коробки).

            Задача хороша тем, что она из реальной жизни. Именно так математику и ставят обычно задачу технологи.
            Найти максимально допустимое отклонение массы конфеты при ее производстве, чтобы нетто коробки, состоящей из n=12 штук их, не выходило за пределы M=310±7 грамм в 90% случаев.


            В задаче нет ничего про распределение. Технолог не знает статистики. Он хочет соблюсти ТУ. А как мы, математики, решили эту задачу?
            1. Показали, что распределение массы коробки — гауссово (ЦПТ), независимо от распределения конфет (мы ее не знаем, но понимаем, что оно непрерывное).
            2. Считаем дисперсию коробки, при которой 95% квантиль нормального распределения равен 7 г.
            3. Пересчитываем (ЦПТ) найденную дисперсию коробки в дисперсию конфеты (делим на корень из 12).
            4. Предлагаем технологу практическую реализацию: выкидывать слишком большие и слишком маленькие конфеты (2-я статья).

            На мой взгляд, логика безупречна.
            Еще можно и экономику посчитать — сколько фабрика сэкономит на том, что не будет перерасхода шоколада и штрафов за несоответствие ТУ.
            • 0
              В этой задаче есть непонятный термин «максимально допустимое отклонение».

              1. Показали — из каких предположений?

              Логика — это про то, как выводить одни формальные утверждения из других. Вы пока что очень не хотите указывать никаких формальных посылок (чтобы из них можно было выводить следствия).
              • 0
                1. Из предположения, что массы конфет — это независимые одинаково (неважно, как именно, но давайте считать — непрерывно) распределенные случайные величины с одинаковым средним и дисперсией.

                Из этого условия логически следует (ЦПТ), что распределение массы коробки близко к нормальному -> 2 и т.д.

                Термин «максимально допустимое отклонение», действительно, не очень хорош (так формулировал исходную задачу сам кондитер в 1й статье), но вполне допустим, на мой взгляд. Я его понимаю так: «какое отклонение конфеты от среднего можно допустить, чтобы положить конфету в коробку, а не выбросить в переплавку?».
                • 0
                  Нет, не следует, выше уже приведен пример (и непрерывность тут неважна — все интересные свойства остаются при прибавлении к распределению равномерного на отрезке [-10^-100; 10^-100] распределения, а сумма уже получится непрерывной).

                  В такой формулировке задача корректна (есть неизвестное распределение; можно его обрезать по отрезку; нужно, чтобы сумма с вероятностью 90% попала в фиксированный отрезок). Проблема в том, что для некоторых распределений такого отрезка может и вообще не существовать.
            • +1
              Задача хороша тем, что она из реальной жизни. Именно так математику и ставят обычно задачу технологи.

              Смотрите, Вы прочитали описание задачи в свободной формулировке технолога, мысленно перевели это свободное описание в формальную постановку задачи, которую нигде полностью не написали, и считаете, что все, прочитавшие исходный текст, у себя в голове получат такую же формальную задачу, как и Вы. Но почему?

              Давайте рассмотрим такой вопрос — а почему Вы решили, что матожидание коробки равно 310? Может, средний вес конфеты 27г. и матожидание веса коробки — 324 г., а технолог хочет выпускать коробки весом только в 310 плюс-минус 7? Может такое быть в жизни? Легко.

              Я не думаю, что найдется много математиков и разработчиков, которые подпишутся под ТЗ с исходной формулировкой и не потребуют уточнений.
              • 0
                Я вовсе не настаиваю на своей правоте. Может, стоило бы более строго формулировать задачу. Но я отталкивался от формулировки первого автора (которую по ходу сначала он сам, а потом и я сам слегка поправил).

                Из своего опыта, как раз такая нечеткая формулировка типична: «Что мне делать, чтобы 90% коробок конфет соответствовали M=310±7?». А потом уже математик с заказчиком уточняют детали. Работая в консалтинге, я время от времени такие задачки решаю. Действительно, ТЗ на НИР стараюсь не подписывать, но в рамках техподдержки или обучения решаю (и с удовольствием).
  • 0
    Речь зашла о характеристических функциях. Давайте посмотрим, как они выглядят. Конфеты считаем распределенными равномерно (отсортированные, как показано во всех трех статьях). Тогда х.ф. для равномерного распределения конфет и нормального распределения коробок:


    Вот так выглядят графики действительной и мнимой части х.ф. конфет:


    Структура х.ф. — фрактальная (график зависит от масштаба):


    Звездочки — это х.ф. нормального распределения коробок.

    Последний график — модуль х.ф. распределения 1-й конфеты (синяя огибающая), суммы 12 конфет (12-я степень х.ф. конфеты — пунктир) и коробки (звездочки):



    Ради примера показана 4-я степень х.ф. конфеты (как бы коробка из 4 конфет).

    Было бы любопытно услышать комментарии от специалистов в теорвере (я не знал про фрактальные осцилляции х.ф. — не ошибся ли я?) — вопрос к всемирному разуму.
    • 0
      Интеграл для характеристической функции берущийся, он получается вида (e^{ita} — e^{itb}) / t = (cos(ta) — cos(tb)) / t + i * (sin(ta) — sin(tb)) / t. Что совсем непохоже на получающееся у вас.
      • 0
        Конечно, берущийся, только Вы в аналитическом вычислении интеграла синус с косинусом перепутали. Он и нарисован (только посчитан численно). Чтобы убедиться, нарисовал на графике:



        Ваша аналитика совпадает с моим численным методом.

        — желтое — разность синусов (аналитика)
        — красные точки — реальная часть разности экспонент (аналитика)
        — зеленый пунктир — численное интегрирование (то же самое, что на всех моих графиках выше, они все правильные)
        • 0
          Не обратил внимания на масштаб( Да, разность синусов с разными коэффициентами аргумента так и выглядит (где-то одинаковая фаза, где-то разная).

          (я не синус с косинусом перепутал, я мнимую единицу вместе с (a-b) в знаменателе потерял)
  • 0
    А принцип максимума энтропии тут никак не применим? Известны параметры всей коробки конфет, нужно определить параметры её составляющих.
  • 0
    Функция распределения центрированной, нормированной суммы 12 независимых, одинаково распределенных, равномерно распределенных случайных величин уклоняется от N(0,1) не более чем на 0,005. Мне кажется, что для фабрики конфет такое приближение вполне достаточно.
    • 0
      Именно это я хотел тут донести. Числовое решение, фактически, было получено в двух предыдущих статьях.

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

Самое читаемое Разработка