Supposons que sont des variables aléatoires iid. Quand la séquence devrait-elle diminuer pour la première fois?

10

Comme suggéré dans le titre. Supposons que sont des variables aléatoires iid continues avec pdf . Considérons l'événement que , , donc est lorsque la séquence diminue pour la première fois. Alors quelle est la valeur de ? $X_1, X_2, \dotsc, X_n$ $f$ $X_1 \leq X_2 \dotsc \leq X_{N-1} > X_N$ $N \geq 2$ $N$ $E[N]$

J'ai d'abord essayé d'évaluer . J'ai De même, j'ai obtenu . Quand deviens grand, le calcul devient plus compliqué et je ne trouve pas le motif. Quelqu'un peut-il suggérer comment je dois procéder? $P[N = i]$

\begin{aligned} P [N = 2] & = \int_{- \infty}^{\infty} f (x) F (x) d x \\ = \frac{F (x)^{2}}{2} |_{- \infty}^{\infty} \\ = \frac{1}{2} \\ P [N = 3] & = \int_{- \infty}^{\infty} f (x) \int_{x}^{\infty} f (y) F (y) d y d x \\ = \int_{- \infty}^{\infty} f (x) \frac{1 - F (x)^{2}}{2} d x \\ = \frac{F (x) - F (x)^{3} / 3}{2} |_{- \infty}^{\infty} \\ = \frac{1}{3} \end{aligned}

$\begin{align*} P[N = 2] & = \int_{-\infty}^{\infty} f(x)F(x)dx \\ & = \frac{F(x)^2}{2}\Large|_{-\infty}^{\infty} \\ & = \frac{1}{2} \\ P[N = 3] & = \int_{-\infty}^{\infty} f(x)\int_x^{\infty}f(y)F(y)dydx \\ & = \int_{-\infty}^{\infty}f(x)\frac{1-F(x)^2}{2}dx \\ & = \frac{F(x)-F(x)^3/3}{2}\Large|_{-\infty}^{\infty} \\ & = \frac{1}{3} \end{align*}$

P [N = 4] = \frac{1}{8}

$P[N = 4] = \frac{1}{8}$

i

$i$

probability self-study iid Hao le chou
la source

Est-ce une question d'un cours ou d'un manuel? Si oui, veuillez ajouter la [self-study]balise et lire son wiki .

Silverfish

1

Un soupçon. Considérez les rangs, qui devraient être permutés au hasard. Il y en adisposition des rangs . Il n'y a qu'une seule permutation dans laquelle les augmentent tous. Pour il y a observations qui ne sont pas le maximum, que nous pouvons ensuite retirer et placer à la fin pour générer une séquence qui augmente jusqu'à l'avant-dernière position, puis diminue. D'où la probabilité que cela soit sur ...? Cela devrait vous trier avec les , et que vous avez trouvés et vous donner une formule simple pour le généraliser. La somme est assez simple.

n!

$n!$

1, 2, \dots, n

$1, 2, \dots, n$

X_{i}

$X_i$

n \geq 2

$n \geq 2$

n - 1

$n-1$

n - 1

$n-1$

1 / 2

$1/2$

1 / 3

$1/3$

1 / 8

$1/8$

Silverfish

(Et si vous ne pouvez pas deviner le résultat de la série, vous additionnerez pour trouver la moyenne, peut-être devriez-vous en faire une simulation. Vous reconnaîtrez les deux premières décimales.)

Silverfish

C'est un problème de l'examen que j'ai passé aujourd'hui. Merci pour l'astuce, maintenant j'ai compris comment le résoudre.

Hao The Cabbage

2

stats.stackexchange.com/questions/51429/… est essentiellement un doublon. Bien qu'il ne s'agisse que d'une distribution uniforme, il est presque trivial de montrer que les deux questions sont équivalentes. (Une façon: appliquer la transformation intégrale de probabilité au .)

X_{i}

$X_i$

whuber

9

Si est une séquence échangeable de variables aléatoires et alors if and ony si . Par conséquent, par symétrie. Par conséquent, . $\{X_i\}_{i\geq 1}$

N = min {n : X_{n - 1} > X_{n}},

$N=\min\,\{n:X_{n-1}>X_n\},$

N \geq n

$N\geq n$

X_{1} \leq X_{2} \leq \dots \leq X_{n - 1}

$X_1\leq X_2\leq\dots\leq X_{n-1}$

