19 октября 2014 в 19:06

Закон Бенфорда и распределения под него попадающие


В теории вероятностей и статистике правило первой цифры, или закон Бенфорда, показывает любопытное проявления частот первой цифры данных из реальной жизни. Для школьников и домохозяек этот закон можно вольно сформулировать так: есть наборы данных, у которых первая цифра будет единицей примерно в 6 раз чаще, чем девятка и это соотношение не изменится при масштабировании исходного набора. Более строго можно сформулировать так: набор чисел удовлетворяет закону Бенфорда, если первая цифра d появляется с вероятностью


Здесь N – основание системы счисления, должно быть больше 2, далее будем рассматривать 10.
Для строгих математиков это правило формулируется так: существуют такие случайные величины, для которых распределение вероятностей дробной части логарифма по любому основанию большему 1 сходится к равномерному на отрезке [0; 1] распределению. Далее я постараюсь писать как можно популярнее и подробнее, укажу примеры, ограничения, применение и случайные величины, для которых закон применим.

Начнем с классического примера. Рассмотрим список стран по населению, например, с википедии . Получим таблицу частот для первой цифры, это можно сделать прямо открыв консоль в википедии:
var populationList = $('table.sortable tr').map(function () {return $('td:nth-child(3)', this).text()}).toArray();
var frequency = [undefined, 0, 0, 0, 0, 0, 0, 0, 0, 0];
var countriesCount = populationList.length;
$(populationList).each(function () { frequency[this[0]] += 1 / countriesCount });

Теперь можно сопоставить получившиеся частоты, с частотами закона Бенфорда, рассчитанных по формуле (1):



Посмотреть и поиграться, подставляя свои данные можно здесь jsfiddle.net/Vr3F9.
Далее рассмотрим еще несколько данных из реальной жизни: население городов России, список стран по количеству заключённых и рейтинг пользователей с сайта dev.by dev.by/users.
Здесь я приведу только результаты, как их получить, вы уже знаете. Откройте, пожалуйста, и не закрывайте диаграмму jsfiddle.net/rWbBs, я ее сейчас объясню. На изображении видно, что все распределения имеют много общего с законом Бенфорда, и только список стран по количеству заключенных имеет некоторые несоответствия с законом, но все равно похож на него больше, чем, скажем, на равномерный закон распределения. В данных из реальной жизни именно так и случается, что помимо распределений, хорошо соответствующих закону, есть такие, которые остаются «похожими» на него, даже при достаточно большом увеличении числа наблюдений, про математическую часть этого вопроса еще будет сказано, пока просто запомните как факт.

Теперь зададимся вопросом, какие наблюдаемые значения из реальной жизни удовлетворяют закону Бенфорда. Вот список некоторых из них.
1. Население стран и городов. Как следствие: результаты демографических измерений, результаты выборов, региональные показатели, пропорциональные населению.
2. Площади бассейнов рек, площади стран и территорий, размеры островов.
3. Тиражи газет и книг.
4. Повседневные расходы. Просто посмотрите на все свои покупки за какой-то период времени.
5. Показатели изменений на финансовых рынках (отдельная большая тема, уверен что, кто-то из вас знает ее лучше меня).

Теперь самое время рассказать про законы, не попадающие под закон Бенфорда. Под этот закон не попадают сильно популярные равномерные и нормальные распределения. Также попадаются распределения с часто встречаемой первой единицей и на первый взгляд, похожих на закон Бенфорда, например атомная масса элементов и основные физические константы. Про атомную массу элементов хочется сказать особенно. Сам Бенфорд в оригинальной статье, изображение заголовка которой я сделал КДПВ , указывал атомную массу, как пример закона удовлетворяющего «правилу первой цифры», однако закону, описываемому формулой (1) это распределение не удовлетворяет, хоть и видно явное преобладание первой единицы. И вот как легко в этом убедиться: достаточно умножить все значения на какое-нибудь одинаковое число, и посмотреть, что будет.



Закон Бенфорда масштабируем: при умножении всех наблюдаемых значений на одно и то же число, он продолжает выполняться, с атомной массой видно, что это не так.

