Геометрическая вероятность - 3

[Gyros]

Задача:
Какова вероятность того, что выпуклый n-угольник с вершинами, случайно расположенными на окружности,
содержит ее центр?

Попытки решить:
Численно смоделировал в Maple для примерно 10 000 попыток, получил:
3-уг 0.125
4-уг 0.499
5-уг 0.687
6-уг 0.812
7-уг 0.890
Выглядит логично, чем больше точек, тем выше вероятность.
И, естественно, должна быть зависимость от n.

Долго думал над получением аналитического решения, пока не увидел в одном задачнике набросок решения.
Там задача переформулируется так:
Какова вероятность того, что эти точки можно накрыть дугой с углом $\alpha=2\pi\cdot t$, где $t\in[0, 0.5]$
Далее следуют рассуждения:
Имеется $n(n-1)$ способов выбрать левую и правую границу дуги.
Оставшиеся $(n-2)$ точки должны попасть между ними.
Получаем интеграл (перебираем все расстояния между границами):
$\int\limits_{0}^{t}n(n-1)a^{n-2}da=n \cdot t^{n-1}$

Для исходной задачи берем $t=\frac{1}{2}$.
В итоге ответ первоначальной задачи: $P(n)=1-\frac{n}{2^{n-1}}$

Теперь сам вопрос: вот это место "получаем интеграл" -? На основе чего?
Как тут увидеть теорему полной вероятности или интеграл от плотности вероятности?

[svv]

Gyros в сообщении #1552901 писал(а):

Численно смоделировал в Maple для примерно 10 000 попыток, получил:
3-уг 0.125

Для треугольника должно быть примерно $0.25$.

Gyros в сообщении #1552901 писал(а):

Имеется $n(n-1)$ способов выбрать левую и правую границу дуги.
Оставшиеся $(n-2)$ точки должны попасть между ними.
Получаем интеграл (перебираем все расстояния между границами):
$\int\limits_{0}^{t}n(n-1)a^{n-2}da=n \cdot t^{n-1}$

Это решение автор задачника назвал Solution b2.

Возьмём $m$ независимых равномерно распределённых на $[0;1]$ случайных величин $X_i, i=1...m$. Множество упорядоченных наборов их значений — единичный $m$-мерный гиперкуб $[0;1]^m$. Множество наборов с $\sum\limits_{i=1}^m X_i<a$, где (важно!) $a\in (0;1]$ — это $m$-симплекс, ограниченный $m$ гиперплоскостями $X_i=0$ и ещё одной $\sum\limits_{i=1}^m X_i=a$. Вероятность попадания в этот симплекс равна его объёму $\frac{a^m}{m!}$. Плотность вероятности суммы равна $\frac{a^{m-1}}{(m-1)!}$.

В нашем случае это $m=n-1$ ориентированных длин дуг $P_1P_2,\,P_2P_3,...,P_{n-1}P_n$ (делённых на $2\pi$), так что плотность вероятности их суммы равна $\frac{a^{n-2}}{(n-2)!}$. Теперь это надо проинтегрировать от $0$ до $t$ (всё в порядке — сначала продифференцировали, теперь интегрируем ). И умножить на $(n-2)!$, потому что мы нашли вероятность для одного конкретного порядка $P_2,...,P_{n-1}$ различимых промежуточных вершин между левой вершиной $P_1$ и правой вершиной $P_n,$ но тот же многоугольник получится при любой перестановке промежуточных вершин.

Предлагаемое автором Solution b1 намного проще:

Цитата:

$p(n,t)=n\cdot t^{n-1}$. Для левой точки имеется $n$ вариантов, при заданной левой точке, остальные точки (их $(n-1)$) должны попасть в отрезок длины $2\pi\cdot t$ при длине окружности $2\pi$.

[Gyros]

Спасибо svv

Цитата:

Для треугольника должно быть примерно $0.25$.

- да, конечно, это я описался

Цитата:

И умножить на $(n-2)!$...

- может умножить на $n! $ ?,
тогда $P(n)=\int\limits_{0}^{t}n! \cdot \frac{a^{n-2}}{(n-2)!}da$ и $(n-2)!$ в знаменателе сократится и придем к тому же интегралу, который написан в задачнике.

[svv]

Да, Вы правы, просто автор уже выделил множитель $n(n-1)$, равный числу вариантов выбора левой и правой вершин. Множитель этот понятен, и я предполагал, что мне нужно объяснить только "оставшуюся" часть выражения, поэтому умножал на число вариантов выбора только внутренних вершин. Конечно, надо просто сразу умножать на $n!$.

[Gyros]

Цитата:

$m$-симплекс, ограниченный $m$ гиперплоскостями $X_i=0$ и ещё одной $\sum\limits_{i=1}^m X_i=a$.

