flaass: сон

сон
Почитал путь спасения, потом заснул и прочитал еще два рассказа оттуда.
Один был про Чорный Морок (или Чорный Поезд). Будто войн не бывает вовсе. Да и вправду, как это: идут-едут массы людей невесть куда, чтобы там убивать совершенно незнакомых других людей. Неправдоподобно звучит, нелогично. На самом деле, конечно, никто никуда не едет, а нападает на всех Чорный Морок, и каждый в одном из своих знакомых вдруг видит Врага, которого надо непременно Убить. И Враг этот называется Фриц, или Еврей, или например Большевик. И люди прямо на месте друг друга убивают, без всяких неудобств. Приехал Морок в Германию на Чорном Поезде, и немцы поубивали друг друга 12 миллионов. А потом он переехал в СССР, и русские поубивали друг друга 20. А потом он через Японию уехал куда-то в Тихий Океан, слава богу.
А другой рассказ был про пушкин наше все, но я его не запомнил.

По этому поводу задачка.
На N человек напал Чорный Морок. Каждый случайно и независимо выбрал себе Врага (может, и себя). Потом каждый из них по очереди - если еще жив и Враг еще жив - убивает своего Врага (вариант - с вероятностью p). Каково матожидание числа убитых?

(Добавить комментарий)

	relf@lj 2005-03-01 07:43 (ссылка)
	У меня получилось, что мат.ожиджание равно p(1+q+q^2+...+q^(N-1))=p(q^N-1)/(q-1), где q=1-1/N. (Ответить) (Ветвь дискуссии)

	flaass@lj 2005-03-01 08:17 (ссылка)
	Вроде бы, это ответ для "ковбойской" версии, когда каждый выбирает себе наугад цель, а потом все разом стреляют. А когда по очереди, там возникают проблемы. (Ответить) (Уровень выше) (Ветвь дискуссии)

	relf@lj 2005-03-01 08:27 (ссылка)
	По-моему, это как раз для "по очереди". А для "ковбойской" версии будет просто pN. (Ответить) (Уровень выше) (Ветвь дискуссии)

relf@lj
2005-03-01 08:37 (ссылка)

Хотя, нет. Для "по очереди" я не учел условия "если еще жив".

Если через m_k обозначит мат.ожидание числа убитых на k-м шаге, то получается рекуррентность
m_0=0, m_{k+1} = m_k + p (n-m_k)/n)^2,
которая сходу не сворачивается. Ответом будет m_N.

(Ответить) (Уровень выше) (Ветвь дискуссии)

flaass@lj
2005-03-01 13:23 (ссылка)

Не работает. Потому что (к+1)-й уже может быть убит к тому времени, с неизвестной вероятностью.
Кстати, и для ковбойской версии ответ другой: число выживших равно
N*(1-p/N)^N, что примерно N*exp(-p).

(Ответить) (Уровень выше) (Ветвь дискуссии)

relf@lj
2005-03-01 17:32 (ссылка)

Почему не работает? (k+1)-й будет убит с вероятностью m_k/N, его жертва - с той же вероятностью. Поэтому вероятность того, что оба они живы равна ((N-m_k)/N)^2, хотя надо отдельно рассмотреть случай когда стрелок и жертва один и тот же человек. Тогда вероятность, что стрелок и жерва живы равна P_k = (N-1)/N*((N-m_k)/N)^2 + 1/N*(N-m_k)/N
Соответственно, исправленная формула выглядит так:
m_0=0, m_{k+1} = m_k + p P_k.

В "ковбойской" версии я пользовался следующим (ошибочным) рассуждением. Вероятность погибнуть каждому конкретному человеку равна p: действительно, i-й человек целится в него с вероятностью 1/N и убивает с вероятностью p, суммируя по i=1..N получаем вероятность p. Так как всего человек N, то ожидаемое убитых будет pN.

Правильнее, конечно, не суммировать вероятности, а перемножать их дополнения, тогда получится N*(1-(1-p/N)^N), как у Вас.

(Ответить) (Уровень выше) (Ветвь дискуссии)

	flaass@lj 2005-03-02 09:04 (ссылка)
	Да, все верно. Я не допер, что в каждый момент вероятность быть живым у всех одинакова. (А случай, когда к+1-й выбирает себя, отдельно рассматривать не надо.) (Ответить) (Уровень выше) (Ветвь дискуссии)

garvej@lj
2005-03-02 13:13 (ссылка)

Что-то тут не так.
С точным ответом не сходится уже при N=3.

Вероятность быть живым неодинакова.
Кто стреляет раньше - у того вероятность выше :-)))
Ведь он может застрелить того, кто хотел застрелить его самого.

Для N=3 всего 27 вариантов, легко перебрать вручную.
Вероятности выжить равны: 12/27, 11/27 и 10/27

(Ответить) (Уровень выше) (Ветвь дискуссии)

	flaass@lj 2005-03-03 01:03 (ссылка)
	Вау. Страньше и страньше. (А загадку про 9значное число из след. записи - разгадал? :) ) (Ответить) (Уровень выше) (Ветвь дискуссии)

	garvej@lj 2005-03-03 09:55 (ссылка)
	Не, не разгадал. Что-то тут слишком хитрое :) Кроме десяти негритят ничего в голову не лезет... %) (Ответить) (Уровень выше)

	garvej@lj 2005-03-03 10:48 (ссылка)
	Блин! Девятизначное число! 3.1415926 Когда встречаешь рядом 1, 3 и 4 - надо сразу настораживаться :) (Ответить) (Уровень выше)

garvej@lj
2005-03-02 12:02 (ссылка)

Матожидание количества выживших для малых значений N. p=1.
{2, 3/4};
{3, 11/9};
{4, 111/64};
{5, 1398/625};
{6, 1775/648};
{7, 381273/117649};

Не знаю, поможет ли ;)
Закономерность не очень просматривается.

Но если смоделировать расстрелы для большого N, то доля выживших что-то подозрительно близка к 1/2.

(Ответить)