Непр. упаковывание (S. Ross, Stochastic Processes, 1.20)

[id]

Решаю задачку из вышеупомянутой книги, не сходится.

Рассмотрим интервал $(0,x)$ на котором равномерно распределены точки $X:=\{ x_i \}_{i=1}^{\infty}$. Случайно выберем одну из них такую, что $x_i<x-1$ и построим интервал $I_1:= (x_i,x_i+1) \subset (0,x)$. Обозначим выбранную левую точку через $X_1$.
Далее, если уже построены интервалы $I_1,\dots,I_n$, случайно выберем следующую точку $y$ из $X$. Если удается построить интервал с левой точкой $y$ (лежащий внутри $(0,x)$ и не пересекающий предыдущие интервалы), то обозначим его $I_{n+1}$ (а выбранную левую точку $y$ - через $X_{n+1}$). Если нет - выбираем следующую точку из $X$.
Обозначим через $M(x)$ ожидание $\mathbb{E} N(x)$, где $N(x)$ - число интервалов, которое удалось запаковать в $(0,x)$ процедурой выше.

Требуется показать, что $M(x)=0, x<1$;
$M(x) = 1 + \frac 2 {x-1} \int\limits_0^{x-1} M(y) dy, x>1$

У меня получилось несколько другое уравнение, а именно:
Рассмотрим $\mathbb{E} ( N(x) | X_1=y)$. Тогда $\int\limits_{B} \mathbb{E} ( N(x) | X_1=y) \frac 1 {x-1} dy = \int\limits_{\{\omega: X_1 \in B\}} N(x) dP$. Положим $B:=(0,x-1)$; тогда $\mathbb{E} ( N(x) ) = \frac 1 {x-1} \int\limits_{0}^{x-1} \mathbb{E} ( N(x) | X_1=y) dy$.
Мне кажется, что $\mathbb{E} ( N(x) | X_1=y) = 1+\mathbb{E} ( N(x-y-1)) $ (но я это строго не доказывал). Тогда $\mathbb{E} ( N(x) ) = 1+\frac 1 {x-1} \int\limits_{0}^{x-1} \mathbb{E} N(t) dt$

Что неверно?

[Хорхе]

id в сообщении #349828 писал(а):

Рассмотрим интервал $(0,x)$ на котором равномерно распределены точки $X:=\{ x_i \}_{i=1}^{\infty}$. Случайно выберем одну из них такую[...]

Что в данном случае значит "случайно"?

[id]

Да, в данном месте "случайно" может быть и лишнее. Вообще, счетное множество $X$ тут тоже лишнее. Неверно перевел условие, пожалуй.

Важно, что $P(y \leqslant t)$, где $y$ - координата выбираемой точки, - равномерное распределение на $(0,x-1)$

Оригинал:

Цитата:

Consider the interval $(0,x)$ and suppose that we pack in this interval random unit intervals, whose left-hand points are all uniformly distributed over $(0,x-1)$ as follows:
Let the first such interval be $I_1$. If $I_1,\dots,I_n$ have already been packed in the interval, then the next random unit interval will be packed if it does not intersect any of the intervals $I_1,\dots,I_n$ and will be denoted by $I_{n+1}$.
If it does intersect - we disregard it and look at the next random interval. The procedure is continued until there's no more room for addtional unit intervals.

Let $N(x)$ denote the number of unit intervals packed into $[0,x]$ by this method.

[Alexey1]

После того, как Вы выбрали первый интервал $(y;y+1)$ у Вас остаётся две области $(0;y-1)$ и $(y+1;x-1)$, то есть $E[N(x)|X_1=y]=1+E[N(y)]+E[N(x-y-1)]$.
Таким образом,
$\int_0^{x-1}E[N(y)]dy=\int_{0}^{x-1}E[N(t)]dt$ и $\int_0^{x-1}E[N(x-y-1)]dy=-\int_{x-1}^{0}E[N(t)]dt=\int_{0}^{x-1}E[N(t)]dt$.

[id]

Alexey1
Вроде как да, оно. Только разве

Цитата:

$E[N(x)|X_1=y]=1+E[N(y-1)]+E[N(x-y-2)]$

а не
$E[N(x)|X_1=y]=1+E[N(y)]+E[N(x-y-1)]$?

Если подставить последнее, то вроде все сходится.

[Alexey1]

Точно, я перепутал определение $N(x)$ и $N(x-1)$ (исправил).

[id]

Теперь сходится.
Спасибо!