OberonCore https://forum.oberoncore.ru/ |
|
Хэш 63% - что это за закон природы такой? https://forum.oberoncore.ru/viewtopic.php?f=27&t=3554 |
Страница 5 из 6 |
Автор: | albobin [ Четверг, 01 Сентябрь, 2011 10:30 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Trurl писал(а): albobin писал(а): Рассмотрим ситуацию. событие A: негенерация числа A за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа B. событие B: негенерация числа B за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа А. Отсюда и отсутствие независимости. из A может следовать 'не B' и наоборот. А давайте упростим. событие A: генерация числа A за 1 попыткe, означает негенерацию любого из остальных, в том числе и числа B. событие B: генерация числа B за 1 попыткe, означает негенерацию любого из остальных, в том числе и числа A. Однако A и B независимы, в чём легко убедиться: P(A|B)=P(AB)/P(B), поскольку P(A|B)=0,P(AB)=0. Может быть я некорректно использую слова "независимость" и пр. Но если A и B независимы то вероятность AB равна произведению вероятностей. То есть в нашем случае N чисел вероятность того что в 1 попытке будут два числа A и B равна (1/N)^2 Чудеса оказываются вполне вероятны P(A|B)#P(A), P(B|A)# P(B) (независимости нет) P(A|B)=P(A), P(B|A)=P(B) (независимость есть) |
Автор: | Trurl [ Четверг, 01 Сентябрь, 2011 11:07 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Да, что-то я какой-то бред написал. |
Автор: | albobin [ Четверг, 01 Сентябрь, 2011 11:10 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Пожалуй я сделаю паузу до лучших свободных минут. Сдаётся мне, что без букваря не обойдусь. |
Автор: | Trurl [ Четверг, 01 Сентябрь, 2011 15:39 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Да, распределение получается не биномиальним. Возьмем m чисел. Существует (n - m)^n вариантов, в которых ни одно из них не генерируется. А вариантов, в которых не генерируется только эти числа: (n - m)^n - (n - m)(n - m - 1)^n + C(2, n - m)(n - m - 2)^n - .... Итого, вероятность, что ровно m чисел не сгенерируется равна C(m, n)*SUM((-1)^k*C(k, n-m)*(n - m - k)^n, k= 0 ..n-m)/n^n, если я опять ничего не напутал. |
Автор: | albobin [ Четверг, 01 Сентябрь, 2011 16:38 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Trurl писал(а): Да, распределение получается не биномиальним. Возьмем m чисел. Существует (n - m)^n вариантов, в которых ни одно из них не генерируется. А вариантов, в которых не генерируется только эти числа: (n - m)^n - (n - m)(n - m - 1)^n + C(2, n - m)(n - m - 2)^n - .... Итого, вероятность, что ровно m чисел не сгенерируется равна C(m, n)*SUM((-1)^k*C(k, n-m)*(n - m - k)^n, k= 0 ..n-m)/n^n, если я опять ничего не напутал. Правильно ли понял идею? имеем к-во , где нет m чисел для каждого из (n-m) чисел отсекаем кол-во, где нет ещё и его ввиду пересечений множеств компенсируем двойное вычитание добавлением, и это для каждой пары из (n-m) далее опять из-за двойных добавок компенсируем вычитанием кол-вом соответствующего множества для каждой тройки из (n-m) и т.д. |
Автор: | Trurl [ Четверг, 01 Сентябрь, 2011 16:49 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
albobin писал(а): Правильно ли понял идею? Правильно. Щас ещё одна идея появилась. |
Автор: | Info21 [ Четверг, 01 Сентябрь, 2011 16:58 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Сергей Губанов писал(а): ... Сформулирую "достижение мысли" этой ветки форума. Эффективность (для построения хэштаблицы) идеальной хэшфункции равна 1-1/e. Около этого значения очень маленькая дисперсия. Поэтому при больших N совершенно бессмысленно брать сложную хэшфункцию с эффективностью, например, 0.632, если самая простая имеет эффективность 0.631 (всего на одну тысячную меньше). ... Не могу судить с определенностью, т.к. нет сил распутывать постановку задачи, но "Поэтому" в цитате выглядит сомнительно: связываются как бэ разные вещи, no? Малость дисперсии идеальной х.ф. -- это одно, а отклонение простой от сложной (идеальной) -- это другое. |
Автор: | Сергей Губанов [ Четверг, 01 Сентябрь, 2011 18:58 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Я рассуждаю так: 1) Малость дисперсии не у хэшфункции, а у распределения количества разных случайных чисел. 2) Для случайных чисел не важно с помощью сложной или простой хэшфункции они были получены. Поэтому всякие хэшфункции при больших N одинаково эффективны (если они вообще удовлетворяют условию хэшфункции то есть выдают равномерно "случайное" число). |
Автор: | Info21 [ Четверг, 01 Сентябрь, 2011 19:52 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Сергей Губанов писал(а): 1) Малость дисперсии не у хэшфункции, а у распределения количества разных случайных чисел. Понятно, но распределение-то есть функция хешфункции.Сергей Губанов писал(а): 2) Для случайных чисел не важно с помощью сложной или простой хэшфункции они были получены. Тогда зачем вообще об этом вспоминать. Предположили, что "случайно-равномерное распределение", и конец этому делу.Надеюсь, народ тут разобрался, что к чему... |
Автор: | albobin [ Пятница, 02 Сентябрь, 2011 07:23 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Вот на суд "землемерческое" доказательство формулы для мат ожидания Идею изложу вкраце. 1.разобъём всё множество вариантов N^N на два подмножества, в одном все те,где есть некоторая цифра(условно 1), в другом - где её нет. 2.каждое подмножество разобъём на два по признаку наличия некой другой цифры (условно 2) 3..N аналогично для цифр 3..N Теперь представим это графически в виде прямоугольника шириной N^N и высотой N область ░ - там, где нет цифры (соответствующего уровня) область █ - там, где она есть на каждом уровне общая площадь ░ равна (N-1)^N, площадь всех областей ░ равна N(N-1)^N главное - абсолютно не важны конкретные ширины заштрихованных областей и ещё - нет вертикальной области высотой N из ░ схематично изображено для N=3 для пояснения Код: 1 N^N 1 ░░░░░░░░░████████████ 2 ░░███████░░░░████████ 3 ██░░░████░░██░░░█████ получается,при рассматривании вертикалей, ░ будет определять к-во отсутствующих цифр в вариантах. мат.ожидание вычисляем, рассматривая вертикали, двигаясь по горизонтали и имеем: мат ожидание есть отношение площади всех областей ░ к N^N, M=N(N-1)^N/N^N= N(1-1/N)^N а отношение мат.ожидания к N, M/N=(1-1/N)^N Спасибо Trurl , идея появилась после чтения http://forum.oberoncore.ru/viewtopic.php?f=27&t=3554&start=80#p65190 PS. Поправил текст немного. Если кого смущает, а зачем нужна это ерунда с разбивкой на части, то отвечу - незачем, просто для того, что бы картинка была более конкретной (этакое упорядочивание применено) Ну и для полноты уж переведу на более "пацанский" язык. Всем возможным последовательностям случайных чисел(1..N) длины N присвоим номера от 1 до N^N, и обозначим каждую как Xj, где j=1..N^N Построим матрицу размерности N (вертикаль) на N^N (горизонталь) из элементов Aij, i=1..N, j=1..N^N Aij=1 , если число i не присутствует в Xj Aij=0 , если число i присутствует в Xj для любого i сумма всех Aij, где j=1..N^N ( по горизонтали) равна (N-1)^N (кол-во всех Xj образованных без числа i) сумма всех Aij по всей матрице S= N(N-1)^N обозачим как Sj сумму всех Aij, где i=1..N (сумма по вертикали), т.е. Sj=кол-ву отсутствующих чисел из диапазона 1..N в последовательности Xj мат.ожидание M (то что нас интересует в рассматриваемом эксперименте) будет равно сумме всех Sj/N^N, где j=1..N^N вынося 1/N^N за скобки и суммируя все Sj получим M=S/N^N=N(N-1)^N/N^N=N(1-1/N)^N а отношение M/N=(1-1/N)^N |
Автор: | Trurl [ Пятница, 02 Сентябрь, 2011 07:57 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Вот еще формула. p(k,m) - вероятность того, что после k проб негенерированных будет m. p(k+1,m)=p(k,m)*(n-m)/n + p(k,m+1)*(m+1)/n (P[стало m]=P[было m]*P[m не изменилось]+P[было m+1]*P[m уменьшилось]). Только развернуть красиво не получается. |
Автор: | albobin [ Пятница, 02 Сентябрь, 2011 08:22 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Trurl писал(а): Вот еще формула. p(k,m) - вероятность того, что после k проб негенерированных будет m. p(k+1,m)=p(k,m)*(n-m)/n + p(k,m+1)*(m+1)/n (P[стало m]=P[было m]*P[m не изменилось]+P[было m+1]*P[m уменьшилось]). Только развернуть красиво не получается. Может быть помог бы направленный граф с весами переходов (вероятность). Тут был у меня вариант. N узлов отражает кол-во несгенерированных обозначены как N-1, N-2, ... 2, 1,0 переход (N-j) -> (N-j) вес = j/N переход (N-j) -> (N-j-1) вес = (N-j)/N в итого надо сделать N-1 шаг по графу начиная с узла (N-1) для наглядности удобно развернуть в виде сетки, двигаться по которой можно либо вправо, т.е (N-j)->(N-j) либо вниз (N-j) ->(N-j-1) ограничена сетка диагональю (N-1 шагов) но там тоже комбинаторика ( утомительно) |
Автор: | Info21 [ Пятница, 02 Сентябрь, 2011 10:26 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
albobin писал(а): но там тоже комбинаторика ( утомительно) Гы...(Где-то наш знаток Галков...) |
Автор: | albobin [ Пятница, 02 Сентябрь, 2011 10:42 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Info21 писал(а): albobin писал(а): но там тоже комбинаторика ( утомительно) Гы...Вполне допускаю, что там можно применить какой-то другой мат.аппарат, но он мне не известен Уместнее было бы сказать: "но там мне видится только комбинаторика (утомительно)" |
Автор: | Info21 [ Пятница, 02 Сентябрь, 2011 11:23 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
albobin писал(а): Info21 писал(а): albobin писал(а): но там тоже комбинаторика ( утомительно) Гы... |
Автор: | Сергей Губанов [ Пятница, 02 Сентябрь, 2011 12:01 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
albobin писал(а): переход (N-j) -> (N-j) вес = j/N Баян.переход (N-j) -> (N-j-1) вес = (N-j)/N viewtopic.php?p=65010#p65010 viewtopic.php?p=65012#p65012 viewtopic.php?p=65013#p65013 |
Автор: | albobin [ Пятница, 02 Сентябрь, 2011 12:25 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Сергей Губанов писал(а): albobin писал(а): переход (N-j) -> (N-j) вес = j/N Баян.переход (N-j) -> (N-j-1) вес = (N-j)/N viewtopic.php?p=65010#p65010 viewtopic.php?p=65012#p65012 viewtopic.php?p=65013#p65013 Не пытаюсь завладевать приоритетом. Но и сказать, что формулки срисованы, не могу. "Было у меня" означает рисовалось давече на бумаге, но было отброшено. Сорри, если ненароком нарушил "чайные церемонии" |
Автор: | Info21 [ Пятница, 02 Сентябрь, 2011 15:38 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Сергей Губанов писал(а): Баян. А где ясно сформулирована исходная проблема? Просьба первый пост не предлагать
|
Автор: | Trurl [ Пятница, 02 Сентябрь, 2011 15:50 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Да какая проблема? Здесь просто беседы о вероятности. |
Автор: | albobin [ Пятница, 02 Сентябрь, 2011 15:59 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Trurl писал(а): Да какая проблема? Здесь просто беседы о вероятности. А как же формула для мат.ожидания в обсуждаемом "эксперименте" Меня лично интересовало как получить (или обосновать интуитивно понятную) формулу для мат.ожидания в неком "'эксперименте" Не претендуя на ясность, из начала сообщения можно понять о каком http://forum.oberoncore.ru/viewtopic.php?f=27&t=3554&start=40#p65126 Но всё равно, первое сообщение С.Губанова это основное, там главное "почему?" |
Страница 5 из 6 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |