Oczekiwanie na sumę liczb K bez wymiany

Biorąc pod uwagę liczb, gdzie wartość każdej liczby jest inna, oznaczona jako , a prawdopodobieństwo wyboru każdej liczby wynosi odpowiednio . $n$ $v_1, v_2, ..., v_n$ $p_1, p_2, ..., p_n$

Teraz, jeśli liczby na podstawie podanych prawdopodobieństw, gdzie , jakie jest oczekiwanie sumy tych liczb ? Zauważ, że zaznaczenie nie jest zastępowane, więc liczby nie mogą obejmować zduplikowanych liczb. Rozumiem, że jeśli wybór jest z zastąpieniem, oczekiwanie sumy liczb jest równe , gdzie $K$ $K \leq n$ $K$ $K$ $K$ $K \times E(V)$

E (V) = v_{1} \times p_{1} + v_{2} \times p_{2} + . . . + v_{n} \times p_{n} .

$E(V) = v_1 \times p_1 + v_2 \times p_2 + ... + v_n \times p_n.$

Ponadto, co z oczekiwaniem wariancji tych liczb ? $K$

Jestem doktorantem CS, który pracuje nad problemem dużych zbiorów danych i nie mam żadnych statystyk. Oczekuję, że ktoś może dać mi formułę jako odpowiedź. Jeśli jednak odpowiedź jest zbyt skomplikowana, aby ją opisać formułą lub konieczne jest zastosowanie intensywnego obliczenia, przybliżona odpowiedź jest całkowicie akceptowalna.

Możesz założyć, że jest tutaj dość duże, a prawdopodobieństwo może być bardzo różne. W praktyce wartości tych prawdopodobieństw pochodzą z dziennika zapytań, który rejestruje serię zapytań agregacyjnych. Chodzi o to, że częstotliwość każdej liczby uczestniczącej w zapytaniach może być dość wypaczona, tj. Niektóre są rzadko pytane, a niektóre bardzo często. Możesz założyć, że rozkład prawdopodobieństwa jest rozkładem normalnym, rozkładem zipf lub innymi rozsądnymi alternatywami. $n$

Rozkład wartości jest tylko ciągłym podzbiorem każdego możliwego rozkładu. Innymi słowy, jeśli masz histogram reprezentujący pewien rozkład, wszystkie liczby zaangażowane w ten problem to liczby znajdujące się w jednym segmencie.

Pod względem wartości K można założyć, że jest ona zawsze mniejsza niż liczba często zadawanych elementów.

probability

— SciPioneer
źródło

Oczekiwanie wariancji sumy będzie różne bez zamiany; będziesz potrzebować skończonego współczynnika korekcji populacji, jeśli nie ma zamiany. (Aby zobaczyć to intuicyjnie, zwróć uwagę, że jeśli K = n wariancja sumy wynosi zero, ponieważ zawsze będzie to ta sama liczba; tak jak K zbliża się n wariancja sumy będzie mniejsza.)

— zbicyclist

To pytanie może być trudniejsze, niż mogłoby się wydawać. Rozważmy przypadek i . Oczekiwana suma dwóch wartości narysowanych przy zamianie wynosi co jest dwukrotnością oczekiwanej sumy jednej wartości; ale oczekiwana suma dwóch wartości narysowanych bez zamiany to oczywiście z wyjątkiem sytuacji, gdy .

n = 2

$n=2$

(v_{1}, v_{2}) = (0, 1)

$(v_1,v_2)=(0,1)$

2 p_{2}

$2p_2$

v_{1} + v_{2} = 1 \neq 2 p_{2}

$v_1+v_2=1\ne 2p_2$

p_{1} = p_{2} = 1 / 2

$p_1=p_2=1/2$

— whuber

@zbicyclist Być może nie wyjaśniłem jasno problemu. W moim scenariuszu, jeśli K = N, wówczas wariancja tych liczb K będzie wariancją ogólnej populacji, a nie 0.

— SciPioneer

(1) Nie wydaje mi się to pytaniem do samodzielnej nauki : wygląda na to, że istnieje prawdziwy problem. (2) Jak duży może być ? Dokładne rozwiązania wyglądają na niewykonalne, chyba że można wymienić wszystkie podzbiory. (3) Jeśli może być znacznie większe niż około , co wyklucza szybkie wyliczanie, co możesz powiedzieć o ? Na przykład, czy mogą się różnić, czy też będą zbliżone do ? Może to pomóc w znalezieniu przybliżonych odpowiedzi.

n

$n$

n

$n$

20

$20$

p_{i}

$p_i$

1 / n

$1/n$

— whuber

Dzięki za zmiany. Im więcej możesz nam powiedzieć o , , i , tym lepiej. Na przykład, jeśli wówczas wzory do próbkowania z zamianą powinny być dobrym przybliżeniem (ponieważ bardzo niewiele wartości, jeśli w ogóle, byłyby wybrane więcej niż jeden raz). Wierzę najtrudniejsze przypadki, gdzie istnieje szeroki zakres wartości -SO że nie można po prostu zastąpić większość z zer i jeszcze z na znaczną liczbę --and .

N

$N$

K

$K$

v_{i}

$v_i$

p_{i}

$p_i$

K max (p_{i}) ≪ 1

$K\max(p_i)\ll 1$

p_{i}

$p_i$

p_{i} > 1 / K

$p_i\gt 1/K$

i

$i$

K \approx N / 2

$K\approx N/2$

— whuber

