Casse-tête: Quelle est la longueur attendue d'une séquence iid qui augmente de façon monotone lorsqu'elle est tirée d'une distribution uniforme [0,1]?

Il s'agit d'une question d'entrevue pour un poste d'analyste quantitatif, rapportée ici . Supposons que nous dessinons à partir d'une distribution uniforme et que les tirages soient iid, quelle est la longueur attendue d'une distribution augmentant de façon monotone? C'est-à-dire que nous arrêtons de dessiner si le tirage actuel est inférieur ou égal au tirage précédent.$[0,1]$

J'ai obtenu les premiers: \ 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

mais je trouve le calcul de ces intégrales imbriquées de plus en plus difficile et je n'ai pas le "truc" pour généraliser à $\Pr(\text{length} = n)$ . Je sais que la réponse finale est structurée

Des idées sur la façon de répondre à cette question?

Voici quelques conseils généraux pour résoudre cette question:

Vous disposez d'une séquence de variables aléatoires IID continues, ce qui signifie qu'elles sont échangeables . Qu'est-ce que cela implique sur la probabilité d'obtenir un ordre particulier pour les n premières $n$valeurs? Sur cette base, quelle est la probabilité d'obtenir un ordre croissant pour les n premières $n$valeurs? Il est possible de comprendre cela sans intégrer la distribution des variables aléatoires sous-jacentes. Si vous le faites bien, vous pourrez dériver une réponse sans aucune hypothèse d'une distribution uniforme - c'est-à-dire que vous obtenez une réponse qui s'applique à toutes les séquences échangeables de variables aléatoires continues.

Voici la solution complète ( ne regardez pas si vous êtes censé le découvrir vous-même ):

Soit votre séquence de variables aléatoires continues indépendantes, et soit soit le nombre d'éléments croissants au début de la séquence. Comme ce sont des variables aléatoires interchangeables continues, elles sont presque sûrement inégales les unes aux autres, et tout ordre est également probable, nous avons donc: (Notez que ce résultat est valable pour toute séquence IID de variables aléatoires continues; elles n'ont pas besoin d'avoir une distribution uniforme.) Ainsi, la variable aléatoire a une fonction de masse de probabilité$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)!}.$$ Vous remarquerez que ce résultat correspond aux valeurs que vous avez calculées en utilisant l'intégration sur les valeurs sous-jacentes. (Cette partie n'est pas nécessaire pour la solution; elle est incluse pour être complète.) En utilisant une règle bien connue pour la valeur attendue d'une variable aléatoire non négative , nous avons: Notez encore qu'il n'y a rien dans notre travail qui utilise la distribution uniforme sous-jacente. Il s'agit donc d'un résultat général qui s'applique à toute séquence échangeable de variables aléatoires continues. $$\mathbb{E}(N) = \sum_{n=1}^\infty \mathbb{P}(N \geqslant n) = \sum_{n=1}^\infty \frac{1}{n!} = e - 1 = 1.718282.$$

Quelques informations supplémentaires:

D'après les travaux ci-dessus, nous voyons que ce résultat de distribution et la valeur attendue qui en résulte ne dépendent pas de la distribution sous-jacente, tant qu'il s'agit d'une distribution continue. Ce n'est vraiment pas surprenant une fois que nous considérons le fait que chaque variable scalaire aléatoire continue peut être obtenue via une transformation monotone d'une variable aléatoire uniforme (la transformation étant sa fonction quantile). Étant donné que les transformations monotones préservent l'ordre de classement, l'examen des probabilités d'ordonnances de variables aléatoires continues IID arbitraires revient à examiner les probabilités d'ordonnances de variables aléatoires uniformes IID .

Une autre méthode de résolution qui vous apporte la solution pour un cas plus général.

Supposons que soit la longueur attendue d'une séquence monotone , telle que . La valeur que nous voulons calculer est . Et nous savons que . Conditionner sur la valeur suivante,$F(x)$$\{x_1, x_2, ...\}$$x\leq x_1\leq x_2\leq\cdots$$F(0)$$F(1)=0$

où est la densité U [0,1]. Alors$\pi(y)=1$

En résolvant avec la condition aux limites , on obtient . D'où .$F(1)=0$$F(x) = e^{(1-x)}-1$$F(0)=e-1$

Une autre méthode de résolution consiste à calculer directement l'intégrale.

La probabilité de générer une séquence dont la partie croissante a une longueur de est , où .$\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$

Ce que nous devons faire est de calculer .$f^n(0)$

Si vous essayez de calculer les premiers , vous constaterez peut-être que$f^n(x)$$f^n(x) = \sum_{t=0}^n \dfrac{(-x)^t}{t!(n-t)!}$

Cas de base: lorsque ,$n=1$$f^1(x) = \sum_{t=0}^1 \dfrac{(-x)^t}{t!(n-t)!}=1-x=\int_{x}^{1}dx_1$

Hypothèse inductive: lorsque ,$n=k$$f^n(x) = \sum_{t=0}^k \dfrac{(-x)^t}{t!(k-t)!}\text{ , for }k \geq 1$

Étape inductive: lorsque ,$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)!}$

Par induction mathématique, l'hypothèse est vraie.

Ainsi, nous obtenons que$f^n(0)=\dfrac{1}{n!}$

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