Comment limiter la probabilité qu'une variable aléatoire soit maximale?

$\newcommand{\P}{\mathbb{P}}$ Supposons que nous ayons variables aléatoires indépendantes , , avec des moyens finis et des variances , , . Je recherche des bornes sans distribution sur la probabilité que tout soit plus grand que tous les autres , . $N$ $X_1$ $\ldots$ $X_n$ $\mu_1 \leq \ldots \leq \mu_N$ $\sigma_1^2$ $\ldots$ $\sigma_N^2$ $X_i \neq X_N$ $X_j$ $j \neq i$

En d'autres termes, si pour simplifier nous supposons que les distributions de $X_i$ sont continues (telles que $\P(X_i = X_j) = 0$ ), je cherche des bornes sur:

P (X_{i} = max_{j} X_{j}) .

$\P( X_i = \max_j X_j ) \enspace.$ Si

N = 2

$N=2$ , nous pouvons utiliser l'inégalité de Chebyshev pour obtenir:

P (X_{1} = max_{j} X_{j}) = P (X_{1} > X_{2}) \leq \frac{σ_{1}^{2} + σ_{2}^{2}}{σ_{1}^{2} + σ_{2}^{2} + (μ_{1} - μ_{2})^{2}} .

$\P(X_1 = \max_j X_j) = \P(X_1 > X_2) \leq \frac{\sigma_1^2 + \sigma_2^2}{\sigma_1^2 + \sigma_2^2 + (\mu_1 - \mu_2)^2} \enspace.$ Je voudrais trouver des limites simples (pas nécessairement strictes) pour le

général

N

$N$ , mais je n'ai pas pu trouver de résultats (esthétiquement) agréables pour le

général

N

$N$ .

Veuillez noter que les variables ne sont pas supposées être iid. Toutes suggestions ou références à des travaux connexes sont les bienvenues.

Mise à jour: rappelez-vous que par hypothèse, $\mu_j \geq \mu_i$ . Nous pouvons alors utiliser la borne ci-dessus pour arriver à:

P (X_{i} = max_{j} X_{j}) \leq min_{j > i} \frac{σ_{i}^{2} + σ_{j}^{2}}{σ_{i}^{2} + σ_{j}^{2} + (μ_{j} - μ_{i})^{2}} \leq \frac{σ_{i}^{2} + σ_{N}^{2}}{σ_{i}^{2} + σ_{N}^{2} + (μ_{N} - μ_{i})^{2}} .

$\P(X_i = \max_j X_j) \leq \min_{j > i} \frac{\sigma_i^2 + \sigma_j^2}{\sigma_i^2 + \sigma_j^2 + (\mu_j - \mu_i)^2} \leq \frac{\sigma_i^2 + \sigma_N^2}{\sigma_i^2 + \sigma_N^2 + (\mu_N - \mu_i)^2} \enspace.$ Cela implique:

(μ_{N} - μ_{i}) P (X_{i} = max_{j} X_{j}) \leq (μ_{N} - μ_{i}) \frac{σ_{i}^{2} + σ_{N}^{2}}{σ_{i}^{2} + σ_{N}^{2} + (μ_{N} - μ_{i})^{2}} \leq \frac{1}{2} \sqrt{σ_{i}^{2} + σ_{N}^{2}} .

$( \mu_N - \mu_i ) \P( X_i = \max_j X_j ) \leq (\mu_N - \mu_i) \frac{\sigma_i^2 + \sigma_N^2}{\sigma_i^2 + \sigma_N^2 + (\mu_N - \mu_i)^2} \leq \frac{1}{2} \sqrt{ \sigma_i^2 + \sigma_N^2 } \enspace.$ Cela implique à son tour:

\sum_{i = 1}^{N} μ_{i} P (X_{i} = max_{j} X_{j}) \geq μ_{N} - \frac{N}{2} \sqrt{\sum_{i = 1}^{N - 1} (σ_{i}^{2} + σ_{N}^{2})} .

$\sum_{i=1}^N \mu_i \P( X_i = \max_j X_j ) \geq \mu_N - \frac{N}{2} \sqrt{ \sum_{i=1}^{N-1} (\sigma_i^2 + \sigma_N^2) } \enspace.$ Je me demande maintenant si cette borne peut être améliorée à quelque chose qui ne dépend pas de façon linéaire sur

N

$N$ . Par exemple, la valeur suivante est-elle vérifiée:

