Автор Тема: Найти матожидание.  (Прочитано 95 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Эта тема содержит сообщение, помеченное как лучший ответ. Кликните здесь для перехода к этому сообщению.

Оффлайн Байт

  • Пользователь
  • Сообщений: 929
  • Поблагодарили: 674 раз(а)
    • Просмотр профиля
Найти матожидание.
« : Ноябрь 06, 2018, 08:41:50 pm »
Задача кажется не очень сложной, но у меня чего-то ступор.
Есть N целей. По ним стреляют. При каждом выстреле цель выбирается случайно. Возможна многократная стрельба по одной цели. Промахов нет. Цель считается пораженной, если в нее попали хотя бы один раз. Найти матожидание количества выстрелов до поражения всех целей.
Если задача и впрямь сложна и нет конечной математической формулы, может быть есть какая-нибудь асимптотика?
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн ARRY

  • Пользователь
  • Сообщений: 223
  • Поблагодарили: 173 раз(а)
    • Просмотр профиля
Re: Найти матожидание.
« Ответ #1 : Ноябрь 13, 2018, 11:44:09 am »
Любопытная задача. Пару дней думал над ней.
Попробуем начать с простого.
1. \( \displaystyle N=1 \). Цель одна, и поражение её первым же выстрелом - событие достоверное. Вероятность поражения \( \displaystyle P_1=1 \), и матожидание \( \displaystyle M_1=1 \)

2. \( \displaystyle N=2  \). У нас \( \displaystyle 2 \) цели. Что в этом случае значит, что процесс стрельбы закончится на \( \displaystyle n \)-м выстреле? Это означает, что первыми \( \displaystyle n-1 \) выстрелами была поражена 1-я цель, и лишь последним выстрелом - 2-я. Или наоборот, первые \( \displaystyle n-1 \) выстрелов попали во 2-ю цель, а последний - в 1-ю.
Поскольку всего возможно \( \displaystyle 2^n  \) комбинаций, то вероятность закончить процесс стрельбы по двум целям на  \( \displaystyle n \)-м выстреле (\( \displaystyle n⩾2 \)) равна \( \displaystyle P_n=\frac {2}{2^n}=2^{1-n} \).
Мне это значение сначала показалось странным, но это легко проверить по полному пространству событий, найдя сумму геометрической прогрессии. Получается \( \displaystyle \sum \limits _2^{\infty} P_n=1 \). Всё верно.
Ну, а матожидание числа выстрелов тоже легко находим дифференцированием геометрической прогрессии: \( \displaystyle \sum \limits _2^{\infty} n\cdot 2^{1-n}=3 \).
3. Перейдём к произвольным \( \displaystyle N \) целям. А вот тут я застопорился. Возникает сложное многократное суммирование. Из его дебрей я вылезти не смог. Попробовал ввести производящую функцию и использовать интегральное представление гамма-функции, но запутался ещё больше.
Ну что ж, буду думать. задача стоит того.
Скрытый текст
Хотя интуиция мне подсказывает, что я выбрал не самый простой способ решения.
[свернуть]
Весь предшествующий опыт убеждает нас в том, что природа представляет собой реализацию простейших математически мыслимых элементов................Альберт Эйнштейн
 
Сказали спасибо: Байт

Оффлайн ARRY

  • Пользователь
  • Сообщений: 223
  • Поблагодарили: 173 раз(а)
    • Просмотр профиля
Re: Найти матожидание.
« Ответ #2 : Ноябрь 13, 2018, 12:04:18 pm »
В старом учебнике Е.Вентцель по теорверу (для военных академий) нашёл схожую задачу о бомбардировке наземных целей. Там весь процесс разбивается на ряд элементарных последовательных процессов. Думаю, можно ли применить это к Вашей задаче.
Весь предшествующий опыт убеждает нас в том, что природа представляет собой реализацию простейших математически мыслимых элементов................Альберт Эйнштейн
 
Сказали спасибо: Байт

Оффлайн Байт

  • Пользователь
  • Сообщений: 929
  • Поблагодарили: 674 раз(а)
    • Просмотр профиля
Re: Найти матожидание.
« Ответ #3 : Ноябрь 13, 2018, 12:18:22 pm »
 ARRY, на другом форуме мне предложили формулу с двойной суммой и биномальными коэффициентами, основанную на методе включений-исключений. И с наскока эта формула упрощению не поддалось. Другой товарищ предложил простую асимтотику N*ln N, что вроде похоже на правду. По дороге сделав симпатичное лингвистическое открытие
Цитировать
вероятность происходит от слов вера и ять (брать).
Третий не поленился и исследовал проблему на МатКаде. M(N=120) = 644, M(N=720) = 5750, M(N=5040) = 45872, а меня интересовал именно этот ряд - факториалов. Предлагалось (в другом месте) найти методом Монте-Карло ВСЕ ПЕРЕСТАНОВКИ. Что, конечно, полный бред, и видно без всякой статистики. Но я хотел под это дело постелить немного математики.
А сюда я выложил задачу в целях оживления форума. Не все же на ноль делить! :)
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 929
  • Поблагодарили: 674 раз(а)
    • Просмотр профиля
