|
В памяти есть $%n$% ячеек. $%k$% из них заполнено. При вставке ключа производится последовательный просмотр ячеек (пробы) до тех пор, пока не найдется свободное место. Надо выразить математическое ожидание числа проб, требующихся при вставке $%k+1$%-го ключа. задан 26 Окт '14 20:23 
nowereman |
|
По формуле математического ожидания оно равно $$E_{k+1}=\sum_{i=1}^{k+1}ip_i.$$ Здесь $%1\leqslant i\leqslant k+1$%, потому что мы можем вставить $%k+1$%-й ключ в свободную ячейку как с первой попытки ($%i=1$%), так и перепробовав все занятые ячейки, и на $%k+1$%-м ходе попав в свободную. Теперь как искать $%p_i$%. $%p_1$% - вероятность вставить ключ с первой попытки в свободную ячейку. Считается по формуле классической вероятности $%n$% - общее число исходов, $%n-k$% - число благоприятных исходов(т.е. свободных ячеек). Получаем $%p_1=\frac{n-k}{n}$%. Далее $%p_2$% - вероятность того, что ключ вставлен со второй попытки. То есть первая попытка неудачная (ее вероятность $%\frac{k}{n}$%), вторая - удачная (ее вероятность - это условная вероятность - $%\frac{n-k}{n-1}$%; здесь в знаменателе $%n-1$%, т.к. при первой попытке мы "израсходовали" одну ячейку и их осталась $%n-1$%). В итоге $%p_2=\frac{k}{n}\cdot\frac{n-k}{n-1}$%. Аналогично для $%i\leqslant k+1$% мы получаем $%p_i=\frac{k}{n}\cdot\frac{k-1}{n-1}\cdot\frac{k-i+2}{n-i+2}\cdot\frac{n-k}{n-i+1}$%. Здесь дробь $%\frac{k-1}{n-1}$% возникает из тех соображений, что после первого шага мы израсходовали одну ячейку, причем занятую, поэтому на следующем шаге число ячеек и число занятых ячеек уменьшается на 1. Последняя дробь $%\frac{n-k}{n-i+1}$% такая, потому что у нас осталось $%n-i+1$% ячеек, причем свободных - как было изначально - $%n-k$%. Дополнительно заметим, что при $%i=k+1$% последняя дробь (в произведении дробей) будет равна 1. При суммировании лучше преобразовать выражение $%ip_i$% до $$ip_i=i\frac{k}{n}\cdot\ldots\cdot\frac{k-i+2}{n-i+2}-i\frac{k}{n}\cdot\ldots\cdot\frac{k-i+1}{n-i+1},$$ выделив единицу из дроби $%\frac{n-k}{n-i+1}$%. Тогда получится выражение вида $$S_n^k=1+\frac{k}{n}+\frac{k}{n}\cdot\frac{k-1}{n-1}+\ldots+\frac{k}{n}\cdot\ldots\cdot\frac{1}{n-k+1},$$ которое можно сосчитать по реккурентной формуле $%S_n^k=1+\frac{k}{n}S_{n-1}^{k-1}$%. Когда начнете раскручивать его с конца, то есть с $%S_{n-k+1}^{1}$%, то там видно, что все получается. отвечен 26 Окт '14 20:55 
cartesius Спасибо за ответ. Я пытаюсь сообразить, какими преобразованиями получить красивую дробь в конце. Вопрос не в том, как считать, а как схлопнуть огромное выражение для суммы в красивую формулу. Слова написаны для общего понимания, откуда что взялось.
(26 Окт '14 21:04)
nowereman
Ясно. Сейчас дополню про сумму.
(26 Окт '14 21:10)
cartesius
Да, там все слагаемые отражают, что i-1 раз мы попадали на занятую ячейку, а на i-й раз попали на свободную. Только последнее слагаемое, оно же произведение дробей, отражает случай, когда мы произвели k проб и все разы попали на занятую ячейку, что в свою очередь гарантирует, что k+1-я проба будет точно удачной, так как заполнено только k ячеек. Это я понимаю, но думаю, как сделать единую дробь, а потом ее сократить. Да, большое спасибо, скорее всего, сейчас получится, проверяю.
(26 Окт '14 21:27)
nowereman
Действительно, получилось куда более приятное выражение, но пока не возьму в голову, как упрощать дальше.
(26 Окт '14 22:43)
nowereman
Я дописала идею в ответе - используйте реккурентную формулу. Я проверила - действительно, все получается.
(26 Окт '14 22:55)
cartesius
|
|
Решение уже дано, но мне захотелось предложить другой подход, при котором не требуется делать арифметических вычислений. Можно считать, что задан порядок, в котором мы проверяем ячейки, а сами они заполнены каким-то случайным образом. Скажем, мы взяли камешки с номерами от $%1$% до $%k$% и случайно разложили их по $%n$% занумерованным ячейкам. Введём случайные величины $%\xi_i$% при $%1\le i\le k$%, где $%\xi_i=1$%, если левее $%i$%-го камешка нет пустых ячеек. В противном случае полагаем $%\xi_i=0$%. Вероятность события $%\{x_i=1\}$% равна $%\frac1{n+1-k}$% по следующей причине: если рассмотреть $%i$%-й камешек и $%n-k$% пустых ячеек, то все варианты их последовательного расположения одинаково вероятны. Поэтому вероятность того, что камешек окажется первым по счёту среди этих ячеек, равна указанному числу. Это же число, очевидно, равно матожиданию данной случайной величины, то есть $%M\xi_i=\frac1{n+1-k}$%. Понятно, что если все пустые ячейки идут правее $%i$%-го камешка, то левее него их нет. Теперь заметим, что сумма случайных величин $%\xi_1+\cdots+\xi_k$% в точности равна максимальному количеству заполненных ячеек, идущих подряд, среди первых $%k$% ячеек в исходной нумерации. Матожидание её равно $%M\xi_1+\cdots+M\xi_k=\frac{k}{n+1-k}$%, и это есть среднее число неудачных попыток. Следующая попытка заведомо будет удачной, поэтому искомая величина равна $%1+\frac{k}{n+1-k}=\frac{n+1}{n+1-k}$%. отвечен 27 Окт '14 2:48 
falcao Спасибо за интерпретацию результата, с точки зрения тервера! К сожалению, никакой "+" мне моя репутация на сайте поставить пока не позволяет, в качестве второго решения отметить не получается.
(27 Окт '14 13:55)
nowereman
@nowereman: Вам спасибо за интересную задачу! Кстати, там можно даже более простое рассуждение предложить, основанное на подсчёте средних расстояний между свободными ячейками. Из общих соображений следует, что в среднем они одинаковые, откуда можно вывести ответ.
(27 Окт '14 14:04)
falcao
Спасибо, хорошо, я попробую подумать над этим. Наверное, будет полезно научиться смотреть на ситуацию с разных сторон.
(27 Окт '14 16:08)
nowereman
|
Огромное спасибо, все получилось!