Здравствуйте. Представим простейшую задачу. Имеется мешок с шарами, пронумерованными от 1 и до конца. Шаров — случайное количество. Экзаменуемый просовывает руку в мешок и тянет один шар, смотрит на его номер и должен попытаться угадать, сколько всего шаров было в мешке. Возможность тактильной или визуальной оценки этого количества в момент взятия шара исключаем. Вопрос — как должен рассуждать экзаменуемый, чтобы максимально точно угадать изначальное количество шаров в мешке на некотором большом количестве независимых экспериментов, в случаях, если:
1. Максимум шаров известен (то есть экзаменуемый знает, что в мешке равновероятно от одного до N шаров).
2. Максимум шаров есть, но экзаменуемому неизвестен (экзаменатор сам решил, сколько шаров максимум может быть в мешке, но распределение все равно линейное).
3. Максимум шаров вообще не определен (не знаю, имеет ли такая постановка задачи вообще смысл).
В каждом эксперименте количество шаров в мешке разное, но максимум, если он установлен — один.

Здравствуйте, Went, Вы писали:

W>1. Максимум шаров известен (то есть экзаменуемый знает, что в мешке равновероятно от одного до N шаров).

Предположим, максимальное число шаров 100, вытащили шар с N=10

Далее для удобства предположим, что у нас есть миллион мешков и с каждым проводили такой опыт. У 10 тысяч мешков Max=1, ещё у 10 тысяч Max=2, ещё у 10 тысяч Max=3 и т.д.
Вытащили N=10. Можно отбросить все мешки с Max<=9. Если Max=10 (всего 10 тысяч таких мешков), вероятность вытащить мешок с N=10 равна 1/10, соответственно получается тысяча вытаскиваний. Если Max=11, вероятность равна 1/11 и получается 10000/11 вытаскиваний (примерно 909). Если Max=12, получается 10000/12 вытаскиваний (833). Если Max=100 получается 10000/100=100 вытаскиваний.
Далее можно просуммировать все вытаскивания: 10000*(1/10+1/11+1/12+1/13+1/14+…+1/100). Мне лень столько считать, но это легко прокодить. По-моему получится около 40 000 вытаскиваний.
Из этих 40 000 тысяча соответствует Max=10, 909 соответствует Max=11, 833 соответствует Max=12 и т.д. Т.е. видно, что наиболее вероятный Max = 10. Итого ответ: наиболее вероятно число шаров, равное номеру вытащенного шара.

W>2. Максимум шаров есть, но экзаменуемому неизвестен (экзаменатор сам решил, сколько шаров максимум может быть в мешке, но распределение все равно линейное).

А здесь уже есть ошибка. Когда выбирался максимум шаров, какое предполагалось распределение? Если говорить “распределение все равно линейное”, значит максимум шаров мог быть с равной вероятностью равен и миллиону, и миллиарду, и гуглу – не получается. Так что распределение не могло быть линейным. Можно сформулировать задачу, например, так: распределение возможных Max убывает по экспоненте до бесконечности. Такую задачу решить можно.

W>3. Максимум шаров вообще не определен (не знаю, имеет ли такая постановка задачи вообще смысл).

См. 2.

W>В каждом эксперименте количество шаров в мешке разное, но максимум, если он установлен — один.

В смысле минимум?

Здравствуйте, Went, Вы писали:

W>Здравствуйте. Представим простейшую задачу. Имеется мешок с шарами, пронумерованными от 1 и до конца. Шаров — случайное количество. Экзаменуемый просовывает руку в мешок и тянет один шар, смотрит на его номер и должен попытаться угадать, сколько всего шаров было в мешке.

Я бы вульгарно предположил, что 2*N. Интересно, что скажут точные рассчёты.

Здравствуйте, Khimik, Вы писали:

K>Здравствуйте, Went, Вы писали:

W>>1. Максимум шаров известен (то есть экзаменуемый знает, что в мешке равновероятно от одного до N шаров).

K>Итого ответ: наиболее вероятно число шаров, равное номеру вытащенного шара.

Что-то какой-то контр-интуитивный результат.