- а как этот симплекс представить?
Например, если $m=4$, то симплекс будет тетраэдром, который пересекает плоскость $\sum\limits_{i=1}^m X_i=a$?
Тогда объем какой части этого рассеченного тетраэдра брать? Или я что -то не то себе представляю..

[svv]

Случаи $m=2$ и $m=3$ показаны на картинке.
При $m=2$ "гиперкуб" — это квадрат, а та "гиперплоскость" — это синяя прямая. Она отсекает от него "симплекс", в данном случае это треугольник.
При $m=3$ "гиперкуб" — это куб, а "гиперплоскость" — это плоскость (в которой лежит синий треугольник). Тут отсекаемый ею симплекс — это тетраэдр.
Ну а в случае $m=4$ все размерности ещё на единичку больше, и представить это затруднительно (но, говорят, при правильной тренировке возможно).
Вершина $O$ на обеих картинках совпадает с началом координат.

[mihaild]

Если решать именно случай $t = \frac{1}{2}$, то можно подсмотреть доказательство теоремы Венделя и обойтись вообще без интегралов, явного вида распределений и т.д. - достаточно чтобы 1) совместное распределение было инвариантно относительно умножения на $-1$ и 2) любые две точки с вероятностью $1$ были линейно независимы.

(Примерное рассуждение)

Идея следующая: зафиксируем прямые, на которых лежат вершины, и для каждого набора прямых посчитаем вероятность того, что многоугольник не содержит центр окружности при условии, что каждая вершина попала на соответствующую прямую - т.е. при условии $\vec x_i = \pm \vec t_i$, где $t_i$ - константы. И внезапно оказывается, что вероятность того, что многоугольник при таком условии не содержит центр окружности, не зависит от расположения этих прямых.
Для двумерного случая это доказывается совсем просто: зафиксировав $\vec x_i$, будем двигать по окружности точку $\vec y$, и записывать, с какими из $\vec x_i$ она образует острый угол, а с какими тупой, пропуская точки, где $\vec y$ перпендикулярна какому-нибудь из $\vec x_i$. При фиксированном расположении $\vec x_i$ мы получим $2n$ разных вариантов остроты углов (прямые, перпендикулярные $\vec x_i$, разбивают окружность на $2n$ частей, и в каждой своя комбинация остроты углов). Таким образом, у нас есть при фиксированных знаках бывают $2n$ комбинаций из $2^n$ возможных, и многоугольник не содержит начала координат если одна из возможных координат - "все уголы острые". А теперь заметим, что все комбинации остроты равноправны, потому что любые две можно перевести одну в другую, отразив соответствующие $\vec x_i$, и значит при случайных знаках вероятность того, что нужная нам комбинация реализуется при каком-то $\vec y$ равна как раз $\frac{2n}{2^n}$.
Для произвольной размерности см. "A problem in geometric probability", J. G. Wendel.

[Gyros]

svv
Т.е. для случая $m=2$ объем этого синего треугольника равен $\frac{a^2}{2!}$.
Но для объема симплекса там же определитель в числителе. Как он сводится к $a^2$?
Т.е. этот треугольник - полквадрата. Эта "гиперплоскость" отсекает $a$ по каждой стороне $X_i=0$?


mihaild- Спасибо. На первый взгляд это для меня новый подход. Надо будет переварить.

[svv]

Мы используем первую формулу отсюда:
$V = \frac{1}{m!} \left|\det\begin{pmatrix}v_1-v_0 && v_2-v_0 && \cdots && v_m-v_0\end{pmatrix}\right|$
Так как симплекс строится от начала координат, $v_0=0$. В $j$-м столбце определителя записаны сверху вниз координаты $j$-го из $m$ векторов, на которых построен симплекс (начало каждого из векторов в начале координат, а конец — в какой-то из остальных вершин симплекса). Определитель имеет вид
$\begin{vmatrix}a&0&\cdots&0\\0&a&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&a\end{vmatrix}=a^m$
А объём нашего симплекса $V=\frac{a^m}{m!}$.
Например, при $m=2$ векторы, на которых построен симплекс, равны $\begin{pmatrix}a\\0\end{pmatrix}$ и $\begin{pmatrix}0\\a\end{pmatrix}$, поэтому
$V=\frac 1{2!}\begin{vmatrix}a&0\\0&a\end{vmatrix}=\frac{a^2}2$

-- Пн апр 18, 2022 21:56:08 --

Gyros в сообщении #1553017 писал(а):

Т.е. этот треугольник - полквадрата. Эта "гиперплоскость" отсекает $a$ по каждой стороне $X_i=0$?

Да, половина квадрата со стороной $a\leqslant 1$.