Comments 145
И доказывается это, кажется, немного проще…
… А следом за трамваем едет маршрутка с номером "к418м" и уж тут можно фантазию развернуть как угодно..
Пример про автобусы "1МА":
В целях упорядочения работы между двумя маршрутами № 1МА (ночной) и № 1МА (временный), по распоряжению Комитета по транспорту к нумерации временного маршрута добавляется точка (.)
Просто ссылки в тему:
Необычная система нумерации автобусных маршрутов
Как дают номера маршрутам городского транспорта?
Математик: — Допустим это и то, допустим мы тут бесконечными жизнями обладаем и можем каждый день попадать в разные города и кто-то нам задает один и тот же вопрос 100500 раз. Допустим мы выиграем в случае, когда не угадаем, но не сильно. И вот сейчас мы решим эту задачку…
Не-математик (которому задали вопрос здесь и сейчас, у него нет бесконечных жизней, у него нет придуманных условий выигрыша) пытается решить задачу в той постановке, в которой она была дана.
И по итогу этой, математически хорошей, статьи, мы так и не имеем ответа на вопрос задачи. Зато у нас есть прекрасное, верное и абсолютно бесполезное решение задачи придуманной математиком по мотивам трамвая и чит-кода на бесконечные жизни. )
Классический сферический конь в вакууме
n < 15: x2
n > 30: x1.5
n > 40: x1
n > 45: n
Это похоже на бой с тенью. Сами допридумывали разные условия и обстоятельства, сами что-то героически посчитали-порешали...
Ввели бинарный признак хорошести оценки — причём, несимметричный, N/2 <= V <= 2N
Почему не (1-0.5)N <= V <= (1+0.5)N?
Почему бинарный, а не штраф за промах, E = |V/N — 1|, например?
Ввели противника, который может играть против вас, подсовывая неудобные значения. Вместо бездушной статистики, ведь ради вас никто загодя не будет строить город с трамвайными линиями, вы просто случайно приехали в готовый город.
Вообще, на то уж пошло. А какая может быть встречная стратегия?
Да очень простая. Нарезать числовую ось на непересекающиеся интервалы допусков.
[17..34..68], [69..138..276], [277..554..1108],…
Далее мы получаем игру с горошиной и X руками.
Любая ваша оценка попадёт либо в один, либо в другой, либо в какой-угодно-ещё интервал.
И я просто наберу статистику о том, как вы предпочитаете выбирать руку, и постараюсь класть горошину в другую. В крайнем случае, — или даже если я не злокозненный, а ленивый пофигист, просто буду класть её наобум.
А поскольку числовая ось бесконечна, то мои шансы выиграть у вас тоже бесконечны. Ну и помогут вам ваши формулы?
А всё почему? Потому что в реальности нет игрока, строящего трамвайные линии.
Вы то говорите, что статистической устойчивости нет, то в соседней ветке — "если вы приедете в 1000 городов...". Определитесь уже!
Если здесь игра с двумя игроками, то одна история. Если посещение городов — другая.
Допустим, я провожу собеседование и задаю вам эту задачу 1000 раз.
Моя оптимальная стратегия тогда будет — случайно чередовать 1000 центров разных интервалов. Авось вы не угадаете мой ГСЧ.
А уж если я знаю вашу эвристику "просто умножьте номер трамвая на 2", — то это ровно то же, как если вы всё время будете искать горошину в правой руке. Буду класть её в левую.
Получается, вы начали за здравие, а кончили за упокой.
Сами хотели уйти от тупой стратегии, сами же к ней пришли.
И кстати, именно поэтому бинарная целевая функция — плохая затея.
Мне, чтобы играть против вас, надо подсовывать любое неподходящее N.
А была бы там плавная функция, — мой выбор был бы не равноценным, я стал брать бы N, максимизирующие её, а вы стали бы охотиться на эти значения… и в результате получилось бы какое-то равновесие.
Вы то говорите, что статистической устойчивости нет, то в соседней ветке — «если вы приедете в 1000 городов...». Определитесь уже!
В обычном понимании «статистическая устойчивость» — это когда частоты наблюдения исходов стремятся каждый к какому-то пределу. Рассмотрим последовательность 101100111100001111111100000000 (каждый раз удваивайте длину участка единиц и участка нулей) — она дает пример, когда статистической устойчивости нет, хотя ее длина даже не 1000, а бесконечность.
Допустим, я провожу собеседование и задаю вам эту задачу 1000 раз.
Моя оптимальная стратегия тогда будет — случайно чередовать 1000 центров разных интервалов
Во власти судьбы выбирать город, но не трамвай. Соответственно Вы можете выбирать параметр длины в семействе равномерных распределении, но не имеете право подменять каким-то своим числом случайный выбор точки из отрезка. Если правила соблюдены, то «вуаля» и моя стратегия прекрасно работает, даже когда она вам известна.
Так что, кому-то еще рано принимать экзамены)
Кто это сказал, что судьба может подсовывать только город? Она и трамвай так же может подсовывать.
"Мы-то знаем", что номер трамвая — 17. Судьба постаралась.
Итак представьте, что Вы приехали в абсолютно незнакомый город и первый трамвай, который вам там повстречался, следовал под номером 17. Как оценить, сколько всего в этом городе трамвайных маршрутов?
В такой постановке правильный ответ — «как минимум один». Потому что, строго говоря, не гарантируется что номера назначаются непрерывно. Возможно именно в этом городе вообще сквозная нумерация для всего общественного транспорта, и все от 1 до 16 — троллейбусы и автобусы. А возможно раньше их было 20, а сейчас все кроме 17 закрыты. Так что всё, кроме «как минимум один» — игра в угадайку, и практического смысла не имеет.
Для простоты считайте, что трамвайные маршруты в городе пронумерованы без пропусков числами от 1 до N и изначально каждое из этих чисел с равными шансами могло оказаться номером трамвая, который вы бы увидели первым.
А почему от 1?
В моем городе есть трамвай номер 0 :)
Причем их два — 0P и 0L, это кольцевой маршрут, одинидёт по часовой, второй против часовой :)
В этой деревне есть коза белая слева (с)
Наиболее вероятно для приезжего встретить трамваи №3 и №27 (на мой взгляд), а маршрутов всего 11.
С чего вы взяли, что ошибиться в два раза в любую сторону — приемлемое решение? Где это было в условиях задачи? Почему не в три, или не на две штуки считать приемлемой ошибкой?
А ведь было интересно. Поначалу.
Ну да, "Бессмыслица — искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет.“…
Нет, этого я не понимаю. В чём тогда заключается решение? Приведите примеры, пожалуйста.
Просто из любопытства — а вы сами можете прямо сейчас, не заглядывая в интернет или справочники, назвать хотя бы один город, в котором есть больше двух трамвайных маршрутов и их нумерация сплошная?
А попробуйте оценить (тоже теоретически) количество таких городов в мире?
В исходной постановке задачи самым разумным мне кажется ответ человека с матмеха.
по максимальному правдоподобию.
Зато в данном случае не требует введения новых параметров. Почему успешным считается интервал интервал [0.5, 2]N, а не [0.9, 1.11]N или [0.5, 1.5]N? Это дополнительные сущности, которые тоже надо как-то оправдывать.
В целом же, я соглашусь с ответом "похоже, что тут как минимум 17 маршрутов", а всё остальное слишком расплывчато, да и кто нас, в конце концов, спрашивает?
Потому, что количество маршрутов может быть любое от 17 и дальше в некоторых разумных пределах. Про 17 мы точно знаем, что такой ответ может быть правильным, про остальные мы это утверждать не можем, поэтому выбрав 17, вероятность угадать выше.
Что значит «оценить количество маршрутов»? Угадать точное количество или дать оценку сверху? Как автор получил вероятность в 50% и 75%, если для вселенной с возможным бесконечным количеством трамваев вероятность того, что их конкретное количество равно 17, стремится к нулю? Равно как и вероятность того, что их n или 2n — она бесконечно мала.
Значит, постановка видимо другая? Где-то умолчали про нормальное распределение количества маршрутов в городах вселенной? Или под оценить понимается не «угадать точное число маршрутов», а что тогда?
А вот теперь встречный вопрос — какая оценка считается «успешной»?
Причем он должен быть похож на нормальное распределение
1. "… Вы приехали в абсолютно незнакомый город" — город выбран случайно из всех существующих городов.
2. "… и первый трамвай..." — значит в городе есть трамвай. Трамваи появляются в городах начиная с некоторого количества жителей и с увеличением числа жителей увеличивается количество маршрутов.
3. «Как оценить сколько всего в этом городе маршрутов?» — назвать самое вероятное число маршрутов.
Ограничения которые Вы уже наложили:
1. Маршруты пронумерованы без пропусков в возрастающем порядке начиная с 1.
2. Вероятность встретить любой номер маршрута одинакова.
Собственно, после того как задана равновероятность встречи любого маршрута в городе, задача свелась к предположениям о распределении количества маршрутов по городам. Другими словами — в город с каким количеством маршрутов мы попали в результате случайного выбора.
Я бы сделал следующие предположения:
1. Городов тем больше, чем меньше в них жителей.
2. Новый маршрут появляется через одинаковый прирост количества жителей.
Из этих предположений следует, что распределение вероятностей количества маршрутов в городе — это убывающая до нуля дискретная функция.
Разделим для наглядности задачу на два этапа:
1. Вы еще не увидели номер трамвая, но он уже показался из-за поворота. Какой номер маршрута прибывающего трамвая будет самый вероятный? Ответ: номер 1. Потому что он есть в каждом городе, где есть трамвай, а вероятность встретить любой номер одинакова.
А сколько всего маршрутов в этом городе? Вероятнее всего тоже 1.
2. Теперь мы увидели номер маршрута. Что дала нам эта информация? Мы отсекаем маршруты меньше прибывшего номера, по моим предположениям они самые вероятные и следующим самым вероятным останется номер прибывшего. В Вашей задаче — 17.
Мехмат, однако.
. "… Вы приехали в абсолютно незнакомый город" — город выбран случайно из всех существующих городов.
Изюминка задачи именно в том, что в город выбирается не обязательно случайно, однако ее решение все равно работает.
Кстати, про стратегию того, кто прячет
Вы привнесли в задачу слишком много нереалистичных условий. В результате её стало можно решить, но к реальному миру это решение не имеет ни малейшего отношения
В качестве примера — мой родной Харьков:
Наиболее вероятно для приезжего встретить трамваи №3 и №27 (на мой взгляд), а маршрутов всего 11.
Может и так, но только разве я виноват в том, что жизнь тяжелая и городские власти Харькова разворовали половину трамвайных путей?
Например, первый маршрут прокладывался так, чтобы не пересекаться с конкой. С исчезновением конки — стали актуальны другие маршруты, но номер некоторое время не использовался, чтобы люди не путались и т.д.
А вот:
Будем считать, что ваш ответ считается приемлемым и игра заканчивается в вашу пользу, если только названное вами число отличается менее чем в два раза от истинного, причем как в большую, так и в меньшую стороны.
Меняет.
А чем вызван такой необычный метод задания ошибки? Диапазон выигрышных ответов «в меньшую» в два! раза меньше чем диапазон «в большую»?
В Вашей формализации ответ зависит от наложенного критерия «выигрыша», что Вы элегантно и доказали. Если «выигрыш» определить как минимальное отклонение, то и ответ будет 17. И то, что закон выбора городов не известен, не меняет ответа, это следует и из Вашего решения тоже.
Спасибо! Было интересно.
Если «выигрыш» определить как минимальное отклонение, то и ответ будет 17. И то, что закон выбора городов не известен, не меняет ответа, это следует и из Вашего решения тоже.
-но с наскоку у меня ничего не получилось. Если отклонение — это мат.ожидание модуля разности, то честно говоря, доказательство мне представляется довольно трудным? С Вашей стороны это была а) очевидная догадка, b) Вы знаете как она строго доказывается, или c) я все неправильно понял?
1. «В Вашем решении задавая порог „выигрыша“ мы определяем ответ. Задав порог как „бесконечно минимальное отклонение“ мы получим 17.»
Доказательство, как мне представляется, сделали Вы. Так коэффициент определяющий границу «сверху» (Вы выбрали х2) определяет наклон прямой графика функции l(k). Если мы выберем k=1, то графики функции и обратной функции совпадут, а при малом k, будут отличаться мало. А далее Ваше доказательство. Я думаю что Вы можете его расширить, на случай если необходимо задать верхнюю границу выигрыша НИЖЕ чем первый увиденный номер трамвая, тем самым обезопасив себя от части «перелетов» и таким образом сделать универсальную систему решения для разных стратегий, раз уж мы говорим в терминах игр. (А вдруг, если мы будем чаше ошибаться в большую сторону, то у нас что-нибудь взорвется в конце концов?) Да там много еще чего вскроется, например влияние «нижней» границы выигрыша должно появиться, как мне кажется.
2. «Ваше решение оптимально как для случайного выбора города, так и для неслучайного, до тех пор пока у нас не будет хоть какой-то информации о законе выбора.»
Это утверждение является следствием того, что сумма большого числа любых распределений стремится к нормальному распределению.
Я не математик, возможно мои рассуждения покажутся Вам наивными.
Вы хотите прикинуть потребность города в трамфаях через определение количества маршрутов.
Вам нужно понять сколько трамваем город закупает в год.
Малую партию 1-7. среднюю 8-31, или большую 32+.
в таком случае вам нужен ответ именно в логарифмической шкале.
#!/usr/bin/env python3
import random
FOUND_TRAM = 17
MAX_TRAM = 100
TRY_COUNT = 100000
n_for_17 = {}
for n in range(FOUND_TRAM, MAX_TRAM + 1):
for _ in range(TRY_COUNT):
seen_tram = 1 + random.randrange(n)
if seen_tram == FOUND_TRAM:
n_for_17[n] = n_for_17[n] + 1 if n in n_for_17 else 1
for n in range(FOUND_TRAM, FOUND_TRAM + 20):
print(f"{n}\t{n_for_17[n]}")
Ответ: номер 1. Потому что он есть в каждом городе, где есть трамвай, а вероятность встретить любой номер одинакова.
Исходя из житейских наблюдений, это не совсем так. В достаточном количестве крупных городов (в которых мне довелось побывать) с развитой трамвайной сетью нумерация начинается с 3, либо же 3 является первым трамваем с чисто числовым номером (как в СПб, где до него идут трамваи А и 1Т).
При этом в городах с небольшим количеством линий нумерация начинается, как правило, с 1. Это относится либо к небольшим городам, либо к крупным городам, в которых трамвай был открыт сравнительно недавно и не успел развиться.
Также из наблюдений, в городах со старой трамвайной сетью преобладает старый же подвижной состав, поэтому в первом пункте мы можем опираться на визуальную оценку трамвая, даже не видя его номер.
То есть, если у нас есть данные о том городе, в который мы приехали, то ответ будет:
- В крупном городе (для конкретики пусть будет областной центр или больше) со старой сетью — 3
- В небольшом городе или в городе с новой сетью — 1
По второму пункту опять же возможны варианты
Старая крупная сеть скорее всего изменялась не раз, в том числе с закрытием линий, поэтому для определения количества маршрутов можно взять поправку на них, которая будет примерно 2 маршрута на каждый полный десяток в номере и еще 1, если последняя цифра номера больше 5 (чисто эмпирические значения, не претендующие на математическую точность).
Таким образом, для трамвая 17 ответ будет 17 – 2 – 1 = 14 маршрутов
Написав абзац сверху, я немного задумался, насколько ответ может быть менее точным, поскольку могут существовать трамваи с номером больше встреченного, поэтому буду признателен за комментарий по этому поводу
Пока, трудность в формализации задачи и согласовании допустимых ограничений. Как мне кажется.
Думаю, что если провести проверку яндекс-транспортом по городам России, то автор будет разочарован.
Очень советую взять распределение Пуассона — ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%9F%D1%83%D0%B0%D1%81%D1%81%D0%BE%D0%BD%D0%B0. Оно чаще всего встречается в подобных задачах.
Собрав немного статистики — получим среднее M и ответ будет Max(N, M)
Если мы не знаем функцию распределения трамваев во всех городах мира, то для начала нам надо найти эту функцию распределения, чисто статистическим методом.
Если мы ее знаем, то ответ будет точка между [N, +беск[ — X, такая что интеграл по плотности от [N, X[ = от [X, +беск[.
Ответ, по-моему абсолютно простой, выбираем любое случайное распределение от [1, +бесконечности[, подкидываем монетку и получаем случайное число X. Ответ Maximum(N, X)
Почему это решение хорошее?
Математическое ожидание по определению и есть ответ задачи.
1) мы не знаем вероятностей, с которыми выбираются города, если они выбираются случайно;
2) города выбираются не обязательно случайно — просто каким-то неизвестным для нас способом.
2) это вообще не интересно с точки зрения статистики, любой случайный процесс выбора описывается формулами. Если это неравномерное распределение, то просто статистическую функцию нужно подправить.
В этой задаче нет ничего принципиально нового, для физики это обычный эксперимент. Мы проводим 1 измерение, получаем оценку снизу, можем провести 2-е, можем провести его в других условиях («городе»), но все это можно объединить и посчитать.
Да, математически, имея только оценки снизу не всегда наше математическое ожидание будет стремиться к математическому ожиданию, когда имеются оценка сверху и снизу, или вообще известное точное распределение. Но повторюсь, в этой задаче нет никакой «интересной фишки», просто можно подсмотреть как с этим борются физики последние 100 лет.
Для начала давайте попробуем проанализировать, преимущества и недостатки следующих четырех простеньких стратегий
Что меня всегда поражало в математике (и математиках): с одной стороны, способность на три страницы расписать самую очевидную вещь (как здесь с горошиной), а с другой – в две строчки утрамбовать весь реальный мир, который портит красивые абстракции.
Нет, я понимаю, что всё это правильно, и эти методы приносят реальную пользу, но выглядит это всё, кхм, странновато.
«Как оценить, сколько всего в этом городе трамвайных маршрутов?»
Что значит оценить?
|ответ-реальное значение| должно стремиться к минимуму?
ответ/реальное значение должно стремиться к единице?
Или должна стремиться к максимуму вероятность дать точный ответ?
«Сколько этому джентльмену лет?» в возрасте лет до 25, обычно оцениваем довольно точно — похоже, работают инстинкты. Возраст людей «постарше» обычно оцениваем с большой погрешностью на основании опыта, как кто выглядит к этому возрасту.
«Сколько людей на вокзальной площади?» Оцениваем площадь (в м2) и оцениваем количество человек на м2 (или количество м2 на человека) — тренированных людей оценка будет довольно точной.
«Каков месячный доход вон того парня на мостовой с табличкой в руках?» — увидев «нищего» обыватель с большой вероятностью ошибется с оценкой его дохода.
И математическую оценку точности прогноза можно провести только для варианта «Сколько людей на вокзальной площади?»
Если я поспорил с другом, кто угадает количество лет: то выберу наиболее вероятное количество лет.
Если поспорили кто будет ближе к истинному возрасту, то буду стреиться у минимому мат ожидания разницы реального возраста и ответа.
Если же нужно оценить возраст, с той целью будет ли интересно общаться(скажем возраст не должен отличаться более чем в 2 раза), то имеет значение отношение возраста к моему.
Толи я не достаточно умён, толи формулировка неполная.
Собственно, для того этот вопрос на собеседованиях и задают, чтобы увидеть ход мысли кандидата и его умение вытягивать из клиента, чего же действительно он хочет.
Будем считать, что ваш ответ считается приемлемым и игра заканчивается в вашу пользу, если только названное вами число отличается менее чем в два раза от истинного, причем как в большую, так и в меньшую стороны. Будем также считать, что это очень долгая партия игр, длиною в целую жизнь
Вы ввели удобные для себя дополнительные условия победы.
Это как про стрелка, который рисует мишень вокруг следа попадания
А ответ про
Итак представьте, что Вы приехали в абсолютно незнакомый город и первый трамвай, который вам там повстречался, следовал под номером 17. Как оценить, сколько всего в этом городе трамвайных маршрутов?
Будет на уровне бытовых рассуждений и опыта жизни. Ну например, трамвайных маршрутов скорее всего будет меньше 100.
p.s. В Москве порядка 50-и https://mosgortrans.ru/tram/
Будет на уровне бытовых рассуждений и опыта жизни. Ну например, трамвайных маршрутов скорее всего будет меньше 100.Обычно намного меньше.
В Новосибирске, например, их 11 (как и в Харькове), только самый вероятный — 13-й (а самый большой номер маршрута — 18).
Согласно стратегии «x1» оценкой V для числа N должно быть само k. Понятное, что k никогда не будет больше N, поэтому не может оказаться так, чтобы V была больше 2N. Следовательно наша оценка будет неприемлемой только в одном случае: если V, то есть k, окажется меньше, чем N/2. Вероятность получить k меньшее N/2 при нечетных N не превосходит 50%, а при четных — равна им.
c какой это стати k при четных N с вероятностью 50% вдвое меньше? у нас нет никаких ограничений на N, это может быть и 1000, и миллион. Вероятность будет стремиться к нулю, кмк.
Эту задачу можно начать решать, если наложить хотя бы одно условие: мы на Земле, города — реальные, есть одна цифра — максимальное количество трамвайных маршрутов. Тогда, зная максимальное количество маршрутов и построив распределение Пуассона для количества маршрутов по городам, мы можем оценить вероятность нахождения в городе некоторого количества маршрутов, а получив одно измерение величины — сделать коррекцию оценки в ту или иную сторону.
столько воды ни о чем. количество трамваев по этим данным узнать невозможно.
статистика это псевдонаука типа философии
Так там говорится не о том как узнать, а как сделать предположение, которое с наибольшим успехом окажется правильным.
Статистика — наука, формулирующая теории, находящие подтверждение на практике. Посмотрите хотя бы на коородинаты ГНСС в вашем смартфоне. Без методов обработки данных, разработанных статистиками, вы видели бы галиматью.
Я не дочитывал статью до конца, решил не хватать спойлеров и пошёл своеобразным путём.
Предположил, что число трамвайных маршрутов ± коррелирует с населением города. Решил взять свой город (1.5 млн. человек, 32 трамвайных маршрута), прикинул что самый населённый город на Земле — Токио и там живут 34.5 млн человек. Попробовал посчитать, сколько там должно быть трамвайных маршрутов и сравнить с реальностью.
>>> 34500000 / (1500000 / 32)
736
Ух, подумал, как они там не путаются? А вот как:
Например, в Токио в 1962 году существовал 41 маршрут, но до сегодняшних дней дожил только один.
Расстроился.
Согласно стратегии «x1» оценкой для числа должно быть само. Понятное, что никогда не будет больше, поэтому не может оказаться так, чтобы была больше. Следовательно наша оценка будет неприемлемой только в одном случае: если, то есть, окажется меньше, чем. Вероятность получить меньшее при нечетных не превосходит 50%, а при четных — равна им. Отсюда следует, что при использовании стратегии «x1» в очень длинной партии игр по крайней мере (примерно) половина сделанных оценок гарантированно окажутся приемлемыми, какой бы там сценарий ни уготовила судьба.
Вы здесь делаете нечестный трюк: исходите из того, что уже знаете N и по известному числу трамваев угадываете, какой приедет. И говорите, что назвав N вы в 50% случаев будете ошибаться не более, чем в два раза. И это верно, но только условие задачи обратное — надо по номеру трамвая угадать их количество.
В общем, как и некоторые другие комментаторы, я вам указываю на то, что вы решили не ту задачу, которая написана в условии.
Решение предлагаемое автором, будет оценено при собеседовании на должность, которая, например, предполагает использование и создание абстрактных математических моделей. Здесь важно уметь быстро «разродиться» таким решением.
На собеседованиях в компании, производящие продукт, для кандидата важнее уметь находить максимально точные решения с минимальными затратами времени. Просто замените «номер трамвая» на «версию пакета»/«число пользователей»/«размер целевой аудитории», и станет очевидно, что требуется не абстрактная модель, оперирующая конями в вакууме и многочисленными допущениями, а простые шаги гарантирующие достоверность результата. В стоячий трамвай, нужно, блин, зайти и посмотреть карту маршрутную карту. За движущимся трамваем нужно последовать вдоль путей до ближайшей остановки и посмотреть карту маршрутов там. Все.
Подобные задачи на собеседованиях призваны оценить Вашу способность находить оптимальное решение для нестандартных задач
Или применять стандартные академические знания к стандартным задачам в их бытовом звучании.
Одно из самых частых заблуждений. Когда ответ подразумевает математическое решение — это отражается в условиях задачи и входных данных.
Если при полностью размытых условиях, от вас требуется конкретное число — стоит задуматься, будет ли демонстрация академических знаний настолько увлекательной, что никто не заметит, что Вы пытаетесь решить совсем другую задачу.
В реальности, от кандидата требуется умение справляться с поставленной задачей адекватными методами. Желательно быстро и не напрягая окружающих. Т.е. умение понять ТЗ, придумать решение и выбрать оптимальные инструменты для реализации. Даже условие задачи полностью основано на «бытовой ситуации», чтобы набор текущий набор технических навыков кандидата никак не отражался на оценке этих качеств.
При k->∞ среднее (n1+n2+...+nk)/k->N/2. Поэтому наилучшей оценкой N будет 2*(n1+n2+...+nk)/k. А при k=1 это даёт n=N/2.
(n1/N1+n2/N2+...+nk/Nk)->1/2
N не обязательно фиксированное.
Это уже интересней. Наверное Вам тогда известен способ, как с помощью конструкции случайных отображений можно на их общем образе задать универсальную полумеру?
В любом случае критерий «хорошести» в статье другой и лично для меня доказательство того, что удвоенное среднее будет наилучшей оценкой, кажется технически почти неразрешимой проблемой даже для двух трамваев.
Кстати, если ответ считать приемлемым только тогда, когда он не отличается от истины более, чем в 1.2 (на 20%) как в большую, так и в меньшую стороны, то для одного увиденного трамвая наилучшей будет оценка "x1.2".
P.S. Тут уж как раз Вам нужно доказать, что Ваш критерий «хорошести» эквивалентен общепринятому.
от нас требуется указать некий коэффициент 0<γ≤1, такой что n=γN. Предположим, что мы выбрали γ<1/2. Это означает, что мы априорно считаем более вероятным, что n<1/2*N, что противоречит заданному в условиях задачи равномерному распределению номеров трамваев по интервалам. Аналогично рассуждая, исключаем γ>1/2, следовательно — γ=1/2.
байесовское рассуждениес тем фактом, что
Кстати, если ответ считать приемлемым только тогда, когда он не отличается от истины более, чем в 1.2 (на 20%) как в большую, так и в меньшую стороны, то для одного увиденного трамвая наилучшей будет оценка «x1.2»?
P(N | 17) = P(17 | N) * P(N) / P(17) -> min, то есть вероятность того, что в городе N трамваев при условии того, что мы увидели 17-й, равна вероятности увидеть 17-й трамвай при условии того, что в городе N трамваев, умножить на (априорную) вероятность того, что в городе N трамваев и поделить на вероятность увидеть 17-й трамвай.
Вероятность в знаменателе можно вычислить как P(17) = Sum{ P(17 | n) * P(n) } по всем возможным n, но она от N не зависит, поэтому достаточно найти N, минимизирующее числитель. А условную вероятность можно вычислить как P(17 | N) = Sum { P(17 | city) * P(city) } по всем городам, имеющим N трамваев.
Для сферического города в вакууме P(17 | city) = 1/N, N >= 17, тогда P(N | 17) = P(N)/N. При предположении, что количество городов с N трамваев падает с ростом N, получаем, что оптимальное N=17.
Для города на планете Земля надо в формулу подставить значения из справочника (если такой существует): P(N) — это количество городов, в которых N трамваев, делить на количество городов на Земле; P(17; city), наверно, можно оценить, как количество времени, которое 17-й маршрут проводит в городе за сутки, умножить на количество составов, поделить на общее количество времени, которое все трамваи города проводят за сутки.
Необязательно с равной вероятностью, достаточно, чтобы города выбирались случайно с заранее известным распределением вероятности
Да, не обязательно, но из текста
то есть вероятность того, что в городе N трамваев при условии того, что мы увидели 17-й, равна вероятности увидеть 17-й трамвай при условии того, что в городе N трамваев, умножить на (априорную) вероятность того, что в городе N трамваев и поделить на вероятность увидеть 17-й трамвай.следует, что в описанном случае города должны были выбираться с равной вероятностью, поэтому я так и написал.
Ваш текст можно изменить так, чтобы это предположение не было необходимым, но опять же — если статистику маршрутов по городам можно загуглить, то загуглить эту неизвестную нам плотность вероятности уже не получиться. К чему формула, если узнать из нее ничего не удасться?
Насколько я видел, вообще определение априорной вероятности в байесовской статистике для практически любой задачи является самым слабым местом: иногда ее можно задать «из общих соображений», но в общем случае непонятно, откуда ее брать. Например, Википедия упоминает deductive reasoning и principle of indifference, что является скорее философией, чем математикой. И для разных распределений можно получить практически произвольные результаты, в этом я с вами согласен.
Но с моей точки зрения, именно в этом ценность формулы: она показывает, что для точного решения задачи необходимо знать это распределение, и без него задачу невозможно формализовать в рамках статистики (но, конечно, можно в других рамках, например, теории игр, как вы делаете)
что для точного решения задачи необходимо знать это распределение, и без него задачу невозможно формализовать в рамках статистики
Могу я предложить вам еще одну задачку?
Пусть у вас есть монета, причем она несимметричная и о ней заведомо известно, что то ли орелом, то ли решкой она выпадает в два раза чаще, но которой из этих двух сторон — вы не знаете. Предположим, Вы подбрасываете эту монету ровно один раз, в результате чего она падает к вершу решкой. Какие выводы можно сделать? Случайность выбора монеты не предполагается.
Эти трамваи всех сбивают с толку.
Давайте попробуем переформулировать. В мешке некоторое (неизвестное, но конечное) количество пронумерованных шаров. Вы вытаскиваете оттуда шар с номером 17. Оцените максимальный номер N, какой есть в этом мешке, если известно, что: 1) количество шаров каждого номера одинаково и 2) номера идут подряд без пропуска.
Эти трамваи всех сбивают с толку
Я бы сказал, вскрывают наши стереотипы и показывают, как мало людей действительно понимают идеи, лежащие в основании математической статистики.
Давайте попробуем переформулировать. В мешке некоторое (неизвестное, но конечное) количество пронумерованных шаров. Вы вытаскиваете оттуда шар с номером 17— это совсем другая задача…
Спасибо за дискуссию.
Данная задача мне напомнила гораздо более приближеную к реальности задачу по оценке количества уникальных объектов и алгоритм hyper log log (на хабре было, рекомендую). Там похожим образом проводиться оценка количества элементов по небольшому количеству агрерированной информации. Для алгоритма достаточно нескольких килобайт памяти для того, чтобы оценить количество уникальных объектов (например, deviceId) с погрешностью в несколько процентов.
Итак, у нас есть следующая игра:
1) Нам выпадает число N. Распределение вероятностей N неизвестно.
2) Нам выпадает число X от 1 до N с равномерным распределением.
Нужно для каждого выпавшего X посчитать распределение вероятностей (апостериорное) возможных N.
Откуда можно найти 95%-процентный доверительный интервал для N и все такое.
Звучит как задача из матстатистики.
Вся проблема в том, что нам ничего не сказано про изначальное распределение вероятностей N на шаге 1, поэтому мы вынуждены его додумывать.
И тут нет никакого «естественного» ответа.
Например, вы не можете придумать равномерное распределения для N, ибо натуральных чисел счетное число.
Соответственно, от выбранного нами распределения вероятностей N на шаге 1 зависит ответ.
Я могу выбрать N, распределенное равномерно от 1 до 10^6, и получу одну задачу.
Или я могу сказать, что N равно 10^10 либо 10^10 + 1, и получу совершенно другую задачу.
И любой выбранный метод решения ошибется сколь угодно сильно.
Между этими «крайними» вариантами существует несчетное множество промежуточных.
Вывод — задача не полна и не имеет решения.
P.S.
Распределение вероятностей у меня здесь — это грубо говоря табличка, где каждому числу, которое можно выпасть, приписана вероятность выпадения.
Мехмат — хорошее место чтобы познакомится с математикой, я тоже там немного поучился. Мне кажется лучшее, что на мехмате прививается — это умение смотреть на любой изучаемый предмет, не как на законченное ортодоксальное учение, а как на некий образец мысли, кладезь идей, который вы можете использовать, чтобы построить какую-то свою теорию или создать свои рамки мышления. Используйте это и у вас без труда получится понять мою статью.
Кстати, в каких отношениях вы находитесь с логикой и мета-математикой?
Одна тривиальная, другая не имеет решений.
Выпадает N (распределение не известно), выпадает X от 1 до N (равномерно).
Задача 1:
Нужно по фиксированному X указать интервал, куда N попадает с вероятностью не ниже epsilon. То есть, выпал X, появляется некое новое апостериорное распределение вероятностей для N, нужно найти доверительный интервал для N.
Задача решения не имеет, согласно указанному мною выше.
Задача 2:
Нужно по X указать интервал, куда N будет попадать с вероятностью не ниже epsilon,
если мы будем генерировать N и X в большом числе экспериментов.
Задача решается тривиально.
При любом выпавшем N число X с вероятностью epsilon лежит в интервале от
от (1-epsilon)*N до N.
Соответственно, берем для N интервал от X до X/(1-epsilon) и не нужно ничего долго считать.
При любом выпавшем N метод работает одинаково, поэтому распределение N не имеет значения.
Суть в том, что в первой задаче рассматривается апостериорная вероятность, а во второй — обычная.
Отсюда разные вероятностные пространства и разные ответы.
Так вот кажется мне, что изначальная формулировка задачи содержит именно апостериорность.
Так что, может так случиться, что это вы решали не ту задачу.
Задача 2:
Нужно по X указать интервал, куда N будет попадать с вероятностью не ниже epsilon,
если мы будем генерировать N и X в большом числе экспериментов.
Близко, но не совсем так. Меня в статье интересовало другое утверждение.
Суть в том, что в первой задаче рассматривается апостериорная вероятность, а во второй — обычная.
Во второй задаче рассматривается тоже «необычная» вероятность. Она ближе всего к тому, что называли доверительной вероятностью, но все эти термины не важны.
Смотрите, k у меня обозначает номер наблюдаемого трамвая, N — неизвестное мне число маршрутов в текущем городе, f() — непрерывная монотонная функция на R+, f(k) я называю оценкой для N и считаю, что оценка оказалась приемлемой, если
(*) N/2≤f(k)≤2N. Пусть у нас есть две оценки f(k) и g(k), как их сравнить — какая лучше?
Наверное, если при каждом N вероятность того, что f(k) даст приемлемую оценку будет не меньше, чем вероятность быть приемлемой для g(k), то f() не хуже оценки g(). Однако здесь появляется проблема, что некоторые оценки слишком хорошо приспособлены для конкретных N (например константная f(k) = 5), которую я решил тем, что для f() и g() взял инфинум вероятности по всем N. Получился порядок сравнения. Так вот, в этом порядке сравнения оценок есть доминанта — оценка l(k)=2k, причем в задаче с фотопленкой при любом N она будет приемлемой с одной и той же вероятностью 3/4.
Не вижу, чтобы это последнее утверждение было каким-то очевидным, тривиальным или бессодержательным.
Вы взяли некую задачу и вроде как решили ее непростым путем.
Но собственно линейность f(k) уже почти вытекает из линейности границ интервала [N/2,2N].
А уже найти, каким линейным отображением отобразить отрезок [N/2,2N] так, чтобы пересечение с отрезком [0,N] было максимальным — тривиально.
Остается подумать о практических применениях всего этого.
Ибо формулировка достаточно странная.
Вы бы могли сделать эту статью полезнее, если бы подняли вопрос о априорной и апостериорной вероятности в задаче о трамвае.
Это и правда очень интересный и тонкий вопрос.
линейность f(k) уже почти вытекает из линейности границ интервала [N/2,2N].
А уже найти, каким линейным отображением отобразить отрезок [N/2,2N] так, чтобы пересечение с отрезком [0,N] было максимальным — тривиально
В математике много почти очевидных утверждений, которые очень трудно доказать, но я рад, что смог донести до вас свои мысли.
Вы бы могли сделать эту статью полезнее, если бы подняли вопрос о априорной и апостериорной вероятности в задаче о трамвае.
Это и правда очень интересный и тонкий вопрос.
Боюсь, в предложенных вами терминах эта задача не решается. Свою заслугу я вижу именно в том, что нашел рамки мышления, в которых она имеет разумный ответ, а отнюдь не в сложности или простоте формальных рассуждений.
Случайный трамвай посреди незнакомого города