Имхо надо считать по Байесу. Нам надо найти распределение вероятностей P[число шаров в мешке N | мы вытащили шар k],

что по Байесу равно P[мы вытащили шар k | число шаров в мешке N] * P[число шаров в мешке N] (опуская нормализацию в знаменателе).

В качестве ответа берём N, при котором вероятность P[число шаров в мешке N | мы вытащили шар k] максимальна.



Если про распределение максимума шаров в мешке ничего не известно, используем фреквентистскую интерпретацию, и считаем вероятности P[мы вытащили шар k | число шаров в мешке N] для разных N, и берём N который максимизирует эту вероятность. В этом случае ваш результат корректен — скажем, если мы вытащили шар №10, то при 10 шарах в мешке фреквентистская вероятность этого события — 1/10, при 11 — 1/11, и т.д.

Хотя да, по Байесу получается такой же результат при равновероятностном распределении кол-ва шаров в мешке. Интересно — контр-интуитивный результат действительно верен.

Здравствуйте, Went, Вы писали:

W>Здравствуйте. Представим простейшую задачу. Имеется мешок с шарами, пронумерованными от 1 и до конца. Шаров — случайное количество. Экзаменуемый просовывает руку в мешок и тянет один шар, смотрит на его номер и должен попытаться угадать, сколько всего шаров было в мешке. Возможность тактильной или визуальной оценки этого количества в момент взятия шара исключаем. Вопрос — как должен рассуждать экзаменуемый, чтобы максимально точно угадать изначальное количество шаров в мешке на некотором большом количестве независимых экспериментов, в случаях, если:

Навскидку, в режиме блиц-раунда:

W>1. Максимум шаров известен (то есть экзаменуемый знает, что в мешке равновероятно от одного до N шаров).

Q(i) = (N(i) + M) / 2;
где:
i — номер попытки (он же номер мешка);
Q(i) — искомое количество шаров в i-м мешке;
N(i) — номер шара, извлеченного из i-го мешка;
M — максимально допустимое количество шаров в мешке (общее для всех мешков).

W>2. Максимум шаров есть, но экзаменуемому неизвестен (экзаменатор сам решил, сколько шаров максимум может быть в мешке, но распределение все равно линейное).

N(avg) = Sum(N(i)) / n;
M = N(avg) * 2;
Q(i) = (N(i) + M) / 2;
где:
n — количество попыток
Sum(N(i)) — сумма номеров шаров по всем попыткам
N(avg) — средневзвешенный номер шара по всем попыткам

W>3. Максимум шаров вообще не определен (не знаю, имеет ли такая постановка задачи вообще смысл).

Q(i) = N(i) * 2.

Здравствуйте, RiNSpy, Вы писали:

RNS>Хотя да, по Байесу получается такой же результат при равновероятностном распределении кол-ва шаров в мешке. Интересно — контр-интуитивный результат действительно неверен.


В смысле — верен?

Я освоился с решением таких задач, когда писал в блоге свою статью "Опровержение "теоремы о конце света"":

http://www.grandrienko.com/DA.html

Здравствуйте, Khimik, Вы писали:

K>Здравствуйте, RiNSpy, Вы писали:

RNS>>Хотя да, по Байесу получается такой же результат при равновероятностном распределении кол-ва шаров в мешке. Интересно — контр-интуитивный результат действительно неверен.

K>В смысле — верен?

Да, извиняюсь, поправил.

Здравствуйте, Went, Вы писали:

W>Здравствуйте. Представим простейшую задачу. Имеется мешок с шарами, пронумерованными от 1 и до конца. Шаров — случайное количество. Экзаменуемый просовывает руку в мешок и тянет один шар, смотрит на его номер и должен попытаться угадать, сколько всего шаров было в мешке. Возможность тактильной или визуальной оценки этого количества в момент взятия шара исключаем. Вопрос — как должен рассуждать экзаменуемый, чтобы максимально точно угадать изначальное количество шаров в мешке на некотором большом количестве независимых экспериментов, в случаях, если:
W>1. Максимум шаров известен (то есть экзаменуемый знает, что в мешке равновероятно от одного до N шаров).
W>2. Максимум шаров есть, но экзаменуемому неизвестен (экзаменатор сам решил, сколько шаров максимум может быть в мешке, но распределение все равно линейное).
W>3. Максимум шаров вообще не определен (не знаю, имеет ли такая постановка задачи вообще смысл).
W>В каждом эксперименте количество шаров в мешке разное, но максимум, если он установлен — один.

