Jak możemy ograniczyć prawdopodobieństwo, że zmienna losowa jest maksymalna?

$\newcommand{\P}{\mathbb{P}}$ Załóżmy, że mamy $N$ niezależnych zmiennych losowych $X_1$ , $\ldots$ , $X_n$ ze skończonymi środkami $\mu_1 \leq \ldots \leq \mu_N$ i wariancji $\sigma_1^2$ , $\ldots$ , $\sigma_N^2$ . Szukam granic bez dystrybucji prawdopodobieństwa, że każdy $X_i \neq X_N$ jest większy niż wszystkie inne $X_j$ , $j \neq i$ .

Innymi słowy, jeśli dla uproszczenia założymy, że rozkłady $X_i$ są ciągłe (takie, że $\P(X_i = X_j) = 0$ ), szukam granic na:

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

$\P( X_i = \max_j X_j ) \enspace.$ Jeśli

N = 2

$N=2$ , możemy użyć nierówności Czebyszewa, aby uzyskać:

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.$ Chciałbym znaleźć jakieś proste (niekoniecznie mocno) Bounds do ogólnego

N

$N$ , ale nie byłem w stanie znaleźć (estetycznie) miłe wyników dla ogólnego

N

$N$ .

Należy pamiętać, że zmienne nie są uważane za id. Wszelkie sugestie lub odniesienia do powiązanych prac są mile widziane.

Aktualizacja: pamiętaj, że z założenia $\mu_j \geq \mu_i$ . Następnie możemy użyć powyższego ograniczenia, aby dojść do:

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.$ Oznacza to:

(μ_{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.$ To z kolei implikuje:

\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.$ Jestem teraz zastanawiasz się, czy ten związany można poprawić na coś, co nie zależy liniowo od

N

$N$ . Na przykład, czy obowiązuje:

\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?$ A jeśli nie, to co może być kontrprzykładem?

probability bounds maximum MLS
źródło

To może być związany mocniej jeśli używasz indeksu , który daje im mniejsza górna granica zamiast . Zauważ, że ta wartość zależy zarówno od średniej, jak i wariancji.

j

$j$

N

$N$

@MichaelChernick: Nie wierzę, że to prawda. Załóżmy na przykład, że mamy trzy jednolite rozkłady na . Następnie, jeśli się nie mylę, , podczas gdy . Nie wiem, czy chciałeś napisać , ale ten sam przykład pokazuje, że nadal nie jest poprawny.

[0, 1]

$[0,1]$

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

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

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

$P(X_1 < X_2) = P(X_1 < X_3) = 1/2$

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

$P( X_i > \max_j X_j )$

MLS

@Michael: Niestety nadal nie jest to prawdą. Zdarzenia dla fixed nie są niezależne.

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

$A_j = \{X_i > X_j\}$

i

$i$

kardynał

@cardinal: Między innymi dotyczy to uzbrojonych bandytów. Jeśli wybierzesz ramię w oparciu o poprzednie nagrody, jak duże jest prawdopodobieństwo, że wybrałeś najlepsze ramię (byłoby to w powyższym zapisie), i czy możemy ograniczyć spodziewaną stratę za wybranie sub -optymalne ramię?

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

$P(X_N = \max_j X_j)$

MLS

Przekreślony na MathOverflow: mathoverflow.net/questions/99313

kardynał

Odpowiedzi:

Możesz użyć nierówności Czebiszewa na wielu odmianach.

Przypadek dwóch zmiennych

W przypadku jednej sytuacji, vs. , do tej samej sytuacji, co komentarz Jochena z 4 listopada 2016 r $X_1$ $X_2$

1) Jeśli to $\mu_1 < \mu_2$ $P(X_1>X_2) \leq (\sigma_1^2 + \sigma_2^2)/(\mu_1-\mu_2)^2$

(i zastanawiam się również nad twoją pochodną)

Wyprowadzenie równania 1

przy użyciu nowej zmiennej $X_1-X_2$
przekształcając go tak, aby miał średnią zero
przyjmowanie wartości bezwzględnej
stosując nierówność Czebyszewa

\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}$

Przypadek wielowymiarowy

Nierówność w równaniu (1) można zmienić na przypadek wielowymiarowy, stosując ją do wielu transformowanych zmiennych dla każdego (zauważ, że są one skorelowane). $(X_n-X_i)$ $i<n$

Rozwiązanie tego problemu (wielowymiarowe i skorelowane) zostało opisane przez I. Olkina i JW Pratta. „A Multivariate Tchebycheff Inequality” w Annals of Mathematical Statistics, tom 29 strony 226-234 http://projecteuclid.org/euclid.aoms/1177706720

Uwaga twierdzenie 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}$

w którym liczba zmiennych, , a . $p$ $t=\sum k_i^{-2}$ $u=\sum \rho_{ij}/(k_ik_j)$

Twierdzenie 3.6 zapewnia ściślejsze powiązanie, ale jest trudniejsze do obliczenia.

Edytować

Ostrzejsze granice można znaleźć, stosując nierówność Cantelliego na wielu odmianach . Ta nierówność jest typem, który użyłeś wcześniej i zapewnił ci granicę który jest ostrzejsze niż . $(\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$

Nie poświęciłem czasu na przestudiowanie całego artykułu, ale i tak możesz znaleźć rozwiązanie tutaj:

AW Marshall i I. Olkin „Jednostronna nierówność typu Czebyszewa” w Annals of Mathematical Statistics tom 31 str. 488-491 https://projecteuclid.org/euclid.aoms/1177705913

(późniejsza uwaga: ta nierówność dotyczy równych korelacji i niewystarczającej pomocy. W każdym razie twój problem, aby znaleźć najostrzejszą granicę, jest równy, bardziej ogólnie, wielowymiarowej nierówności Cantellego. Byłbym zaskoczony, gdyby rozwiązanie nie istniało)

Sextus Empiricus
źródło

Czy możesz podać wyraźne stwierdzenie wielowymiarowej nierówności Czebyszewa?

whuber

Zredagowałem rozwiązanie podając całe twierdzenie.

Sextus Empiricus

-1

Znalazłem twierdzenie, które może ci pomóc i spróbuję je dostosować do twoich potrzeb. Załóżmy, że masz:

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}))$

Następnie przez nierówność Jensena (ponieważ exp (.) Jest funkcją wypukłą), otrzymujemy:

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})$

Teraz w przypadku musisz podłączyć dowolną funkcję generującą moment swojej zmiennej losowej (ponieważ jest to tylko definicja mgf). Następnie, po zrobieniu tego (i potencjalnie upraszczając twój termin), bierzesz ten termin, bierzesz dziennik i dzielisz go przez t, aby uzyskać oświadczenie o terminie . Następnie możesz wybrać t z dowolną wartością (najlepiej, aby termin był mały, aby granica była ciasna). $exp(t \cdot X_{i}$ $X_{i}$ $\mathbf{E}(\underset{1 \leq i \leq n}{max}X_{i})$

Następnie masz oświadczenie o oczekiwanej wartości maksymalnej ponad n rvs. Aby uzyskać teraz stwierdzenie o prawdopodobieństwie, że maksimum tych wartości rv odbiega od tej oczekiwanej wartości, możesz po prostu użyć nierówności Markowa (zakładając, że twoje wartości rv jest nieujemne) lub innej, bardziej szczegółowej wartości rv, odnoszącej się do twojego konkretnego wartości.

Fabian Falck
źródło