Prawdopodobnie ma to charakter odpowiedzi, która, choć dokładna, prawdopodobnie nie jest tak przydatna. Horvitz i Thompson (1952) przedstawiają wyniki, które ogólnie obejmują tę sytuację. Wyniki te podano w kategoriach wyrażeń kombinatorycznych, których można się spodziewać.

Aby zachować spójność z ich notacją, a także lepiej odpowiadać powszechnie stosowanej notacji, pozwól mi na nowo zdefiniować niektóre ilości. Niech będzie liczbą elementów w populacji, a będzie wielkością próby. $N$ $n$

Niech , , reprezentują elementów populacji, z podanymi wartościami , i prawdopodobieństwami wyboru . Dla danej próbki o rozmiarze , niech obserwowane wartości w próbce będą wynosić . $u_i$ $i=1,...,N$ $N$ $V_i$ $i=1,...,N$ $p_1,...,p_N$ $n$ $v_1,..., v_n$

Pożądana jest średnia i wariancja sumy próby

\sum_{i = 1}^{n} v_{i} .

$\sum_{i=1}^n v_i.$

Jak wspomniano w komentarzach, prawdopodobieństwo wyboru konkretnej próbki narysowanej w tej kolejności wynosi gdzie początkowe prawdopodobieństwo rysowania jest podane przez , drugie prawdopodobieństwo rysowania jest uwarunkowane usunięciem z populacji i tak dalej. Tak więc każda kolejna narysowana jednostka powoduje nowy rozkład prawdopodobieństwa dla następnej jednostki (stąd wybór różnych liter wskaźnikowych, ponieważ każda reprezentuje inny rozkład). $s = \{u_i, u_j, ..., u_t\}$

Par (s) = p_{{ja}_{1}} p_{{jot}_{2)}} \dots p_{t_{n}},

$\textrm{Pr}(s) = p_{i_1}p_{j_2}\cdots p_{t_n},$

p_{i_{1}}

$p_{i_1}$

u_{i}

$u_i$

p_{i}

$p_i$

p_{j_{2}}

$p_{j_2}$

u_{j}

$u_j$

u_{i}

$u_i$

Istnieją próbki wielkości które zawierają z całej populacji. Zauważ, że bierze to pod uwagępermutacje próbki.

{S.}^{(ja)} = n! (\binom{N. - 1}{n - 1})

$S^{(i)} = n! \binom{N-1}{n-1}$

n

$n$

u_{i}

$u_i$

n!

$n!$

Niech oznacza konkretną próbkę o rozmiarze która obejmuje . Następnie prawdopodobieństwo wybrania elementu jest określone przez gdzie sumowanie dla zestawu rozmiarów z wszystkie możliwe próbki o rozmiarze które zawierają . (Zmieniłem nieco notację z papieru, ponieważ wydawało mi się to mylące). $s_n^{(i)}$ $n$ $u_i$ $u_i$

P. (u_{ja}) = \sum Par (s_{n}^{(ja)}),

$P(u_i) = \sum \textrm{Pr}(s_n^{(i)}),$

S^{(i)}

$S^{(i)}$

s_{n}^{(i)}

$s_n^{(i)}$

n

$n$

u_{i}

$u_i$

Podobnie zdefiniuj jako liczba próbek zawierających zarówno jak i . Następnie możemy zdefiniować prawdopodobieństwo próbki zawierającej zarówno jako gdzie suma jest większa niż zbiór wielkości wszystkich możliwych próbek o rozmiarze które zawierają i .

{S.}^{(ja jot)} = n! (\binom{N. - 2)}{n - 2)})

$S^{(ij)} = n! \binom{N-2}{n-2}$

u_{i}

$u_i$

u_{j}

$u_j$

P. (u_{ja} u_{jot}) = \sum Par (s_{n}^{(ja jot)}),

$\textrm{P}(u_i u_j) = \sum \textrm{Pr}(s_n^{(ij)}),$

S^{(i j)}

$S^{(ij)}$

s_{n}^{(i j)}

$s_n^{(ij)}$

n

$n$

u_{i}

$u_i$

u_{j}

$u_j$

Oczekiwana wartość jest następnie obliczana jako

mi (\sum_{ja = 1}^{n} v_{ja}) = \sum_{ja = 1}^{N.} P. (u_{ja}) {V.}_{ja} .

$E \left( \sum_{i=1}^n v_i \right) = \sum_{i=1}^N \textrm{P}(u_i) V_i.$

Chociaż wariancja nie została wyraźnie wyprowadzona z pracy, można ją uzyskać z oczekiwań co do momentu i produkty krzyżowe $q$

mi (\sum_{ja = 1}^{n} v_{ja}^{q}) = \sum_{ja = 1}^{N.} P. (u_{ja}) {V.}_{ja}^{q}

$E \left( \sum_{i=1}^n v_i^q \right) = \sum_{i=1}^N \textrm{P}(u_i) V_i^q$

mi (\sum_{ja \neq jot}^{n} v_{ja} v_{jot}) = \sum_{ja \neq jot} P. (u_{ja} u_{jot}) {V.}_{ja} {V.}_{jot} .

$E \left( \sum_{i \ne j}^n v_iv_j \right) = \sum_{i \ne j} \textrm{P}(u_i u_j) V_i V_j.$

Innymi słowy, wygląda na to, że należałoby przejść przez wszystkie możliwe podzbiory, aby wykonać te obliczenia. Być może można to jednak zrobić dla mniejszych wartości . $n$

Horvitz, DG i Thompson, DJ (1952) Uogólnienie próbkowania bez zastąpienia ze skończonego wszechświata. Journal of American Statistics Association 47 (260): 663–685.

— jvbraun
źródło