Если кому интересно — наши союзники во второй мировой войне использовали решение похожей проблемы для оценки количества немецких танков, исходя из серийных номеров танков захваченных: https://en.wikipedia.org/wiki/German_tank_problem (к сожалению, не нашёл на русском).

Т.е. использовалась расширенная версия исходной задачи, где вы вынимаете не один шар, а несколько. Интересно, что подобная математическая оценка оказалась намного точнее данных разведки.

Здравствуйте, RiNSpy, Вы писали:

RNS>Если кому интересно — наши союзники во второй мировой войне использовали решение похожей проблемы для оценки количества немецких танков, исходя из серийных номеров танков захваченных: https://en.wikipedia.org/wiki/German_tank_problem (к сожалению, не нашёл на русском).

Для этой же цели серийные номера делают непопорядку.

Здравствуйте, Khimik, Вы писали:

K>http://www.grandrienko.com/DA.html

Чтобы это показать нагляднее, приведём два примера таких задач:
1) Попросить человека загадать случайное число N (с заданным распределением вероятностей) ...

Khimik, если вы разбирались с этой задачей, то задумывались ли вы над тем, каким способом можно было бы из бесконечного набора чисел выбрать случайное число N?

Здравствуйте, B0FEE664, Вы писали:

BFE>Здравствуйте, Khimik, Вы писали:

K>>http://www.grandrienko.com/DA.html
BFE>

BFE>Чтобы это показать нагляднее, приведём два примера таких задач:
BFE>1) Попросить человека загадать случайное число N (с заданным распределением вероятностей) ...

BFE>Khimik, если вы разбирались с этой задачей, то задумывались ли вы над тем, каким способом можно было бы из бесконечного набора чисел выбрать случайное число N?

Распределение вероятностей должно быть убывающим и составлять сходящийся ряд.
Например, вероятность что N=1 равна 1/2, вероятность что N=2 равна 1/4, вероятность что N=3 равна 1/8, далее 1/16 и т.д. Сумма этих вероятностей даст единицу.
А если попробовать так: P(N=1)=1/2, P(N=2)=1/3, P(N=3)=1/4, далее 1/5, 1/6 и т.д. — получается в сумме бесконечность, т.е. такое распределение использовать нельзя. Это называется гармонический ряд.

Здравствуйте, Khimik, Вы писали:

K>Я освоился с решением таких задач, когда писал в блоге свою статью "Опровержение "теоремы о конце света"":
K>http://www.grandrienko.com/DA.html
Ха, как раз исходя из схожих мыслей у меня и возникла данная задача. Выражаясь "философски", она звучит так: "является ли тот факт, что я живу именно сейчас доводом того, что именно сейчас количество людей, живущих на планете — максимально?" То есть тут сразу несколько вопросов скрывается:
1. Можно ли считать факт моего рождения именно сейчас независимым экспериментом? Например тот факт, что вместе со мной родился мой брат, таковым считать нельзя (если бы не родился именно этот мой брат, родился бы какой-то другой, которого я бы считал именно этим). Но я — один, если я родился в это время, значит, я не родился ранее и не рожусь позднее. Или все-таки, это иллюзия? Ведь подобным вопросом мог задаться и житель древней Греции, решивший, что именно он, вероятно, находится на "экваторе" человеческого вида. И он бы, очевидно, ошибся. Но ведь он тоже — не я, какое-то количество людей должно было родиться тогда в Греции и задуматься о подобном вне зависимости от того, сколько людей еще родятся. Для человека, родившегося вчера — я такой же "грек", но ведь и он для меня "грек"?
2. Если все-таки, факт моего рождения статистически значим, то какова эта значимость? Мы не знаем сколько еще людей родится. Если представить оптимистическую теорию о том, что человечество колонизирует множество планет и будет исчисляться не миллиардами, а триллионами, и в день будет рождаться много большее количество людей, чем рождалось в конце 20-го века, то какова была вероятность, что я попаду именно в эти 60 миллиардов (вроде столько было человек на Земле за всю историю судя по вики?), а не в те триллионы и триллионы, что родятся позже?
3. Имеет ли для проблемы определение границы пред-человека, современного человека и пост-человека (если таковой будет)? Мог ли "я" оказаться неандертальцем (они же точно так же себя осознавали, хотя и вряд ли задавались подобными вопросами) или разумной кибернетической машиной? Кибернетическая машина, будучи достаточно умной, наверняка, может задаться подобным вопросом, но будет ли ее мнение статистически важным?

Здравствуйте, Went, Вы писали:

W>Здравствуйте, Khimik, Вы писали:

K>>Я освоился с решением таких задач, когда писал в блоге свою статью "Опровержение "теоремы о конце света"":
K>>http://www.grandrienko.com/DA.html
W>Ха, как раз исходя из схожих мыслей у меня и возникла данная задача. Выражаясь "философски", она звучит так: "является ли тот факт, что я живу именно сейчас доводом того, что именно сейчас количество людей, живущих на планете — максимально?" То есть тут сразу несколько вопросов скрывается:
W>1. Можно ли считать факт моего рождения именно сейчас независимым экспериментом? Например тот факт, что вместе со мной родился мой брат, таковым считать нельзя (если бы не родился именно этот мой брат, родился бы какой-то другой, которого я бы считал именно этим). Но я — один, если я родился в это время, значит, я не родился ранее и не рожусь позднее. Или все-таки, это иллюзия? Ведь подобным вопросом мог задаться и житель древней Греции, решивший, что именно он, вероятно, находится на "экваторе" человеческого вида. И он бы, очевидно, ошибся. Но ведь он тоже — не я, какое-то количество людей должно было родиться тогда в Греции и задуматься о подобном вне зависимости от того, сколько людей еще родятся. Для человека, родившегося вчера — я такой же "грек", но ведь и он для меня "грек"?
W>2. Если все-таки, факт моего рождения статистически значим, то какова эта значимость? Мы не знаем сколько еще людей родится. Если представить оптимистическую теорию о том, что человечество колонизирует множество планет и будет исчисляться не миллиардами, а триллионами, и в день будет рождаться много большее количество людей, чем рождалось в конце 20-го века, то какова была вероятность, что я попаду именно в эти 60 миллиардов (вроде столько было человек на Земле за всю историю судя по вики?), а не в те триллионы и триллионы, что родятся позже?
W>3. Имеет ли для проблемы определение границы пред-человека, современного человека и пост-человека (если таковой будет)? Мог ли "я" оказаться неандертальцем (они же точно так же себя осознавали, хотя и вряд ли задавались подобными вопросами) или разумной кибернетической машиной? Кибернетическая машина, будучи достаточно умной, наверняка, может задаться подобным вопросом, но будет ли ее мнение статистически важным?

Я думаю, это всё паралогизмы, а ответ таков: "Теорема о конце света" (Doomsday argument) и подобные рассуждения не имеют никакой предсказательной силы. Подробнее всё это разобрано у меня в статье.

Здравствуйте, Went, Вы писали:

На одном форуме эта тема долго обсуждалась, процитирую одного участника, который понял мои рассуждения:

Лол, оно вообще на поверхности лежало.
Теперь даже удивляюсь почему его сразу не увидел никто из нас.
Мы до сих пор рассуждали всегда по одной колее:
Есть два мешка в первом 100 камней во втором 1000 камней.
Тебе дают случайно выбрать мешок и выбранного мешка вытаскивают случайный камень — и просят по номеру оценить из какого мешка камень.

Ответ: Если ты видишь номер >100 — это 100%-ов мешок 2. Если номер <=100 — это с вероятностью 9/10 значительно повышенной мешок №1.

Но на самом деле формулировка должна быть такой:
Есть два мешка в первом 100 камней во втором 1000 камней.
Тебе дают случайный камень из них — и просят по номеру оценить из какого мешка камень.
Чувствуешь где теперь вероятности? =)

