Algorytm - estymator grup


(LonngerM) #1

Głupio mi tutaj pisać o moim problemie, bo zwykle z tymi radzę sobie sam. Niestety im bardziej się odchodzi od zadań teoretycznych to jak nagle przychodzi zadanie na papierze kuleje. Prosiłbym Was o pomoc… nakierowanie na rozwiązanie w przypadku tego zadania:

Nad zadaniem siedzę od początku marca, ale nie potrafię go ugryźć, zwykle indukcja i wykazanie pewnych zależności nie stanowią dla mnie problemu, ale elementy prawdopodobieństwa rozkładają mnie na łopatki. Proszę o pomoc, wskazówki, rady.


(Pablo_Wawa) #2

Nie mam pewności, bo studiowałem ponad 15 lat temu, ale czy:

  1. E(S) to wartość oczekiwana zmiennej losowej (sumy)?

  2. dla rozkładów dyskretnych E(X) = suma iloczynu (wartość * prawdopodobieństwo tej wartości)

  3. dla n wartości (zero-jedynkowych) wartość sumy może wynosić między 0 a n (wynosi k, czyli tyle ile jest jedynek);

  4. prawdopodobieństwo tego, że suma wyniesie k można obliczyć ze wzoru na ilość kombinacji (n po k) => dwumian Newtona, bo na tyle sposobów można rozstawić k jedynek na n pozycjach;

  5. E(S) = Suma [po k od 0 do n] (k * (n po k)) - być może da się to uprościć i otrzymać szukany wynik.


(LonngerM) #3

E(S) to szacowana liczba grup występujących w grupie czyli nie jest to suma. Grupa powstaje gdy następny element jest inny od bieżącego.

Czyli jak będziemy mieć tablice 4 elementową z dwoma jedynkami to będzie wyglądać tak:

[1,1,0,0] - 1 grupa

[1,0,1,0] - 3 grupy

[0,1,1,0] - 2 grupy

[0,1,0,1] - 3 grupy

[0,0,1,1] - 1 grupa

E(S) = (2*2(4-2))/4 = 8/4 = 2

sr = (1+3+2+3+1) / 5 = 10/5 = 2

Tak więc widzimy, że jest tu ważna pozycja jedynki… Więc podejrzewam, że będę musiał użyć wzór na wariacje z powtórzeniami… Ale w nim będziemy mieć uwzględniane tylko n… gdzie miejsce na k?:confused:

Dodane 29.03.2013 (Pt) 21:33

Próbowałem na konsultacjach zaczepić prowadzącego, ale jedynie zasugerował mi jakiś wzorzec w którym ograniczam “n” i sprawdzam wszystkie możliwości “k” - inne rozwiązanie nie przychodziło mu do głowy… ale więcej nie powie bo by rozwiązał zadanie za mnie… - a ja naprawdę już nie wiem jak to policzyć:/