На отрезок бросили мильён точек случайным образом.
После этого от каждой точки закрасили до ближайшей.
Для каждой точки это будет, очевидно, маленький отрезочек либо влево, либо вправо.
Некоторые отрезки покрасятся один раз, некоторые дважды, некоторые не покрасятся вовсе.
1) Какой процент маленьких отрезочков будет закрашен? (Это задачка попроще).
2) Какая доля длины исходного отрезка будет закрашена? (Это посложнее)
Здравствуйте, Pushkin, Вы писали:
P>На отрезок бросили мильён точек случайным образом. P>После этого от каждой точки закрасили до ближайшей.
Судя по всему, от каждой брошенной точки?
Если расстояние до обоих соседей одинаково, какой отрезок закрашивать? Никакой, по-видимому...
P>Для каждой точки это будет, очевидно, маленький отрезочек либо влево, либо вправо. P>Некоторые отрезки покрасятся один раз, некоторые дважды, некоторые не покрасятся вовсе.
P>1) Какой процент маленьких отрезочков будет закрашен? (Это задачка попроще). P>2) Какая доля длины исходного отрезка будет закрашена? (Это посложнее)
Насколько я понимаю, строгого ответа не существует?
Если мы рассмотрим вариант с двумя точками (они делят отрезок на 3 части), то, в зависимости от того, как упали точки, мы получим:
.Х.____.Х.
.Х.ХХ.___.
.____.Х._.
.__.__.__.
Соответственно количесво вариантов будет расти с ростом количества точек...
Здравствуйте, Alik, Вы писали:
P>>На отрезок бросили мильён точек случайным образом. P>>После этого от каждой точки закрасили до ближайшей. A>Судя по всему, от каждой брошенной точки?
Да, от каждой. Либо влево либо вправо.
A>Если расстояние до обоих соседей одинаково, какой отрезок закрашивать? Никакой, по-видимому...
Не бывает такого. Невероятно это. Float числа! Но если случится, можешь покрасить любой
A>Насколько я понимаю, строгого ответа не существует? A>Если мы рассмотрим вариант с двумя точками A>Соответственно количесво вариантов будет расти с ростом количества точек...
Вся прелесть задачи в большом количестве точек. Для них ответ вполне точный. Обычная ситуация: 1 — легко, 2 — труднее, 3 — совсем трудно, 4 — ну его на фиг ... 10 — полный ужас ... 100000 — снова всё легко и замечательно
Здравствуйте, Pushkin, Вы писали:
A>>Насколько я понимаю, строгого ответа не существует?
Прогу написать 5 минут.
Для M=100 точек, кидаемых на массив из, скажем, N=100000 байт (или бит).
С рандомом.
Ты всё время будешь получать примерно одно и то же число.
Чем больше M и N тем точнее (надо только соблюдать условие M<<N)
Здравствуйте, Pushkin, Вы писали:
P>На отрезок бросили мильён точек случайным образом. P>1) Какой процент маленьких отрезочков будет закрашен? (Это задачка попроще).
Ну, так как от любой точки отрезок с равной вероятностью падает влево или вправо, то вероятность, что отрезок не покрашен обоими соседними точками — 1/4. Ответ — 75%
P>2) Какая доля длины исходного отрезка будет закрашена? (Это посложнее)
Очевидно, непокрашенные отрезочки побольше. Но вот наколько в среднем?
Мне почему-то кажется, что несущественно, т.е. ответ — те же 75%. Но доказать не могу
Здравствуйте, Pushkin, Вы писали:
P>Здравствуйте, Pushkin, Вы писали:
A>>>Насколько я понимаю, строгого ответа не существует?
P>Прогу написать 5 минут. P>Для M=100 точек, кидаемых на массив из, скажем, N=100000 байт (или бит). P>С рандомом. P>Ты всё время будешь получать примерно одно и то же число. P>Чем больше M и N тем точнее (надо только соблюдать условие M<<N)
А, так нас интересует мат. ожидание? Так бы и говорили.
Здравствуйте, mihoshi, Вы писали:
M>Ну, так как от любой точки отрезок с равной вероятностью падает влево или вправо, то вероятность, что отрезок не покрашен обоими соседними точками — 1/4. Ответ — 75%
Если из точки идёт отрезок вправо, то из точки справа от неё более вероятен отрезок влево, чем вправо.
P>>2) Какая доля длины исходного отрезка будет закрашена? (Это посложнее)
M>Очевидно, непокрашенные отрезочки побольше.
Факт!
M>Мне почему-то кажется, что несущественно, т.е. ответ — те же 75%. Но доказать не могу
А ты прогу напиши и проверь. Заодно убедишься в неверности своего первого ответа
Здравствуйте, Pushkin, Вы писали:
P>Здравствуйте, mihoshi, Вы писали:
M>>Ну, так как от любой точки отрезок с равной вероятностью падает влево или вправо, то вероятность, что отрезок не покрашен обоими соседними точками — 1/4. Ответ — 75%
P>А ты прогу напиши и проверь. Заодно убедишься в неверности своего первого ответа
Ах да, конечно, вероятности зависимы.
Если рассмотреть длины трех соседних отрезков, то все 6 вариантов их порядков (т.е. левый самый длинный, потом правый, потом средний и т.п.), то в четырех из них средний будет закрашен. Присчем все эти 6 вариантов равновероятны. Так что ответ —
2/3
M>Ах да, конечно, вероятности зависимы. M>Если рассмотреть длины трех соседних отрезков, то все 6 вариантов их порядков (т.е. левый самый длинный, потом правый, потом средний и т.п.), то в четырех из них средний будет закрашен. Присчем все эти 6 вариантов равновероятны. Так что ответ — M>2/3
Гениально!
Но это ответ на более простой вопрос — о доле закрашенных отрезков по ШТУКАМ.
По ДЛИНЕ всё сложнее — незакрашенные в среднем более длинные.
PS
На самом деле для доли по длине у меня нет простого решения. Т.е. оно, есть, я в нём вполне уверен, и ответ подтверждается численным моделированием, но ... это листок А4 мелким почерком... Буду очень рад, если кто найдёт простой способ. Хотя, может оказаться и так, что его нет.
Здравствуйте, mihoshi, Вы писали:
M>Ах да, конечно, вероятности зависимы. M>Если рассмотреть длины трех соседних отрезков, то все 6 вариантов их порядков (т.е. левый самый длинный, потом правый, потом средний и т.п.), то в четырех из них средний будет закрашен. Присчем все эти 6 вариантов равновероятны. Так что ответ — M>2/3
Если учесть "краевые" эффекты, то можно получить более точную формулу: (2*N+1)/(3*(N+1)), где N — кол-во точек. Правда, на "мильёне" точек разница несуществена.
Здравствуйте, Pushkin, Вы писали:
P>По ДЛИНЕ всё сложнее — незакрашенные в среднем более длинные.
P>PS P>На самом деле для доли по длине у меня нет простого решения. Т.е. оно, есть, я в нём вполне уверен, и ответ подтверждается численным моделированием, но ... это листок А4 мелким почерком... Буду очень рад, если кто найдёт простой способ. Хотя, может оказаться и так, что его нет.
По-моему, это можно свести к следующей задаче. Из кучи наших отрезков берем случайно три. Отношение незакрашенной части к закрашенной равно матожиданию отношения длины большего из этих трех отрезков к сумме длин всех трех.
Здравствуйте, mihoshi, Вы писали:
M>По-моему, это можно свести к следующей задаче. Из кучи наших отрезков берем случайно три. Отношение незакрашенной части к закрашенной равно матожиданию отношения длины большего из этих трех отрезков к сумме длин всех трех.
Ну в общем да, наверное можно и так. Только поправочка:
отношение незакрашенной части всего отрезка ко всему отрезку равно отношению большего к сумме трёх
или
отношение незакрашенной части всего отрезка к закрашенной равно отношению большего к сумме двух меньших
Но я на самом деле искал матожидание длины отрезка при условии, что он не наибольший из трёх. Интегрировал
M>Кстати, какое число получилось у тебя? Красивое?
Закачаешься
Скажем так: рациональное, с весьма нетривиальным знаменателем.
Здравствуйте, Pushkin, Вы писали:
P>На отрезок бросили мильён точек случайным образом. P>После этого от каждой точки закрасили до ближайшей. P>Для каждой точки это будет, очевидно, маленький отрезочек либо влево, либо вправо. P>Некоторые отрезки покрасятся один раз, некоторые дважды, некоторые не покрасятся вовсе.
P>1) Какой процент маленьких отрезочков будет закрашен? (Это задачка попроще). P>2) Какая доля длины исходного отрезка будет закрашена? (Это посложнее)
Не хочется, чтобы задача сгинула без ответа, поэтому напишу.
На первый вопрос уже дали простое и красивое решение — любой отрезочек с вероятностью 1/3 больше своих двух соседей (из трёх кто-то должен быть больше) и значит для каждого отрезка вероятность остаться незакрашенным 1/3 и доля таких значит 1/3.
Второй вопрос сложнее, потому что играет роль распределение длин. Но вы ответом полюбуйтесь. Всего закрашенно 7/18 отрезка. Ну не чудо ли?! Откуда бы взяться такому крокодилу?
Чтобы не растерять читателей, я не буду подробно выкладки писать — кто хочет сам легко повторит.
Сначала надо найти распределение для длины одного отрезка, т.е. коэффициент между вероятностью для длины попасть в интервал dx и самим dx. Легко видеть, что это спадаюшая экспонента.
dP=N*exp(-x*N)
Теперь для каждого отрезочка рассмотрим величину
L = x * б(x<x1 || x<x2),
где x-длина этого отрезка,
x1 — длина отрезка слева,
x2 — длина отрезка справа,
а функция
б()
отлична от нуля только при выполнении условия в своих скобках
Сумма именно этих величин по всем отрезкам даст закрашенную длину.
Если мы посчитаем её среднюю величину и умножим на N, получим примерно то же самое.
Итак надо посчитать среднее от величины L(x,x1,x2) по совместному распределению x,x1,x2.
Тут следующая важная точка — совместное распределение можно считать просто произведением распределений, так как величины x,x1,x2 практически независимы. Действительно, если отрезков всего два, то большой первый заставляет второй быть маленьким. А если отрезков много, то выбросы делятся на всех и соседи независимы.
Итак осталось просто взять интеграл по трём переменным от произведения трёх экспонент и одной линейной функции по довольно хитрой области. Он берётся без больших сложностей, но с некоторой морокой, так что можете поверить мне на слово, он равен 7/18/N.
В таких задачах, конечно, больше всего потрясает тот момент, когда ответы, полученные таким вот словоблудием и численным экспериментом точнёхонько совпадают.
...
P>Итак осталось просто взять интеграл по трём переменным от произведения трёх экспонент и одной линейной функции по довольно хитрой области. Он берётся без больших сложностей, но с некоторой морокой, так что можете поверить мне на слово, он равен 7/18/N.
P>В таких задачах, конечно, больше всего потрясает тот момент, когда ответы, полученные таким вот словоблудием и численным экспериментом точнёхонько совпадают.
Евгений