Re: Найти матожидание.
« Ответ #4 : Ноябрь 13, 2018, 12:30:18 pm »
для военных академий)
Когда появились первые Спорт-Лото, мои дружки кинулись ко мне. "Считай, мол, наши выигрыши.!" Я покрутил так и эдак, по терверу у меня была твердая тройка, дружки отвязались. А через пару лет приходит бравый лейтенант из Академии, и предлагает за червонец (я к тому времени стал отцом, надо было семью кормить) решить задачку. Есть 49 целей. 6 настоящих, 43 - ложных. И на них напускают 6 бомберов. Найти вероятность поражения 3-х целей, 4-х, 5-ти, 6-ти. Решил сходу. И только потом дошло. Ба! Да это спорт-лото!
Я к тому, что материальная стимуляция - великое дело и двигатель прогресса :)
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн ARRY

  • Пользователь
  • Сообщений: 223
  • Поблагодарили: 173 раз(а)
    • Просмотр профиля
Re: Найти матожидание.
« Ответ #5 : Ноябрь 13, 2018, 03:02:14 pm »
на другом форуме мне предложили формулу с двойной суммой и биномальными коэффициентами. И с наскока эта формула упрощению не поддалось.
Байт
Мне кажется, я вывел Вам формулу, и довольно-таки простую. Только я сейчас убегаю на работу. Поздно вечером сегодня выложу, надо проверить.
Весь предшествующий опыт убеждает нас в том, что природа представляет собой реализацию простейших математически мыслимых элементов................Альберт Эйнштейн
 
Сказали спасибо: Байт

Помечен как лучший ответ пользователем Байт Ноябрь 14, 2018, 08:47:28 pm

Оффлайн ARRY

  • Пользователь
  • Сообщений: 223
  • Поблагодарили: 173 раз(а)
    • Просмотр профиля
Re: Найти матожидание.
« Ответ #6 : Ноябрь 14, 2018, 12:40:45 pm »
Да, можно применить идею Вентцель о разбиении случайного процесса к Вашей задаче.
Вся стрельба представляет собой дискретный случайный процесс, завершающийся при поражении последней цели.
Весь процесс можно разбить на \( \displaystyle N \) последовательных независимых процессов (этапов). Окончанием каждого такого этапа является поражение новой, ранее не поражённой цели.
Обозначим матожидание количества выстрелов на каждом этапе \( \displaystyle M_i \), где \( \displaystyle i \) - номер этапа.

Итак, на 1-м этапе новая цель поражается с вероятностью \( \displaystyle 1 \). \( \displaystyle M_1=1 \).
На 2-м этапе выстрелов может быть несколько. При каждом выстреле с вероятностью \( \displaystyle \frac {1}{N} \) поражается старая, уже поражённая цель, и с вероятностью \( \displaystyle \frac {N-1}{N} \) поражается новая, ещё не поражённая цель.
 \( \displaystyle M_2=1\cdot \frac {N-1}{N}+2\cdot \frac {1}{N}\cdot\frac {N-1}{N}+3\cdot \left (\frac {1}{N} \right )^2 \cdot \frac {N-1}{N}+4\cdot \left (\frac {1}{N} \right )^3 \cdot \frac {N-1}{N} +\ldots=\frac {N}{N-1} \)

На 3-м этапе старая цель поражается с вероятностью \( \displaystyle \frac {2}{N} \), а новая - с вероятностью \( \displaystyle \frac {N-2}{N} \)
 
\( \displaystyle M_3=1\cdot \frac {N-2}{N}+2\cdot \frac {2}{N}\cdot\frac {N-2}{N}+3\cdot \left (\frac {2}{N} \right )^2 \cdot \frac {N-2}{N}+4\cdot \left (\frac {2}{N} \right )^3 \cdot \frac {N-2}{N} +\ldots=\frac {N}{N-2} \)

