Brain-teaser: Какова ожидаемая длина последовательности iid, которая монотонно увеличивается при получении из равномерного распределения [0,1]?

Это вопрос интервью для позиции количественного аналитика, о котором сообщается здесь . Предположим, что мы рисуем из равномерного распределения а ничьи идентифицированы, какова ожидаемая длина монотонно увеличивающегося распределения? Т.е. мы прекращаем рисование, если текущее рисование меньше или равно предыдущему.$[0,1]$

Я получил первые несколько: \ Pr (\ text {length} = 2) = \ int_0 ^ 1 \ int_ {x_1} ^ 1 \ int_0 ^ {x_2} \ mathrm {d} x_3 \, \ mathrm {d} x_2 \, \ mathrm {d} x_1 = 1/3 \ Pr (\ text {length} = 3) = \ int_0 ^ 1 \ int_ {x_1} ^ 1 \ int_ {x_2} ^ 1 \ int_0 ^ {x_3} \ mathrm {d} x_4 \, \ mathrm { d} x_3 \, \ mathrm {d} x_2 \, \ mathrm {d} x_1 = 1/8

но мне все труднее вычислять эти вложенные интегралы, и я не получаю «трюк» для обобщения в $\Pr(\text{length} = n)$ . Я знаю, что окончательный ответ структурирован

Есть идеи, как ответить на этот вопрос?

Вот несколько общих советов по решению этого вопроса:

У вас есть последовательность непрерывных случайных величин IID, что означает, что они являются взаимозаменяемыми . Что это означает о вероятности получения определенного порядка для первых $n$ значений? Исходя из этого, какова вероятность получения возрастающего порядка для первых $n$ значений? Это можно выяснить, не интегрируя по распределению основных случайных величин. Если вы сделаете это хорошо, вы сможете получить ответ без какого-либо предположения о равномерном распределении - т.е. вы получите ответ, который применим для любых заменяемых последовательностей непрерывных случайных величин.

Вот полное решение ( не смотрите, если вы должны выяснить это самостоятельно ):

Пусть - ваша последовательность независимых непрерывных случайных величин, и пусть - количество увеличивающихся элементов в начале последовательности. Поскольку это непрерывные взаимозаменяемые случайные величины, они почти наверняка не равны друг другу, и любой порядок одинаково вероятен, поэтому имеем: (Обратите внимание, что этот результат справедлив для любой последовательности IID непрерывных случайных величин; они не должны иметь равномерное распределение.) Таким образом, случайная величина имеет функцию вероятности массы$U_1, U_2, U_3, \cdots \sim \text{IID Continuous Dist}$$N \equiv \max \{ n \in \mathbb{N} | U_1 < U_2 < \cdots < U_n \}$

$$\mathbb{P}(N \geqslant n) = \mathbb{P}(U_1 < U_2 < \cdots < U_n) = \frac{1}{n!}.$$ $N$ $$p_N(n) = \mathbb{P}(N=n) = \frac{1}{n!} - \frac{1}{(n+1)!} = \frac{n}{(n+1)!}.$$ Вы заметите, что этот результат соответствует значениям, которые вы вычислили, используя интеграцию по базовым значениям. (Эта часть не нужна для решения; она включена для полноты.) Используя известное правило для ожидаемого значения неотрицательной случайной величины , мы имеем: Еще раз отметим, что в нашей работе нет ничего, что использовало бы базовое равномерное распределение. Следовательно, это общий результат, который применим к любой заменяемой последовательности непрерывных случайных величин. $$\mathbb{E}(N) = \sum_{n=1}^\infty \mathbb{P}(N \geqslant n) = \sum_{n=1}^\infty \frac{1}{n!} = e - 1 = 1.718282.$$

Некоторые дальнейшие идеи:

Из вышеприведенной работы мы видим, что этот результат распределения и полученное ожидаемое значение не зависят от базового распределения, если оно является непрерывным распределением. Это на самом деле неудивительно, если учесть тот факт, что каждая непрерывная скалярная случайная величина может быть получена путем монотонного преобразования равномерной случайной величины (причем преобразование является ее квантовой функцией). Поскольку монотонные преобразования сохраняют порядок рангов, рассмотрение вероятностей упорядочения произвольных непрерывных случайных величин IID аналогично рассмотрению вероятностей упорядочения равномерных случайных величин IID .

Другой метод решения, который дает вам решение для более общего случая.

Предположим, что является ожидаемой длиной монотонной последовательности , такой, что . Значение, которое мы хотим вычислить, равно . И мы знаем . Кондиционирование на следующем значении,$F(x)$$\{x_1, x_2, ...\}$$x\leq x_1\leq x_2\leq\cdots$$F(0)$$F(1)=0$

где - плотность U [0,1]. Так$\pi(y)=1$

Решая с граничным условием , получаем . Следовательно, .$F(1)=0$$F(x) = e^{(1-x)}-1$$F(0)=e-1$

Еще один метод решения - вычислить интеграл напрямую.

Вероятность генерации последовательности, чья возрастающая часть имеет длину равна , где .$\geq n$$f^n(0)$$f^n(x) = \int_{x}^{1}\int_{x_1}^{1}\int_{x_2}^{1}...\int_{x_{n-2}}^{1}\int_{x_{n-1}}^{1}dx_ndx_{n-1}...dx_2dx_1$

Что нам нужно сделать, это вычислить .$f^n(0)$

Если вы попытаетесь вычислить первые несколько , возможно, вы обнаружите, что$f^n(x)$$f^n(x) = \sum_{t=0}^n \dfrac{(-x)^t}{t!(n-t)!}$

Базовый случай: когда ,$n=1$$f^1(x) = \sum_{t=0}^1 \dfrac{(-x)^t}{t!(n-t)!}=1-x=\int_{x}^{1}dx_1$

Индуктивная гипотеза: когда ,$n=k$$f^n(x) = \sum_{t=0}^k \dfrac{(-x)^t}{t!(k-t)!}\text{ , for }k \geq 1$

Шаг индукции: когда ,$n = k+1$

$\ \ \ \ \ f^{n}(x) = f^{k+1}(x) = \int_{x}^{1}f^{k}(x^*)dx^*$

$=\int_{x}^{1}\sum_{t=0}^{k} \dfrac{(-x^*)^t}{t!(k-t)!}dx^*$

$=\sum_{t=0}^{k} \dfrac{-(-x^*)^{t+1}}{t!(k-t)!\times(t+1)}\Biggr|_{x}^{1}\\=\sum_{t=0}^{k} \dfrac{-(-x^*)^{t+1}}{(t+1)!(k-t)!}\Biggr|_{x}^{1}$

$=\sum_{t=1}^{k+1} \dfrac{-(-x^*)^{t}}{t!(k-t+1)!}\Biggr|_{x}^{1}$

$=\sum_{t=1}^{k+1} \dfrac{(-1)^{t+1}}{t!(k-t+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\sum_{t=1}^{k+1} \dfrac{(-1)^{t+1}C_t^{k+1}}{(k+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\dfrac{1}{(k+1)!}+\sum_{t=0}^{k+1} \dfrac{(-1)^{t+1}C_t^{k+1}}{(k+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\dfrac{1}{(k+1)!}-\dfrac{(1-1)^{k+1}}{(k+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\sum_{t=0}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

По математической индукции предположение верно.

Таким образом, мы получаем, что$f^n(0)=\dfrac{1}{n!}$

Итак,$E(length)=\sum_{n=1}^{\infty} Pr(length\geq n)=\sum_{n=1}^{\infty} \dfrac{1}{n!}=e-1$