Еще раз смотри — предположим мы вытащили из 1-ого одного мешка камень — и мы можем с 95%-ой вероятностью утверждать что он находится в 95%-ах любого подмножества мешка (последние ли 95%-ов, или первые 95%-ов, или средние 95%-ов — неважно).
Это абсолютно верное утверждение и с 95%-ой вероятностью мы можем дать прогноз на 95%-ов верный о количестве камней в ЭТОМ мешке.

Теперь говорим что есть 2 мешка в одном из которых в 100 раз больше камней, чем в другом.
Выбираем случайно один из мешков и вынимаем из него случайно камень — просим оценить в каком мешке мы находимся — оказывается что 50 на 50, ибо выбор был дан в первом выборе, а не во втором — т.е. у нас нет оснований полагать что вероятнее всего живём в более короткой вселенной — хотя мы так же разрушаем миф о том, что DA говорит что более вероятно жить недолго (т.е. находится в меньшем мешке). Никакие выборки тут смысла не имеют.

А теперь делаем еще более крутой коленкор — выбираем случайный камень из обоих мешков сразу — ведь это и значит "родится в случайное время в случайном месте", т.е. высыпаем все камни на землю, тыкаем в один из них случайно, а потом уже смотрим из какого мешка выбранный был — не фиксируется изначально 50 на 50 в какой вселенной мы живём.
То... получается что в 100 раз больше шансов оказаться в более долгоживущей вселенной!
Лол, т.е. при честной выборке вероятность жить дольше даже больше!

Здравствуйте, Khimik, Вы писали:

BFE>>Khimik, если вы разбирались с этой задачей, то задумывались ли вы над тем, каким способом можно было бы из бесконечного набора чисел выбрать случайное число N?

K>Распределение вероятностей должно быть убывающим и составлять сходящийся ряд.
K>Например, вероятность что N=1 равна 1/2, вероятность что N=2 равна 1/4, вероятность что N=3 равна 1/8, далее 1/16 и т.д. Сумма этих вероятностей даст единицу.
Понятно. Спасибо.

Здравствуйте, Khimik, Вы писали:

W>>1. Максимум шаров известен (то есть экзаменуемый знает, что в мешке равновероятно от одного до N шаров).
K>Итого ответ: наиболее вероятно число шаров, равное номеру вытащенного шара.

Быть этого не может. Если мы вытащили шар с номером m < N, то мы достоверно знаем, что в мешке не менее m шаров. А варианты такие... шаров может быть m, m+1, m+2, ... N, хотя, конечно, распределение не линейное.

Т.е. у нас есть предел N шаров. В мешке лежит M шаров (M <= N) и вытащили шар с номером m. В этой ситуации лично мне интуитивно кажется, что оценка для M будет лучше m, если взять её за сумму m + m/e, где e — число Эйлера (2,7...).

Здравствуйте, B0FEE664, Вы писали:

BFE>Быть этого не может. Если мы вытащили шар с номером m < N, то мы достоверно знаем, что в мешке не менее m шаров. А варианты такие... шаров может быть m, m+1, m+2, ... N, хотя, конечно, распределение не линейное.

Оно плавно убывающее. Для m вероятность самая большая.

BFE>Т.е. у нас есть предел N шаров. В мешке лежит M шаров (M <= N) и вытащили шар с номером m. В этой ситуации лично мне интуитивно кажется, что оценка для M будет лучше m, если взять её за сумму m + m/e, где e — число Эйлера (2,7...).

Здесь уже выше написали — интуитивное решение неверное.
Интуитивное решение было бы правильным, если бы распределение вероятностей имело некий пик, похожий на гауссов, справа от m. Но здесь этого нет, вероятность просто плавно убывает от m до N.

Здравствуйте, Khimik, Вы писали:

BFE>>Быть этого не может. Если мы вытащили шар с номером m < N, то мы достоверно знаем, что в мешке не менее m шаров. А варианты такие... шаров может быть m, m+1, m+2, ... N, хотя, конечно, распределение не линейное.
K>Оно плавно убывающее. Для m вероятность самая большая.

Даже если убывающие, то ведь это значит, что m — не наилучшая оценка.

