Вероятность/Задачи/Curse-of-dimensionality — различия между версиями

Версия 20:23, 24 декабря 2014

@@ Строка 7: / Строка 7: @@
 </m>
+==Решение==
+<m>
+Найдем функцию распределения расстояния от центра сферы до случайно вброшенной в сферу точки.
+$$P(\xi < x) = \frac{\text{V (сферы радиуса $x$ в $\mathbb{R}$)}}{\text{V (сферы радиуса $1$ в $\mathbb{R}^d$)}} = \frac{x^d}{1^d} = x^d$$
+Теперь найдем функцию распределения расстояния до ближайшей из $N$ точек.
+$$P(\min(\xi_1,\dots,\xi_N) < x) = 1 - P(\min(\xi_1,\dots,\xi_N) \geq x) = 1 - P(\xi \geq x)^N = 1 - (1 - P(\xi < x))^N = 1 - (1 - x^d)^N$$
+Теперь найдем медиану. Медиана - это $0.5$-квантиль, то есть точка, в которой функция распределения равна $0.5$.
+$$1 - (1 - x_{med}^d)^N = 0.5$$
+$$x_{med}^d = 1 - (\frac{1}{2})^{\frac{1}{N}}$$
+$$x_{med} = (1 - (\frac{1}{2})^{\frac{1}{N}})^{\frac{1}{d}}$$
+</m>
 [[Категория:Предложенные студентами задачи]]