Перейдем к математическим объектам, удовлетворяющих закону. Вот небольшой список:
1. Последовательность степеней двойки, и любая другая экспоненциальная последовательность.
2. Числа Фибоначчи.
3. Факториалы.
Также есть два распределения из курса Теории вероятностей, подчиняемых данному закону. Первое это гамма-распределение, при k→0 это распределение подчиняется закону (см ссылку на статью mi.mathnet.ru/tvp113). Я не встречал случаев, чтобы на практике приходилось работать с этим распределением со столь малым параметром.
А вот второй класс распределений интереснее. Оказывается, что к закону Бенфорда сходятся односторонние устойчивые распределения (ссылка на статью: mi.mathnet.ru/tvp244). Про устойчивые распределения я писал в своей предыдущей статье. Напомню кратко, что это такое. Здесь, возможно, будет немного сложно, можете сразу читать следующий абзац, основную мысль вы не потеряете. Есть класс распределений, удовлетворяющий обобщенной центральной предельной теореме, то есть эти распределения с точностью до масштаба и сдвига сохраняют свой вид при суммировании. Вот именно это свойство сохранять вид функции распределения и называется устойчивостью. Этих распределений целый класс, описываемый четырьмя параметрами, два из которых это сдвиг и масштаб как в нормальном распределении, третий параметр асимметрии, а четвертый самый важный параметр альфа, принимающий значения от нуля до двух характеризует, степень «тяжести хвоста» распределения. При альфа равном двум устойчивое распределение будет нормальным, это частный, и даже можно сказать вырожденный случай, так как только в этом случае распределение будет иметь моменты любого порядка, во всех остальных случаях моменты будут только порядка меньше альфы. То есть, дисперсия будет бесконечна, ну статистически ее можно посчитать и получить какое-то значение, но оно для разных выборок из одного и того же распределения будет принимать сильно разные значения. А при альфа меньшем, или равном единице, не будет и математического ожидания. То есть наши рассуждения «в среднем» для этого случая просто бессмысленны. И вот как раз для случая очень маленьких альф и в случае односторонности (принимают только положительные или отрицательные значения, этого можно добиться при правильном выборе параметра асимметрии), эти распределения и удовлетворяют закону Бенфорда.

Что общего можно сказать про односторонние устойчивые распределения с малым параметром хвоста, удовлетворяющих закону Бенфорда: они все не имеют среднего значения и одновершинные, статистически это можно объяснить так: существует небольшой по сравнению с разницей максимального и минимального значения, где будет находиться большинство значений. Чем больше мы проводим наблюдений, тем больше вероятность получить еще более аномальное значение. Так вот с примером про список стран по количеству заключенных: там просто параметр альфа не так сильно устремлен к нулю, а значит будет просто похожесть на закон Бенфорда, а не строгое ему соответствие, даже при весьма значительном увеличении числа наблюдений. Теперь можете закрыть этот пример, скоро вас ожидает более интересный.

Сейчас попробую пояснить, что распределений, не имеющих среднее значение в реальной жизни, гораздо больше, чем может показаться. Представьте, что вы гуляете с маленьким ребенком, возможно даже своим, по лесу. И он показывает на сосну и спрашивает: «а это дерево высокое?». Ответ на этот вопрос прост: если оно выше среднего, значит высокое, а если не совсем, то не совсем. Среднюю высоту сосны можно узнать. А вот дальше, этот же самый ребенок показывает вам камень и спрашивает: «а этот камень большой?». Теперь согласитесь, размер среднего камня для каждого человека будет свой и вероятность наткнуться на камень размером на порядки больше привычного не так уж мала.

А вот теперь более наш пример такого распределения. Размер файла на носителе. Попробуйте сходу ответить на вопрос, какой средний размер файла на вашем системном диске? Догадались? Зайдите в какую-нибудь папку, желательно имеющую побольше файлов и на системном диске, а не там, где собраны однотипные вещи вроде фоток и музыки. Теперь выведите список всех файлов и посмотрите, какая часть размеров из них начинается с единицы, двойки и так далее. Готов спорить, что девятка будет гораздо реже двойки (просто я уже много где успел проверить и даже убедился в устойчивости этого распределения). Такая же ситуация будет и с размером таблиц и числом записей в таблице в базе данных. Устойчивость и как следствие «тяжелый хвост» в этом случае означает, что две-три самые большие таблицы в базе данных будут занимать больше места, чем все остальные вместе.

