Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 34
Что-то это похоже на какой-то трюк.
Скажем, как меняется «Закон Бедфорда», если перевести всё в двоичную систему счисления?
Ну и «Закон Ципфа» — это тоже скорее некий курьёзный факт, нежели закон природы.
Скажем, как меняется «Закон Бедфорда», если перевести всё в двоичную систему счисления?
Ну и «Закон Ципфа» — это тоже скорее некий курьёзный факт, нежели закон природы.
Никак не меняется. Подставив двойку вместо N в формулу в начале статьи, получаем P(1)=log2(1+1/1)=1.
Внезапно, любое двоичное число действительно начинается с единицы.
Внезапно, любое двоичное число действительно начинается с единицы.
Почему вы так легко избавляетесь от «trailing zeroes»?
И потом, как у Арнольда, так и в Википедии, иллюстрируется, что «Закон Бенфорда» — явление скорее социальное, нежели математическое. Иными словами, если записывать статистику экспоненциально растущих (или падающих) величин, то одинаковое расстояние действительно часто будет между логарифмами чисел, нежели между самими числами.
И потом, как у Арнольда, так и в Википедии, иллюстрируется, что «Закон Бенфорда» — явление скорее социальное, нежели математическое. Иными словами, если записывать статистику экспоненциально растущих (или падающих) величин, то одинаковое расстояние действительно часто будет между логарифмами чисел, нежели между самими числами.
Я избавляюсь не от trailing zeroes, а от leading zeroes. Если от них не избавляться, то любое число будет начинаться с бесконечного числа нулей и все рассуждения станут бессмысленными. Естественно, под «первой цифрой» везде понимается первая значащая цифра.
Скорее я бы сказал, что социальное явление состоит в том, что некоторые величины в мире действительно имеют либо одностороннее устойчивое распределение, либо экспоненциально растут. А уже из этого следует математическое явление — первые цифры распределены по закону Бедфорда.
Скорее я бы сказал, что социальное явление состоит в том, что некоторые величины в мире действительно имеют либо одностороннее устойчивое распределение, либо экспоненциально растут. А уже из этого следует математическое явление — первые цифры распределены по закону Бедфорда.
А почему вы избавляетесь от leading zeros в случае 10-чной системы исчисления?
Я не избавляюсь.
Более того, если принять, что числа фиксированной длины(с нулями добитыми до числа цифр), то закон поменяется.
Ну, и нет, например, ничего фундаментального в том, что мы «увеличиваем разряды вместе с ростом числа» на один разряд. (до первой значащей цифры) Могли бы, например, как в какой-нибудь из реализаций длинной арифметики, увеличивать блоками по Х разрядов. Это же только конвенция.
Более того, если принять, что числа фиксированной длины(с нулями добитыми до числа цифр), то закон поменяется.
Ну, и нет, например, ничего фундаментального в том, что мы «увеличиваем разряды вместе с ростом числа» на один разряд. (до первой значащей цифры) Могли бы, например, как в какой-нибудь из реализаций длинной арифметики, увеличивать блоками по Х разрядов. Это же только конвенция.
Сильное утверждение, про 0 забыли.
Любое натуральное двоичное число действительно начинается с 1.
Любое натуральное двоичное число действительно начинается с 1.
(я глупость написал, del)
Хотел сам написать, да опередили! В свое время изучал как он работает в соц. сетях ( в частности — во «Вконтакте», на количестве подписчиков) Удивительно, но я обнаружил там удивительнейшую закономерность, если взять разность между полученным распределением и ожидаемым (log(1+ 1/n)), то можно получить такую штуковину:
Как в школьном учебнике физики, не правда ли!
У меня было предположение, что это связано с рекламой сообществ, но если кто-нибудь объяснит мне, что это на самом деле может означать, я буду очень рад.
Как в школьном учебнике физики, не правда ли!
У меня было предположение, что это связано с рекламой сообществ, но если кто-нибудь объяснит мне, что это на самом деле может означать, я буду очень рад.
Мне не нравится, что подано под соусом «смотрите какое чудо» и нету простого объяснения, почему так, на некоторых примерах.
Вот, скажем, с населением стран можно объяснить просто, сделав почти верное предположение, что в каждой стране население увеличивается экспоненциально со временем.
Вот, скажем, с населением стран можно объяснить просто, сделав почти верное предположение, что в каждой стране население увеличивается экспоненциально со временем.
А простого общего объяснения может и не быть. Я привел три примера. Хорошо, страны могут расти экспоненциально. А вот с рейтингом пользователей как? Разве карма растет пропорционально текущему значению? Нет, причем она растет скачкообразно, а именно такой рост и происходит в случае процесса Леви, приросты которого суть устойчивые распределения, про которые я и пишу. Записи в базах данных могут расти экспоненциально, но это не всегда так; и даже для растущих линейно закон Бенфорда выполняется. Я просто хотел показать, что этот закон применим для распределений с тяжелыми хвостами, то есть могущим принять весьма большие заурядного значения, как в случае с камнями в статье. Вот я, например, собрался на Севан поехать. Это громадное озеро, но даже видя его я могу себе представить озеро в десятки и сотни раз больше. Не проверяя, готов спорить, что площади озер будут удовлетворять этому закону.
Где-то читал достаточно простое оъяснение этому закону. Звучит примерно так:
Для примера возьмем все двузначные числа. Кол-во цифр в них распределено равномерно — каждая цифра повторятся по 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 любой диапазон числе от нуля.
Коряво немножко объясняю, но звучит примерно так. Объяснение, конечно, сильно упрощенное, не учитывает того что числа могут иметь также случайный минимум вместо нуля. Так же числа берутся все, а не набор случайных числе как в реальности (хотя для набора случайных чисел распределение будет стремиться к такому же чем больше числе в наборе). Может еще есть какие другие косяки — я не профессиональный математик, могу что-то не учесть.
Для примера возьмем все двузначные числа. Кол-во цифр в них распределено равномерно — каждая цифра повторятся по 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 любой диапазон числе от нуля.
Коряво немножко объясняю, но звучит примерно так. Объяснение, конечно, сильно упрощенное, не учитывает того что числа могут иметь также случайный минимум вместо нуля. Так же числа берутся все, а не набор случайных числе как в реальности (хотя для набора случайных чисел распределение будет стремиться к такому же чем больше числе в наборе). Может еще есть какие другие косяки — я не профессиональный математик, могу что-то не учесть.
P.S (редактировать не могу). Конечно нужно было считать только певые цифры а не все, но рассуждение работает точно в таком же виде и для первых цифр.
Спасибо за развернутый комментарий. Если у вас m пробегает от 1 до 100, то в итоговом распределении будет 100 единиц, 99 двоек и ток далее до одной сотни. А это и есть, упомянутый в заключении и весьма критикуемый закон Ципфа, у него тоже преобладание единицы над девяткой но не в таком соотношении. Просто проверьте статистически файлы на своем системном диске и убедитесь, что закон Бенфорда лучше подходит.
100 единиц будет если просто все цифры сложить. Я же предложил найти соотношение цифр для каждого m, то есть для m=15 будет (если считать первые цифры): единиц 6/15, двоек — 1/15, троек — 1/15, и т.д. Потом для всех m найти усредненное соотношение цифр.
А вообще объяснение скорее иллюстрирует «почему единиц больше чем других цифр», а не почему закон работает.
А вообще объяснение скорее иллюстрирует «почему единиц больше чем других цифр», а не почему закон работает.
… или в качестве простых паролей часто используют год рождения (http://testingbenfordslaw.com/most-common-iphone-passcodes, но уже пошло смещение в сторону двойки).
На самом деле для результатов выборов закон Бенфорда, к сожалению, не работает. На эту тему статьи написаны — к примеру: www.vote.caltech.edu/sites/default/files/benford_pdf_4b97cc5b5b.pdf
Ни для каких? Ни для честных, ни для липовых?
Ну иногда он срабатывает, но это ничего не гарантирует. Есть случаи, когда он не соблюдается на заведомо честных выборах и наоборот, выполняется на заведомо нечестных. Можно, конечно, идти дальше и предположить, что демократические цивилизованные некоррумпированные страны (типа Великобритании, где он не сработал — blog.jgc.org/2009/06/does-benfords-law-apply-to-election.html) на самом деле не столь демократичны, не столь цивилизованны и не столь некоррумпированы. Но тогда совсем непонятно, как проверять закон.
существуют такие случайные величины, для которых распределение вероятностей дробной части логарифма по любому основанию большему 1 сходится к равномерному на отрезке [0; 1] распределению.
Непонятно, как этому условию могут удовлетворять примеры из реального мира, приведённые дальше — ведь мы всегда можем взять основание логарифма, которое больше квадрата населения планеты, её площади, общего количества денег… и тогда логарифмы элементов выборки не достигнут даже 1/2, не говоря уже об 1. Наверное, должны быть какие-то ограничения на «любое основание»?
Правильное замечание. В этом определении основание логарифма в дальнейших рассуждениях совпадает с основанием системы счисления с которой мы работаем. Здесь нет смысла усложнять и брать сильно больше 10 или 16.
Потому и уточняется что «существуют» а не «все». То есть елси для населения стран мира вы выберете основание логарифма в несколько раз больше населения планеты, то не сработает. Но для этого же самого основания логарифма можно найти другие случайные величнины (например массы планет в граммах, или кол-во звезд в галлактиках) для которых сработает
Но для этого же самого основания логарифма можно найти другие случайные величнины (например массы планет в граммах, или кол-во звезд в галлактиках) для которых сработает
Даже если это и так, то это будет подтверждением утверждения «для любого основания, большего 1, существуют такие случайные величины, для которых распределение вероятностей дробной части логарифма по этому основанию сходится к равномерному на отрезке [0; 1] распределению» — а это совсем не то же самое.
И неважно, в чём измерять массы планет — в граммах или в килотоннах. Если распределение дробных частей логарифма было равномерным в одном случае, оно останется равномерным и в другом (если основания одинаковы). Потому что значения логарифмов одной и той же массы в разных единицах измерения будут отличаться на константу.
Кстати, для степеней двойки и чисел Фибоначчи утверждение про «логарифм по любому основанию» тоже неверно. По основанию 16 степени двойки будут начинаться только с 1,2,4,8 — ни о какой равномерности речи не идёт. Дробная часть логарифма числа Фибоначчи по основанию phi=(1+sqrt(5))/2 стремится к log((3*sqrt(5)+5)/10)/log(phi)=0.327724… Наверное, следовало бы написать «по почти любому основанию» (т.е. за исключением множества меры 0) — может быть, тогда бы оно стало правильнее.
Да, весьма верное замечание. Я напутал, добавляя математические целочисленные объекты к статистическим, или показывая строгое определение. Но вот для устойчивых распределений с малым альфа это будет работать всегда. Здесь статистический подход: делал наблюдения в предположении, что они имеют непрерывное распределение. Вот у меня там такая строчка была:
Предлагаю дальше исходить из нее.
Здесь N – основание системы счисления, должно быть больше 2, далее будем рассматривать 10.
Предлагаю дальше исходить из нее.
Исходники 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: 8
1: 5069
2: 7919
3: 4852
4: 2968
5: 2498
6: 2353
7: 1612
8: 1044
9: 687
2 популярнее.
Big Data?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Закон Бенфорда и распределения под него попадающие