И т.д...
...
На \( \displaystyle (N-1) \)-м этапе старая цель поражается с вероятностью \( \displaystyle \frac {N-2}{N} \), а новая - с вероятностью \( \displaystyle \frac {2}{N} \)

\( \displaystyle M_{N-1}=1\cdot \frac {2}{N}+2\cdot \frac {N-2}{N}\cdot \frac {2}{N}+3\cdot \left (\frac {N-2}{N} \right )^2 \cdot \frac {2}{N}+4\cdot \left (\frac {N-2}{N} \right )^3 \cdot \frac {2}{N} +\ldots=\frac {N}{2} \)

На \( \displaystyle N \)-м этапе старая цель поражается с вероятностью \( \displaystyle \frac {N-1}{N} \), а новая - с вероятностью \( \displaystyle \frac {1}{N} \)

\( \displaystyle M_N=1\cdot \frac {1}{N}+2\cdot \frac {N-1}{N}\cdot \frac {1}{N}+3\cdot \left (\frac {N-1}{N} \right )^2 \cdot \frac {1}{N}+4\cdot \left (\frac {N-1}{N} \right )^3 \cdot \frac {1}{N} +\ldots=N \)
 
Поскольку все этапы независимы, найдём суммарное матожидание количества всех выстрелов
 
\( \displaystyle M=\sum \limits _i M_i=1+\frac {N}{N-1}+\frac {N}{N-2}+\ldots +\frac {N}{2}+N=N\left (1+\frac {1}{2}+\frac {1}{3}+\ldots +\frac {1}{N-1}+\frac {1}{N} \right ) \).

В скобках - частичная сумма гармонического ряда.

Если задача и впрямь сложна и нет конечной математической формулы, может быть есть какая-нибудь асимптотика?

Формула вполне конечная, однако при больших \( \displaystyle N \) возможно её асимптотическое выражение.

Другой товарищ предложил простую асимтотику N*ln N, что вроде похоже на правду.
Этот Ваш товарищ был недалёк от истины, только надо бы добавить постоянную Эйлера-Маскерони. Ведь \( \displaystyle \sum \limits _{i=1}^N \frac {1}{i} \approx \ln {N}+\gamma \), а посему искомое матожидание \( \displaystyle M\approx N(\ln{N}+\gamma) \)
Весь предшествующий опыт убеждает нас в том, что природа представляет собой реализацию простейших математически мыслимых элементов................Альберт Эйнштейн
 
Сказали спасибо: Байт

Оффлайн Байт

  • Пользователь
  • Сообщений: 929
  • Поблагодарили: 674 раз(а)
    • Просмотр профиля
Re: Найти матожидание.
« Ответ #7 : Ноябрь 14, 2018, 12:51:13 pm »
ARRY, Огромное спасибо! И все оказалось не так уж сложно. Главное - посмотреть на задачу с правильной стороны. Но эту сторону надо еще найти...
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн ARRY

  • Пользователь
  • Сообщений: 223
  • Поблагодарили: 173 раз(а)
    • Просмотр профиля
Re: Найти матожидание.
« Ответ #8 : Ноябрь 15, 2018, 02:15:42 pm »
Байт
Вспомнилась задача из какого-то старого задачника по теорверу.
Из колоды в \( \displaystyle 52 \) карты вытягивают одну карту. Если она не пиковая дама, то её снова засовывают в колоду, тщательно перемешивают и опять вытягивают одну карту. Найти матожидание числа вытягиваний до появления вышеуказанной дамы пик.
Эта задача - полная аналогия последнего 52-го этапа стрельбы применительно к Вашей задаче. Все цели кроме одной - дамы пик, поражены. Мат ожидание количества выстрелов на этом этапе я посчитал выше. Оно равно \( \displaystyle M_{52}=52 \).
А можно эту задачу расширить до полной аналогии со всей Вашей задачей.
Из колоды в \( \displaystyle 52 \) карты вытягивают одну карту, смотрят на неё, засовывают обратно, тщательно перемешивают и опять вытягивают. Найти матожидание количества вытягиваний до появления всех \( \displaystyle 52 \) карт колоды. Это матожидание я тоже выше посчитал. Оно равно \( \displaystyle M=52\sum \limits _{i=1}^{52}\frac {1}{i}\approx 52(\ln {52}+0,577)\approx 235 \)
Похоже, что так.
Весь предшествующий опыт убеждает нас в том, что природа представляет собой реализацию простейших математически мыслимых элементов................Альберт Эйнштейн
 
Сказали спасибо: Байт