Основное применение закона Бенфорда: определение возможной фальсификации входящих значений в случаях, когда значения должны удовлетворять этому закону: в сетях передачи данных, с системах хранения данных, при проведении социологических опросов и выборов, некоторых научных экспериментах и так далее. Также закон Бенфорда чем-то похож и даже связан с принципом Парето и законом Ципфа, но это уже отдельные темы, так что будет продолжение…
Александр Черноокий @paunch
карма
43,7
рейтинг 0,0
Самое читаемое Разработка

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

  • –6
    Что-то это похоже на какой-то трюк.

    Скажем, как меняется «Закон Бедфорда», если перевести всё в двоичную систему счисления?

    Ну и «Закон Ципфа» — это тоже скорее некий курьёзный факт, нежели закон природы.
    • +8
      Приведенные ссылки на статьи за авторством академика Прохорова, ученика Колмогорова, поверьте, он бы трюкачества в математике не допустил бы.
      Можно глянуть еще популярную статью академика Арнольда, у него подход другой, не через теорию вероятностей.
      • +2
        Слушайте, я не говорю, что этот трюк неверен.

        Но объяснение также очень интересно. У Арнольда (спасибо вам за статью) разобрано несколько примеров, очень любопытных.
    • +12
      Никак не меняется. Подставив двойку вместо N в формулу в начале статьи, получаем P(1)=log2(1+1/1)=1.
      Внезапно, любое двоичное число действительно начинается с единицы.
      • –2
        Почему вы так легко избавляетесь от «trailing zeroes»?

        И потом, как у Арнольда, так и в Википедии, иллюстрируется, что «Закон Бенфорда» — явление скорее социальное, нежели математическое. Иными словами, если записывать статистику экспоненциально растущих (или падающих) величин, то одинаковое расстояние действительно часто будет между логарифмами чисел, нежели между самими числами.
        • +5
          Я избавляюсь не от trailing zeroes, а от leading zeroes. Если от них не избавляться, то любое число будет начинаться с бесконечного числа нулей и все рассуждения станут бессмысленными. Естественно, под «первой цифрой» везде понимается первая значащая цифра.

          Скорее я бы сказал, что социальное явление состоит в том, что некоторые величины в мире действительно имеют либо одностороннее устойчивое распределение, либо экспоненциально растут. А уже из этого следует математическое явление — первые цифры распределены по закону Бедфорда.
        • 0
          А почему вы избавляетесь от leading zeros в случае 10-чной системы исчисления?
          • –1
            Я не избавляюсь.

            Более того, если принять, что числа фиксированной длины(с нулями добитыми до числа цифр), то закон поменяется.

            Ну, и нет, например, ничего фундаментального в том, что мы «увеличиваем разряды вместе с ростом числа» на один разряд. (до первой значащей цифры) Могли бы, например, как в какой-нибудь из реализаций длинной арифметики, увеличивать блоками по Х разрядов. Это же только конвенция.
      • –3
        Сильное утверждение, про 0 забыли.

        Любое натуральное двоичное число действительно начинается с 1.
    • 0
      (я глупость написал, del)
  • +1
    Хотел сам написать, да опередили! В свое время изучал как он работает в соц. сетях ( в частности — во «Вконтакте», на количестве подписчиков) Удивительно, но я обнаружил там удивительнейшую закономерность, если взять разность между полученным распределением и ожидаемым (log(1+ 1/n)), то можно получить такую штуковину:
    image
    Как в школьном учебнике физики, не правда ли!

    У меня было предположение, что это связано с рекламой сообществ, но если кто-нибудь объяснит мне, что это на самом деле может означать, я буду очень рад.
  • +3
    Мне не нравится, что подано под соусом «смотрите какое чудо» и нету простого объяснения, почему так, на некоторых примерах.
    Вот, скажем, с населением стран можно объяснить просто, сделав почти верное предположение, что в каждой стране население увеличивается экспоненциально со временем.
    • +2
      А простого общего объяснения может и не быть. Я привел три примера. Хорошо, страны могут расти экспоненциально. А вот с рейтингом пользователей как? Разве карма растет пропорционально текущему значению? Нет, причем она растет скачкообразно, а именно такой рост и происходит в случае процесса Леви, приросты которого суть устойчивые распределения, про которые я и пишу. Записи в базах данных могут расти экспоненциально, но это не всегда так; и даже для растущих линейно закон Бенфорда выполняется. Я просто хотел показать, что этот закон применим для распределений с тяжелыми хвостами, то есть могущим принять весьма большие заурядного значения, как в случае с камнями в статье. Вот я, например, собрался на Севан поехать. Это громадное озеро, но даже видя его я могу себе представить озеро в десятки и сотни раз больше. Не проверяя, готов спорить, что площади озер будут удовлетворять этому закону.
    • 0
      Где-то читал достаточно простое оъяснение этому закону. Звучит примерно так:

      Для примера возьмем все двузначные числа. Кол-во цифр в них распределено равномерно — каждая цифра повторятся по 10 раз на первом месте и по 10 раз на втором. Предположим что у нас есть набор всех чисел не больше 100 (обозначим его как Y), и пусть максимум m для любого числа из Y случайная величина. Минимум для Y пусть будет равен 0. Теперь представим что будет с распределением цифр в наборе Y когда m принимает разные значения:
      * m < 10 — распеделение равномерное — всех цифр поровну
      * 10 <= m < 20 — цифра 1 повторяется 12 раз, остальные фиры по 2 раза
      * 20 <= m < 30 — цифры 1, 2 повторяются по 13 раз, остальные по 3 раза
      * 30 <= m < 40 — цифры 1, 2, 3 повторяются по 14 раз, остальные по 4 раза

      Видите закономерность? С каждым новым десятком добавляем одну цифру в компанию к удинице и двойке, остальные равномерно по чуть-чуть. Заметили что 1 повторяется больше 10 раз когда m — любое число больше 10? Двойка же повторяется больше 10 раз только когда m > 20, тройка и того реже. А девятка так вообще только если m больше 90.

      Предположим что шанс для m быть любым числом от нуля до ста одинокав — то есть вроятность что m будет равен например 22 такая же как если m будет равен 74. Если мы будем возьмем множество разных наборов чисел, от 0 до некоего максимум, у каждого набора разный случайный максимум от 1 до 100, посчитаем процетное соотношение цифр в каждом наборе, а потом найдем среднее среди всех наборов, то вот тогда то увидим что единиц больше всего. Потому что в наборах где m меньше 20 но больше 9 единиц будет больше 10 штук, а остальных по чуть-чуть, а в наборах, где m например меньше 50, единиц будет все еще больше 10 (так же двоек, троек, четверок).

      Это будет работать также когда мы выберем для m любой диапазон числе от нуля.

      Коряво немножко объясняю, но звучит примерно так. Объяснение, конечно, сильно упрощенное, не учитывает того что числа могут иметь также случайный минимум вместо нуля. Так же числа берутся все, а не набор случайных числе как в реальности (хотя для набора случайных чисел распределение будет стремиться к такому же чем больше числе в наборе). Может еще есть какие другие косяки — я не профессиональный математик, могу что-то не учесть.
      • 0
        P.S (редактировать не могу). Конечно нужно было считать только певые цифры а не все, но рассуждение работает точно в таком же виде и для первых цифр.
        • +1
          да и «все» вы как-то очень криво посчитали.
      • +1
        Спасибо за развернутый комментарий. Если у вас m пробегает от 1 до 100, то в итоговом распределении будет 100 единиц, 99 двоек и ток далее до одной сотни. А это и есть, упомянутый в заключении и весьма критикуемый закон Ципфа, у него тоже преобладание единицы над девяткой но не в таком соотношении. Просто проверьте статистически файлы на своем системном диске и убедитесь, что закон Бенфорда лучше подходит.
        • 0
          100 единиц будет если просто все цифры сложить. Я же предложил найти соотношение цифр для каждого m, то есть для m=15 будет (если считать первые цифры): единиц 6/15, двоек — 1/15, троек — 1/15, и т.д. Потом для всех m найти усредненное соотношение цифр.

          А вообще объяснение скорее иллюстрирует «почему единиц больше чем других цифр», а не почему закон работает.
    • 0
      … или в качестве простых паролей часто используют год рождения (http://testingbenfordslaw.com/most-common-iphone-passcodes, но уже пошло смещение в сторону двойки).
  • 0
    После таких постов перестаешь везде замечать 42 и начинаешь замечать числа, начинающиеся на 1.
    • 0
      Сдайте свой значок и полотенце.
  • 0
    На самом деле для результатов выборов закон Бенфорда, к сожалению, не работает. На эту тему статьи написаны — к примеру: www.vote.caltech.edu/sites/default/files/benford_pdf_4b97cc5b5b.pdf
    • 0
      Ни для каких? Ни для честных, ни для липовых?
      • 0
        Ну иногда он срабатывает, но это ничего не гарантирует. Есть случаи, когда он не соблюдается на заведомо честных выборах и наоборот, выполняется на заведомо нечестных. Можно, конечно, идти дальше и предположить, что демократические цивилизованные некоррумпированные страны (типа Великобритании, где он не сработал — blog.jgc.org/2009/06/does-benfords-law-apply-to-election.html) на самом деле не столь демократичны, не столь цивилизованны и не столь некоррумпированы. Но тогда совсем непонятно, как проверять закон.
  • 0
    существуют такие случайные величины, для которых распределение вероятностей дробной части логарифма по любому основанию большему 1 сходится к равномерному на отрезке [0; 1] распределению.

    Непонятно, как этому условию могут удовлетворять примеры из реального мира, приведённые дальше — ведь мы всегда можем взять основание логарифма, которое больше квадрата населения планеты, её площади, общего количества денег… и тогда логарифмы элементов выборки не достигнут даже 1/2, не говоря уже об 1. Наверное, должны быть какие-то ограничения на «любое основание»?
    • 0
      Правильное замечание. В этом определении основание логарифма в дальнейших рассуждениях совпадает с основанием системы счисления с которой мы работаем. Здесь нет смысла усложнять и брать сильно больше 10 или 16.
    • 0
      Потому и уточняется что «существуют» а не «все». То есть елси для населения стран мира вы выберете основание логарифма в несколько раз больше населения планеты, то не сработает. Но для этого же самого основания логарифма можно найти другие случайные величнины (например массы планет в граммах, или кол-во звезд в галлактиках) для которых сработает
      • 0
        Но для этого же самого основания логарифма можно найти другие случайные величнины (например массы планет в граммах, или кол-во звезд в галлактиках) для которых сработает


        Даже если это и так, то это будет подтверждением утверждения «для любого основания, большего 1, существуют такие случайные величины, для которых распределение вероятностей дробной части логарифма по этому основанию сходится к равномерному на отрезке [0; 1] распределению» — а это совсем не то же самое.
        И неважно, в чём измерять массы планет — в граммах или в килотоннах. Если распределение дробных частей логарифма было равномерным в одном случае, оно останется равномерным и в другом (если основания одинаковы). Потому что значения логарифмов одной и той же массы в разных единицах измерения будут отличаться на константу.
        • 0
          Упс, моя ошибка. Не до конца понял к чему претензия. Все верно, всегда можно выбрать основание да побольше
  • +1
    Кстати, для степеней двойки и чисел Фибоначчи утверждение про «логарифм по любому основанию» тоже неверно. По основанию 16 степени двойки будут начинаться только с 1,2,4,8 — ни о какой равномерности речи не идёт. Дробная часть логарифма числа Фибоначчи по основанию phi=(1+sqrt(5))/2 стремится к log((3*sqrt(5)+5)/10)/log(phi)=0.327724… Наверное, следовало бы написать «по почти любому основанию» (т.е. за исключением множества меры 0) — может быть, тогда бы оно стало правильнее.
    • 0
      Да, весьма верное замечание. Я напутал, добавляя математические целочисленные объекты к статистическим, или показывая строгое определение. Но вот для устойчивых распределений с малым альфа это будет работать всегда. Здесь статистический подход: делал наблюдения в предположении, что они имеют непрерывное распределение. Вот у меня там такая строчка была:
      Здесь N – основание системы счисления, должно быть больше 2, далее будем рассматривать 10.

      Предлагаю дальше исходить из нее.
  • 0
    Исходники Qt 5.3 (только .h/.cpp):

    0: 8
    1: 5069
    2: 7919
    3: 4852
    4: 2968
    5: 2498
    6: 2353
    7: 1612
    8: 1044
    9: 687

    2 популярнее.
  • 0
    Big Data?

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