Matematyka.pl

Witam.

Ostatnio przyszło mi zaprogramować funkcję wybierającą k elementów z n-elementowej tablicy. Intuicyjnie zaprogramowałem to następująco:
Po kolei przechodząc tablicę elementów obliczam wartość:
\(\displaystyle{ \frac{\mbox{ilosc brakujacych elementow}}{\mbox{ilosc pozostalych elementow}}}\)
która określa prawdopodobieństwo wybrania kolejnego elementu z tablicy (na początku będzie to równe \(\displaystyle{ \frac{k}{n}}\), a też gwarantuje wybór odpowiedniej ilości elementów).

To co jednak dla mnie intuicyjne, dla moich kolegów z zespołu jest nieco podejrzane i bardzo byliby radzi zobaczyć jakiś dowód poprawności (i.e. dowód, że taki algorytm wybiera elementy z rozkładem jednostajnym). Ja sam niestety nie jestem na tyle sprawny w rachunku prawdopodobieństwa, aby im to ad hoc przedstawić. Proszę więc o pomoc w utworzeniu dowodu poprawności (lub też niepoprawności) takiego schematu wyboru. Z góry dziękuję.

Hmmm, tylko jakoś jestem bliżej tego co myślą twoi koledzy.
Zastanów się nad dwoma aspektami tego co mówisz:
1. gdy k=n to będzie sie nieźle dzialo z twoim sposobem obliczania prawdopodobieństwa będzie cały czas równy 1, a to dziwne by prawdopodobieństwo wyboru w kroku np. 17 gdy zostało mi np. 29 elementów w tablicy było 1 - jakbyś teraz chciał zsumować prawdopodobieństwa tych 17-stu wybranych już elementów to otrzymałbyś wynik 17 (który jak wiadomo nie powinien być większy od 1)
2. Dwa: przyjrzyj się sposobie tworzenia drzewka prawdopodobieństw (dla elementów jednakowo prawdopodobnych) na dowolnym poziomie wyboru (według mnie to jest odpowiedź na wartość prawdopodobieństwa w dowolnym kroku iteracji w twoim programie)

W kroku i
prawdopodobieństwo to \(\displaystyle{ p=1/(n-i)}\)

OneLove pisze:1. gdy k=n to będzie sie nieźle dzialo z twoim sposobem obliczania prawdopodobieństwa będzie cały czas równy 1

No i bardzo dobrze, bo jeżeli chcę wybrać n elementów z n-elementowego zbioru, to prawdopodobieństwo wyboru każdego kolejnego elementu ma być równe 1.0 (inaczej mogę wybrać mniej niż n-elementów, czego bym nie chciał)

Poza tym, to chyba mam rozwiązanie tego problemu (pozytywne dla mnie) obliczone z prawdopodobieństwa warunkowego, ale na razie muszę je zaprezentować komuś znającemu się na rzeczy.

Coś jest nie tak z ogólną twoją koncepcją.
Mówisz, że

No i bardzo dobrze, bo jeżeli chcę wybrać n elementów z n-elementowego zbioru, to prawdopodobieństwo wyboru każdego kolejnego elementu ma być równe 1.0

Idąć tym rozumowaniem, można równie dobrze powiedzieć, że byle tylko k

OneLove pisze:Coś jest nie tak z ogólną twoją koncepcją.

Hm, no dobrze. Może napiszę dokładniej.
Mam zadany zbiór \(\displaystyle{ P}\) o mocy \(\displaystyle{ n \mathbb{N}}\). Chcę otrzymać zbiór \(\displaystyle{ P' P}\) o mocy \(\displaystyle{ k n}\). Wobec tego przechodzę wszystkie elementy \(\displaystyle{ P}\), w dowolnej kolejności, i każdy z rozważanych elementów dodaję do \(\displaystyle{ P'}\) z prawdopodobieństwem opisanym wyżej. Moim celem jest dowiedzenie, że takie rozwiązanie wybierania podzbioru jest poprawne, tzn wybór elementów nie zależy od ich kolejności (i.e. prawdopodobieństwo wyboru każdego elementu jest jednakowe).

OneLove pisze:Idąć tym rozumowaniem, można równie dobrze powiedzieć, że byle tylko k 0 ), bo właśnie chce się wybrać k elementów. Ale nie jest prawdą, że wybierze się każdy z elementów (chociażby dlatego, że dla k < n prawdopodobieństwo wylosowania pierwszego elementu nie jest równe 1).

Nazwij mnie upatym osłem, ale ja dalej uważam, że sie mylisz (co nie znaczy, że ja mam racje, ale stoje przy swoim).
Pozdrawiam.