Pr (N \geq n) = Pr (X_{1} \leq X_{2} \leq \dots \leq X_{n - 1}) = \frac{1}{(n - 1)!}, (*)

$\Pr(N\geq n) = \Pr(X_1\leq X_2\leq\dots\leq X_{n-1})=\frac{1}{(n-1)!}, \qquad (*)$

E [N] = \sum_{n = 1}^{\infty} Pr (N \geq n) = e \approx 2.71828 \dots

$\mathrm{E}[N]=\sum_{n=1}^\infty \Pr(N\geq n)=e\approx 2.71828\dots$

PS Les gens ont posé des questions sur la preuve de . La séquence étant échangeable, il faut que, pour toute permutation , on ait Puisque nous avonspermutations possibles, le résultat suit. $(*)$ $\pi:\{1,\dots,n-1\}\to\{1,\dots,n-1\}$

Pr (X_{1} \leq X_{2} \leq \dots \leq X_{n - 1}) = Pr (X_{π (1)} \leq X_{π (2)} \leq \dots \leq X_{π (n - 1)}) .

$\Pr(X_1\leq X_2\leq\dots\leq X_{n-1}) = \Pr(X_{\pi(1)}\leq X_{\pi(2)}\leq\dots\leq X_{\pi(n-1)}).$

(n - 1)!

$(n-1)!$

Zen
la source

2

J'aime ça - c'est un rappel que nous n'avons souvent pas besoin de trouver l'individu pour trouver la moyenne de Y et il peut être plus utile d'aller directement pour place.

Pr (Y = y)

$\Pr(Y=y)$

Pr (Y \geq y)

$\Pr(Y \geq y)$

Silverfish

+1 - mais cela ne répond pas réellement à la question, ce qui suppose un nombre fini donné de . Néanmoins, la technique s'applique au cas fini de manière évidente.

X_{i}

$X_i$

whuber

1

