Losowo wybierane z listy z ważonymi prawdopodobieństwami

Question

Mam tablicę N elementów (reprezentujących litery N danego alfabetu), a każda komórka tablicy zawiera wartość całkowitą, która to liczba całkowita oznacza liczbę wystąpień w podany tekst tego listu. Teraz chcę losowo wybierać list od wszystkich liter alfabetu, na podstawie jego liczby występów z podanych ograniczeń:

• Jeżeli litera ma wartość dodatnią (niezerowy), to może być zawsze wybierany przez algorytm (oczywiście z większym lub mniejszym prawdopodobieństwem).

• Jeśli litera A ma wyższą wartość niż litera B, musi być bardziej prawdopodobne, że zostanie wybrana przez algorytm.

Teraz, biorąc to pod uwagę, mam wymyślić prosty algorytm, który może wykonać zadanie, ale ja po prostu zastanawiasz się, czy nie było lepiej coś zrobić. Wydaje się to być dość fundamentalne i myślę, że mogą być bardziej sprytne rzeczy do zrobienia, aby osiągnąć to bardziej wydajnie. Jest to algorytm, o którym myślałem:

• Dodaj wszystkie częstotliwości w tablicy. Przechowuj go w SUM
• Wybór losowej wartości od 0 do SUMY. Przechowuj go w sieci RAN
• [Podczas] RAN> 0, Rozpoczynając od pierwszej, przejdź do każdej komórki w tablicy (w kolejności) i odejmij wartość tej komórki od RAN
• Ostatnia odwiedzona komórka jest wybrana

Czy jest coś lepszego niż to? Czy czegoś brakuje?

Jestem świadomy, że większość współczesnych komputerów potrafi to obliczyć tak szybko, że nawet nie zauważy, czy mój algorytm jest nieefektywny, więc jest to raczej pytanie teoretyczne, a nie praktyczne.

Preferuję wyjaśniony algorytm, a nie tylko kod do odpowiedzi, ale jeśli czujesz się wygodniej udzielając odpowiedzi w kodzie, nie mam z tym problemu.

Answer 1

Pomysł:

• iterację wszystkich elementów i ustawić wartość każdego elementu jako skumulowaną częstość pory.
• Generowanie liczby losowej od 1 do sumy wszystkich częstotliwości
• Wykonaj binary search dla wartości dla tego numeru (znalezienie pierwszej wartości większej lub równej liczbie).

przykład:

Element A B C D 
Frequency 1 4 3 2 
Cumulative 1 5 8 10 

wygenerować losową liczbę w zakresie 1-10 (1 + 4 + 3 + 2 = 10, tak samo jak w poprzednim wartości skumulowanej listy) do poszukiwania binarnego, który powróci następujące wartości:

Number Element returned 
1  A 
2  B 
3  B 
4  B 
5  B 
6  C 
7  C 
8  C 
9  D 
10  D 

Answer 2

Alias Method jest amortyzowane o (1), raz w generowana wartość, ale wymaga za jednorodnych odnośnika.Zasadniczo tworzysz tabelę, w której każda kolumna zawiera jedną z generowanych wartości, drugą wartość nazywaną aliasem i warunkowe prawdopodobieństwo wyboru między wartością a jej aliasem. Użyj pierwszego munduru, aby wybrać jedną z kolumn z równym prawdopodobieństwem. Następnie wybierz między wartością podstawową a aliasem na podstawie drugiego munduru. Aby początkowo skonfigurować poprawną tabelę dla wartości n, konieczne jest wykonanie operacji O (n log n), ale po wygenerowaniu wartości generowanych przez tabelę jest stały czas. Możesz pobrać this Ruby gem, aby zobaczyć rzeczywistą implementację.

Dwie inne bardzo szybkie metody autorstwa Marsaglia et al. są opisane here. Dostarczyli C implementations.