\sum_{i = 1}^{N} μ_{i} P (X_{i} = max_{j} X_{j}) \geq μ_{N} - \sqrt{\sum_{i = 1}^{N} σ_{i}^{2}} ?

$\sum_{i=1}^N \mu_i \P( X_i = \max_j X_j ) \geq \mu_N - \sqrt{ \sum_{i=1}^N \sigma_i^2 } \enspace?$ Et sinon, quel pourrait être un contre-exemple?

probability bounds maximum MLS
la source

Cette borne peut être plus serré si vous utilisez l'index

j

$j$ qui vous donne la plus petite limite supérieure au lieu de

N

$N$ . Notez que cette valeur dépend à la fois de la moyenne et de la variance.

@ MichaelChernick: Je ne pense pas que ce soit correct. Supposons par exemple que nous ayons trois distributions uniformes sur

[0, 1]

$[0,1]$ . Ensuite, si je ne me trompe pas,

P (X_{1} < max_{j} X_{j}) = 2 / 3

$P( X_1 < \max_j X_j ) = 2/3$ , tandis que

P (X_{1} < X_{2}) = P (X_{1} < X_{3}) = 1 / 2

$P(X_1 < X_2) = P(X_1 < X_3) = 1/2$ . Je ne sais pas si vous vouliez écrire

P (X_{i} > max_{j} X_{j})

$P( X_i > \max_j X_j )$ , mais alors le même exemple montre qu'il n'est toujours pas valide.

MLS

@Michael: Ce n'est toujours pas vrai, malheureusement. Les événements pour fixe ne sont pas indépendants.

A_{j} = {X_{i} > X_{j}}

$A_j = \{X_i > X_j\}$

i

$i$

cardinal

@cardinal: Entre autres, c'est lié aux bandits multi-armés. Si vous choisissez un bras en fonction des récompenses précédentes, quelle est la probabilité que vous choisissiez le meilleur bras (ce serait dans la notation ci-dessus), et pouvons-nous limiter la perte attendue pour choisir un sous -bras optimal?

P (X_{N} = max_{j} X_{j})

$P(X_N = \max_j X_j)$

MLS

Crossposted to MathOverflow: mathoverflow.net/questions/99313

cardinal

Réponses:

Vous pouvez utiliser l'inégalité multivariée de Chebyshev.

Cas de deux variables

Pour une seule situation, vs , j'arrive à la même situation que le commentaire de Jochen le 4 novembre 2016 $X_1$ $X_2$

1) Si alors $\mu_1 < \mu_2$ $P(X_1>X_2) \leq (\sigma_1^2 + \sigma_2^2)/(\mu_1-\mu_2)^2$

(et je m'interroge également sur votre dérivation)

Dérivation de l'équation 1

en utilisant la nouvelle variable $X_1-X_2$
le transformer de telle sorte qu'il a la moyenne à zéro
prendre la valeur absolue
appliquer l'inégalité de Chebyshev

\begin{matrix} P (X_{1} > X_{2}) & = P (X_{1} - X_{2} > 0) \\ = P (X_{1} - X_{2} - (μ_{1} - μ_{2}) > - (μ_{1} - μ_{2})) \\ \leq P (| X_{1} - X_{2} - (μ_{1} - μ_{2}) | > μ_{2} - μ_{1}) \\ \leq \frac{σ_{(X_{1} - X_{2} - (μ_{1} - μ_{2}))}^{2}}{(μ_{2} - μ_{1})^{2}} = \frac{σ_{X_{1}}^{2} + σ_{X_{2}}^{2}}{(μ_{2} - μ_{1})^{2}} \end{matrix}

$\begin{array} \\ P \left( X_1 > X_2 \right) &= P \left( X_1 - X_2 > 0 \right)\\ &= P\left( X_1 - X_2 - (\mu_1 - \mu_2) > - (\mu_1 - \mu_2)\right) \\ &\leq P\left( \vert X_1 - X_2 - (\mu_1 - \mu_2) \vert > \mu_2 - \mu_1\right) \\ &\leq \frac{\sigma_{(X_1-X_2- (\mu_1 - \mu_2))}^2}{(\mu_2 - \mu_1)^2} = \frac{\sigma_{X_1}^2+\sigma_{X_2}^2}{(\mu_2 - \mu_1)^2}\\ \end{array}$

Cas multivarié

L'inégalité dans l'équation (1) peut être transformée en un cas multivarié en l'appliquant à plusieurs variables transformées pour chaque (notez qu'elles sont corrélées). $(X_n-X_i)$ $i<n$