BFE>>Т.е. у нас есть предел N шаров. В мешке лежит M шаров (M <= N) и вытащили шар с номером m. В этой ситуации лично мне интуитивно кажется, что оценка для M будет лучше m, если взять её за сумму m + m/e, где e — число Эйлера (2,7...).
K>Здесь уже выше написали — интуитивное решение неверное.
K>Интуитивное решение было бы правильным, если бы распределение вероятностей имело некий пик, похожий на гауссов, справа от m. Но здесь этого нет, вероятность просто плавно убывает от m до N.

Погодите. Нам ведь нужно найти наилучшую оценку для M, а не наибольшую вероятность того, что некое число совпадёт с M. Вопрос стоит так:

Вопрос — как должен рассуждать экзаменуемый, чтобы максимально точно угадать изначальное количество шаров в мешке на некотором большом количестве независимых экспериментов

Обозначим за X угадываемое число — оценку для M. Нам нужно найти такое X, чтобы sum(|X-M|)/k (где к — количество испытаний) было минимальным. Т.е. от нас требуется найти не наиболее часто выпадающие число для количества шаров в мешке, а такое число, которое будет наиболее точно указывать количество шаров в мешке. Т.е. искать надо не то число которое наиболее часто совпадает с числом шаров в мешке, а такое число, что которое наиболее часто будет лежать поблизости от числа шаров в мешке.

Т.е., иными словами, угадать, что число лежит в некотором диапазоне от M можно в большем количестве случаев, чем то число которое точно совпадает с M. При этом средняя ошибка будет меньше.

Если бы мы играли в эту игру на деньги по таким правилам, что в каждом раунде ставку забирает тот, чьё число ближе к количеству шаров в мешке, то я бы выигрывал чаше не смотря на то, что вы чаще бы меня угадывали число шаров в мешке.

Здравствуйте, B0FEE664, Вы писали:

BFE>Если бы мы играли в эту игру на деньги по таким правилам, что в каждом раунде ставку забирает тот, чьё число ближе к количеству шаров в мешке, то я бы выигрывал чаше не смотря на то, что вы чаще бы меня угадывали число шаров в мешке.

Да, вроде верно. Рассуждать лучше так, как я уже показывал – разобрать большое количество конкретных случаев.

Предположим, максимальное число шаров N=100.
Всего миллион мешков, в десяти тысячах из них M=10. Для любого другого M тоже наберётся 10 тысяч мешков.
Мы играем миллион раз. Для каждого M все десять тысяч мешков надо разделить на M – получится число вытаскиваний шаров c отдельным m. Предположим, M=10. Имеем 10 тысяч мешков, в тысяче случаев вытащили шар с m=1, ещё в тысяче – шар с m=2, и.т.д. до десяти. Я всегда называю m, угадываю в тысяче вытаскиваний (из десяти тысяч – только в одной тысяче m совпадает с M). Вы называете, например, m*1.5 с округлением либо вверх, либо вниз. При округлении вверх вы не угадываете никогда: при m=6 вы называете 9, при m=7 вы называете 11. При округлении вниз вы угадываете в тысяче случаев с m=7. Тут получается путаница из-за округлений, но в целом видно что вы будете угадывать M немного реже.
Для тысячи мешков с m=2 я называю 2, а вы называете 3. Ваш ответ ближе к 10. Для четырёх тысяч мешков я называю 4, а вы называете 6 – тоже ближе. Мой ответ оказывается ближе только для m=9,10 (я называю 9, вы 13 или 14; я называю 10 а вы 15). Для m=8 наши ответы равноудалены (я называю 8, вы 12).
Тут следует подсчитать и для других M, просуммировать, но вроде ответ виден. Тем не менее, мой ответ больше подходит к изначальной формулировке “максимально точно угадать изначальное количество шаров в мешке”.

Здравствуйте, B0FEE664, Вы писали:

BFE>Погодите. Нам ведь нужно найти наилучшую оценку для M, а не наибольшую вероятность того, что некое число совпадёт с M.

Кстати да. Почему нам здесь интересна именно максимальная вероятность, а не мат. ожидание?