OberonCore

Да, это минимальная вероятность.

Я имел в виду условия вида: "Какова вероятность того, что среди выпавших неуникальных чисел сумма чётных будет равна 50?"

Наверное, не совсем правильно, но легко поправимо. Из 1 следует, что у нас биномиальное распределение, а для него матожидание = np, т.е n*(1+1/n)^n.

Я рассуждал так.
Пусть у нас есть N чисел.
Всего комбинаций без повторений - это перестановки - равно N!
Всего комбинаций с повторениями равно N^N.
Итого отношение N!/N^N дает вероятность выпадения N чисел без повторений.
Что не так?

Формула такая же, как и приведённая Trurl-ем на 2 странице. Только описка в трактовке числа N^N.

Ага, увидел...

Сергею Губанову.
Вот наткнулся на Tiger.
http://ru.wikipedia.org/wiki/Tiger_%28% ... 8%D1%8F%29
http://ru.wikipedia.org/wiki/TTH
C ним не пробовали поэкспериментировать?

Не пробовал и не собираюсь.

Сформулирую "достижение мысли" этой ветки форума. Эффективность (для построения хэштаблицы) идеальной хэшфункции равна 1-1/e. Около этого значения очень маленькая дисперсия. Поэтому при больших N совершенно бессмысленно брать сложную хэшфункцию с эффективностью, например, 0.632, если самая простая имеет эффективность 0.631 (всего на одну тысячную меньше).

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

Нечесна .
Tiger - это не хеш-функция, а способ применения оной.

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

Слово "искусство" применительно к выбору хеш-функции, конечно, есть элемент надувания щек, но внимательность, несомненно, нужна, когда речь о специфических данных, где много сильно скоррелированных элементов (фамилии, например, где коррелируют буквы и много одинаковых суффиксов; или в той же символической алгебре, где могут коррелировать показатели степеней переменных, которыми кодируются мономы, которые и надо хешировать).
Простодушный выбор х.ф. тогда может оказаться дико неудачным -- нерандомизирующим в силу коррелированности элементов данных.

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

В сфере ИТ такой просмотр меня не особо удивил бы, -- но Кнут человек скрупулезный, может, у него где-то это все-таки упоминается?

Ага... человек поставил эксперимент (вычислительный в данном случае), получил результат и задумался, как его объяснить. Вспоминается такая история. Л.Д. Ландау (кажется) спросили, что он может сказать об учёном Н. как о физике. Ландау ответил: "Физики получают результаты, а Н. доказывает теоремы." В то же время необязательна оппозиция мышлений. Так, тот же метод проверки моделей (систем алгопроцессов) можно, пожалуй, рассматривать как эксперимент по проверке логических утверждений на математической модели системы. Т.е. математика - однако принцип физический - так сказать, "экспериментальное доказательство теорем"...

Хоть вроде бы уже всё обсуждено, но есть некоторая неудовлетворённость.
Биномиальное распределение получится, если, наверное, всё таки "свольничать" и "нужным" образом эксперимент мысленно трансформировать.

Имеем.
1. N раз генерируем число из диапазона 1..N, для каждого числа вероятность появления в одной попытке одинакова и равна 1/N, и непоявления (1-1/N)
2. Для любого из чисел 1..N вероятность события "это число ни разу за N попыток не сгенерировано" равна (1-1/N)^N
3. После N попыток имеем итог, что какое-то кол-во чисел из 1..N так и ни разу не появилось. (Хотелось бы найти мат.ожидание этого кол-ва)

Начинаем "биномиализацию"
Опираемся на изложенное в п.2 п.3, отвлекаемся от конкретных чисел и представляем, что будто бы в процессе исходного
эксперимента неявно происходит и другой, в котором в каждой из N попыток имеем некое событие,назовём его - "нет числа", c вероятностью численно равной (1-1/N)^N (см. п.2)
Получаем мат.ожидание кол-ва событий "нет числа" после N попыток N((1-1/N)^N) (бином.распред.)
Следует заметить, что в этом неявном эксперименте результат значим только после окончания (N попыток), потому как эти попытки разворачиваются как бы "ортогонально" исходному процессу (N попыток, потому что N чисел)

Наверное возможность сведения исходного эксперимента к случаю бином.распред. основана на том, что,
рассматривая числа по отдельности (п.1), имеем случай бином.распред. кол-ва появлений конкретного числа.

PS.
Книжки почитать правильней, но ответ то хочется знать без приложения усилий

А главное, оппозиция мышлений не соответствует оппозиции наук (физики<>математики).

А у Ландау от не в последнюю очередь сексуальной закомплексованности развилась манера чрезмерно выдрючиваться, отчего получались суждения экстремистского толка.

По-моему наоборот: из Кнута проще, но самому поупражняться -- правильней

Для простоты обозначим эту вероятность p.
Для любых k чисел вероятность события "за N попыток ни разу не сгенерированы эти и только эти числа" равна p^k*(1-p)^(N-k).
Всего множеств по k чисел - C(k,N). Соотсветственно вероятность события "за N попыток ни разу не сгенерированы ровно k чисел" - C(k,N)*p^k*(1-p)^(N-k).

Другими словами: "процесс" состоит в том, что мы перебираем числа от 1 до N и смотрим, не попало ли число в категорию "ни разу не сгенерированных".

"Другие слова" гораздо лучше выражают мысль.

PS.
Но опять что-то не то

Опять возражаю.
Нельзя применять перемножение вероятностей, события не независимы
Ведь в одной попытке генерится только одно значение. Определяя вероятность негенерации конкретных чисел комбинаторным способом как отношение всех возможных вариантов развития событий за N попыток к числу всех возможных (N^N) получим то, что есть комбинации для разных чисел, которые вступают в противоречие из-за ограничение на единственность значения в конкретной попытке.
Самое смешное но формула N((1-1/N)^N) для мат.ожидания интуитивно понятна, а формализьм пока не поддаётся. Хочется же быстренько, одним махом без погружения в теории

Не понял... имеется в виду, что алгоритм генерации как бы обладает данными, какие числа из интервала уже были сгенерированы?..

Язык моя - враг ...
Мысль уточнил уже.
PS.
Боюсь, уточнил всё таки не точно.
Рассмотрим ситуацию.
событие 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.