Une solution à ce problème (multivariée et corrélée) a été décrite par I. Olkin et JW Pratt. «A Multivariate Tchebycheff Inequality» dans Annals of Mathematical Statistics, volume 29 pages 226-234 http://projecteuclid.org/euclid.aoms/1177706720

Remarque le théorème 2.3

$P(\vert y_i \vert \geq k_i \sigma_i \text{ for some } i) = P(\vert x_i \vert \geq 1 \text{ for some } i) \leq \frac{(\sqrt{u} + \sqrt{(pt-u)(p-1)})^2}{p^2}$

dans laquelle le nombre de variables, , et . $p$ $t=\sum k_i^{-2}$ $u=\sum \rho_{ij}/(k_ik_j)$

Le théorème 3.6 fournit une limite plus stricte, mais est moins facile à calculer.

modifier

Une borne plus nette peut être trouvée en utilisant l' inégalité multivariée de Cantelli . Cette inégalité est le type que vous avez utilisé auparavant et qui vous a fourni la limite qui est plus nette que . $(\sigma_1^2 + \sigma_2^2)/(\sigma_1^2 + \sigma_2^2 + (\mu_1-\mu_2)^2)$ $(\sigma_1^2 + \sigma_2^2)/(\mu_1-\mu_2)^2$

Je n'ai pas pris le temps d'étudier l'article en entier, mais de toute façon, vous pouvez trouver une solution ici:

AW Marshall et I. Olkin «Une inégalité unilatérale du type Chebyshev» dans Annals of Mathematical Statistics volume 31 pp. 488-491 https://projecteuclid.org/euclid.aoms/1177705913

(note ultérieure: cette inégalité est pour des corrélations égales et pas une aide suffisante. Mais de toute façon votre problème, pour trouver la borne la plus nette, est égal à l'inégalité Cantelli multivariée plus générale. Je serais surpris si la solution n'existe pas)

Sextus Empiricus
la source

Pourriez-vous fournir une déclaration claire de l'inégalité multivariée de Chebyshev?

whuber

J'ai édité la solution fournissant le théorème entier.

Sextus Empiricus

-1

J'ai trouvé un théorème qui pourrait vous aider et j'essaierai de l'adapter à vos besoins. Supposons que vous ayez:

e x p (t \cdot E (\underset{1 \leq i \leq n}{m a x} X_{i}))

$exp(t \cdot \mathbf{E}(\underset{1 \leq i \leq n}{max}X_{i}))$

Ensuite par l'inégalité de Jensen (puisque exp (.) Est une fonction convexe), on obtient:

e x p (t \cdot E (\underset{1 \leq i \leq n}{m a x} X_{i})) \leq E (e x p (t \cdot \underset{1 \leq i \leq n}{m a x} X_{i})) = E (\underset{1 \leq i \leq n}{m a x} e x p (t \cdot X_{i})) \leq \sum_{i = 1}^{n} E (e x p (t \cdot X_{i})

$exp(t \cdot \mathbf{E}(\underset{1 \leq i \leq n}{max}X_{i})) \leq \mathbf{E}(exp( t \cdot \underset{1 \leq i \leq n}{max}X_{i})) = \mathbf{E}( \underset{1 \leq i \leq n}{max} \text{ }exp( t \cdot X_{i})) \leq \sum_{i=1}^{n} \mathbf{E} (exp(t \cdot X_{i})$

Maintenant, pour vous devez brancher quelle que soit la fonction de génération de moment de votre variable aléatoire (car ce n'est que la définition du mgf). Ensuite, après l'avoir fait (et potentiellement simplifiant votre terme), vous prenez ce terme et prenez le journal et le divisez par t pour obtenir une déclaration sur le terme . Ensuite, vous pouvez choisir t avec une valeur arbitraire (mieux pour que le terme soit petit pour que la borne soit serrée). $exp(t \cdot X_{i}$ $X_{i}$ $\mathbf{E}(\underset{1 \leq i \leq n}{max}X_{i})$

Ensuite, vous avez une déclaration sur la valeur attendue du maximum sur n rvs. Pour obtenir maintenant une déclaration sur la probabilité que le maximum de ces VR s'écarte de cette valeur attendue, vous pouvez simplement utiliser l'inégalité de Markov (en supposant que votre RV n'est pas négative) ou une autre RV, plus spécifique, s'appliquant à votre RV particulier.

Fabian Falck
la source