Un peu déroutant, non? L'OP mentionne une "séquence". Mais tu as raison. Au fait, est-il intuitif pour vous que le résultat soit "universel" (tel quel), en ce sens qu'il ne dépend pas de la distribution des (distribués à l'identique) ?

X_{i}

$X_i$

Zen

1

En fait, l'indépendance n'est pas nécessaire. L'échangeabilité suffit. Le résultat est plus fort. J'ajouterai ceci à ma réponse.

Zen

3

Il est intuitif qu'il est universel pour les variables continues . Une façon de rendre cela évident est de reconnaître que l'événement reste inchangé ae lors de l'application de la transformée intégrale de probabilité, ce qui la réduit au cas où les variables ont une distribution uniforme commune.

whuber

8

Comme suggéré par Silverfish, je poste la solution ci-dessous. Et

\begin{aligned} P [N = i] & = P [X_{1} \leq X_{2} \dots \leq X_{i - 1} > X_{i}] \\ = P [X_{1} \leq X_{2} \dots \leq X_{i - 1}] - P [X_{1} \leq X_{2} \dots \leq X_{i - 1} \leq X_{i}] \\ = \frac{1}{(i - 1)!} - \frac{1}{i!} \end{aligned}

$\begin{align*} P[N = i] & = P[X_1 \leq X_2 \dotsc \leq X_{i-1} > X_i] \\ & = P[X_1 \leq X_2 \dotsc \leq X_{i-1}] - P[X_1 \leq X_2 \dotsc \leq X_{i-1} \leq X_i] \\ & = \frac{1}{(i-1)!} - \frac{1}{i!} \end{align*}$

\begin{aligned} P [N \geq i] & = 1 - P [N < i] \\ = 1 - (1 - \frac{1}{2!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{1}{(i - 2)!} - \frac{1}{(i - 1)!}) \\ = \frac{1}{(i - 1)!} \end{aligned}

$\begin{align*} P[N \geq i] & = 1 - P[N < i] \\ & = 1 - \left(1 -\frac{1}{2!} + \frac{1}{2!} - \frac{1}{3!} + \cdots +\frac{1}{(i-2)!} - \frac{1}{(i-1)!}\right)\\ & = \frac{1}{(i-1)!} \\ \end{align*}$

Ainsi . $E[N] = \sum_{i = 1}^{\infty}P[N \geq i] = \sum_{i = 1}^{\infty}\frac{1}{(i-1)!} = e$

Hao le chou
la source

7

Un argument alternatif: il n'y a qu'un seul ordre du qui augmente, sur lepermutations possibles de . Nous nous intéressons aux ordonnances qui augmentent jusqu'à l'avant-dernière position, puis diminuent: cela nécessite que le maximum soit en position , et que l'un des autres soit en position finale. Puisqu'il existe façons de choisir l'un des premiers termes de notre séquence ordonnée et de le déplacer vers la position finale, alors la probabilité est: $X_i$ $n!$ $X_1, \dots, X_n$ $n-1$ $n-1$ $X_i$ $n-1$ $n-1$

Pr (N = n) = \frac{n - 1}{n!}

$\Pr(N=n) = \frac{n-1}{n!}$

Remarque , et donc ceci est cohérent avec les résultats trouvés par intégration. $\Pr(N=2) = \frac{2-1}{2!} = \frac{1}{2}$ $\Pr(N=3) = \frac{3-1}{3!} = \frac{1}{3}$ $\Pr(N=4) = \frac{4-1}{4!} = \frac{1}{8}$

Pour trouver la valeur attendue de nous pouvons utiliser: $N$

E (N) = \sum_{n = 2}^{\infty} n Pr (N = n) = \sum_{n = 2}^{\infty} \frac{n (n - 1)}{n!} = \sum_{n = 2}^{\infty} \frac{1}{(n - 2)!} = \sum_{k = 0}^{\infty} \frac{1}{k!} = e

$\mathbb{E}(N) = \sum_{n=2}^{\infty} n \Pr(N=n) = \sum_{n=2}^{\infty} \frac{n(n-1)}{n!} = \sum_{n=2}^{\infty} \frac{1}{(n-2)!}= \sum_{k=0}^{\infty} \frac{1}{k!} = e$

(Pour rendre la sommation plus évidente, j'ai utilisé ; pour les lecteurs qui ne connaissent pas cette somme, prenez la série Taylor et remplacez ) $k=n-2$ $e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}$ $x=1$

On peut vérifier le résultat par simulation, voici du code en R:

firstDecrease <- function(x) {
    counter <- 2
    a <- runif(1)
    b <- runif(1)
    while(a < b){
        counter <- counter + 1
        a <- b
        b <- runif(1)
    }
    return(counter)
}

mean(mapply(firstDecrease, 1:1e7))

Cela revint 2.718347, assez près pour 2.71828me satisfaire.

Silverfish
la source

-1

EDIT: Ma réponse est incorrecte. Je le laisse comme un exemple de la facilité avec laquelle une question apparemment simple comme celle-ci est mal interprétée.

Je ne pense pas que vos calculs soient corrects pour le cas . On peut le vérifier via une simulation simple: $P[N=4]$

n=50000
flag <- rep(NA, n)
order <- 3
for (i in 1:n) {
  x<-rnorm(100)
  flag[i] <- all(x[order] < x[1:(order-1)])==T
}
sum(flag)/n

Nous donne:

> sum(flag)/n
[1] 0.33326

Changer le orderterme à 4 nous donne:

> sum(flag)/n
[1] 0.25208

Et 5:

> sum(flag)/n
[1] 0.2023

Donc, si nous faisons confiance à nos résultats de simulation, il semble que le motif soit que . Mais cela a également du sens, car ce que vous demandez vraiment, c'est quelle est la probabilité que toute observation donnée dans un sous-ensemble de toutes vos observations soit l'observation minimale (si nous supposons iid, nous supposons alors l'échange, et donc l'ordre est arbitraire ). L'un d'eux doit être le minimum, et donc vraiment la question est de savoir quelle est la probabilité que toute observation sélectionnée au hasard soit le minimum. Il s'agit simplement d'un processus binomial simple. $P[N = X] = \frac{1}{x}$

Dalton Hance
la source

1

Vous avez légèrement mal interprété la question, si ma lecture est correcte - nous avons besoin que le final soit autre que le maximum (pas nécessairement le minimum) tandis que le premier du doit être en ordre croissant, donc le un en position est le maximum.

X_{n}

$X_n$

n - 1

$n-1$

X_{i}

$X_i$

n - 1

$n-1$

Silverfish

Je pense que c'est un peu plus qu'une légère mauvaise interprétation. Vous avez raison, je me trompe.

Dalton Hance

Supposons que sont des variables aléatoires iid. Quand la séquence devrait-elle diminuer pour la première fois?

Réponses: