Paweł Goleń, blog

import random
osoby = ['osoba1', 'osoba2', 'osoba3']
print osoby[random.randint(0,10)%len(osoby)]

Jeśli ten sposób losowania jest wykorzystywany do wyznaczania osoby, która ma zrobić coś, czego nikt nie chce robić, to osoba3 ma lepiej niż osoba1. Dowód? Proszę:

In [41]: x = [random.randint(0,10)%3 for x in range(10)]

In [42]: x.count(0), x.count(1), x.count(2)
Out[42]: (5, 3, 2)

Wartość 0 jest losowana wyraźnie częściej, niż inne, w szczególności niż wartość 2. Czyli wracając do pierwszego przypadku osoba1 będzie miała wątpliwą przyjemność wykonywać tę niechcianą czynność częściej niż inni.

Jeśli ktoś twierdzi, że 10 prób to za mało by wyciągać wnioski, nie ma racji. To znaczy ma w tym sensie, że rzeczywiście uzyskanie takiego wyniku w 10 próbach przy "sprawiedliwym" losowaniu nie jest nieprawdopodobne (jeśli komuś się nudzi, może policzyć z jakie jest prawdopodobieństwo takiego wyniku losowania). W tym wypadku jednak nie jest to przypadek.

Funkcja randint zwraca element z przedziału (domkniętego) [0;10]. Wybrana wartość jest poddawana operacji modulo 3 (bo tyle jest osób), a więc wynikiem całości jest zbiór 0, 1 i 2. Przeprowadzamy zbiór składający się z 11(!) elementów w zbiór, który składa się z 3 elementów. Elementy 0, 3, 6 i 9 wskazują na osoba1, 1, 4, 7 i 10 na osoba2, na osoba3 wskazują tylko elementy 2, 5 i 8.

Zakładając, że prawdopodobieństwo wylosowania każdej z tych wartości jest jednakowe, osoba1 i osoba2 są losowane z jednakowym prawdopodobieństwem 4/11 natomiast osoba3 z prawdopodobieństwem 3/11. Różnica może niewielka, ale jest. Gdyby z kolei chodziło o faworyzowanie osoba1, to lepszym rozwiązaniem byłaby sytuacja z modulo 9, każdy może sobie przeliczyć dlaczego.

W tym konkretnym przypadku problem można rozwiązać korzystając z random.choice, co w praktyce sprowadza się do:

    def choice(self, seq):
        """Choose a random element from a non-empty sequence."""
        return seq[int(self.random() * len(seq))]  # raises IndexError if seq is empty

Jest jednak inna kwestia, która czasem może, choć wcale nie musi, powodować problem. Cytując dokumentację:

Python uses the Mersenne Twister as the core generator. It produces 53-bit precision floats and has a period of 2**19937-1. The underlying implementation in C is both fast and threadsafe. The Mersenne Twister is one of the most extensively tested random number generators in existence. However, being completely deterministic, it is not suitable for all purposes, and is completely unsuitable for cryptographic purposes.

Nie zawsze to muszą być zastosowania związane z kryptografią. Jeśli atakujący w jakiś sposób pozna wewnętrzny stan generatora, będzie w stanie przewidzieć kolejne jego wskazania. Jeśli atakującemu daje to jakąkolwiek korzyść, to mamy problem.

Problem możemy rozwiązać korzystając z os.urandom (w przypadku Pythona). Funkcja ta zwraca n (pseudo)losowych bajtów, ale w tym wypadku generator PRNG, z którego one pochodzą, nadaje się do zastosowań kryptograficznych. W tym przypadku jednak mamy n bajtów, jak mając 8 bajtów mamy sprawiedliwie wybrać spośród 3 elementów?

Rozwiązanie z modulo 3 oczywiście nie nadaje się do zastosowania. Prawidłowym rozwiązaniem jest to, które polega na losowaniu do czasu, gdy wylosowana wartość mieści się w przedziale [0;3]. Takie podejście jest oczywiście bardzo nieefektywne, aż 252 możliwe wyniki losowania trzeba konsekwentnie odrzucać.

Można zrobić jeszcze inaczej - sama operacja modulo nie jest taka zła, pod warunkiem, że przedział jest odpowiednio dobrany. W początkowym przykładzie nie byłoby problemu, gdyby pierwsze losowanie odbywało się z przedziałów [0;2] (tu modulo nie jest potrzebne), [0;5], [0;8], [0;11], (...).

Ogólnie jeśli chcemy wybrać element z przedziału 0, ..., n-1 to możemy znaleźć taką wartość k, gdzie 2**k >= n. Tą wartość k wybieramy w sposób dogodny dla nas, czyli na przykład może to być wartość 8, bo 2**8 to 256, co jest zdecydowanie więcej niż 3 (szukamy z wartości z przedziału [0, 2] czyli nasze n to 3), a z generatora dostajemy co najmniej 8 bitów.

W kolejnym kroku wyliczamy pewną wartość q, w ten sposób, że dzielimy (bez reszty) 2**k przez nasze n. W tym wypadku daje nam to 85. Jeśli wybierzemy losowo wartość [0; n*q-1], w tym wypadku [0; 254], a następnie wykonamy operację modulo n (teraz - modulo 3), dostaniemy wartość z interesującego nas przedziału, przy czym każda wartość jest jednakowo prawdopodobna. Najważniejsze jest jednak to, że musimy przy tym losowaniu odrzucać tylko dwa wyniki - 255 i 256, a więc takie podejście jest zdecydowanie bardziej efektywne.

Cały ten wpis to może "oczywiste oczywistości". Dla innych osób kombinowanie z jakimś dziwnym "bezpiecznym" generatorem nie ma sensu, po co się męczyć, skoro są funkcje, które robią to, o co chodzi (np. wspomniany random.choice)? Ja patrzę na to nieco inaczej. Dla mnie jeśli coś ma być losowe, to ma być nieprzewidywalne. Jeśli ma być nieprzewidywalne, to trzeba użyć "bezpiecznego" generatora, a tak się składa, że te "bezpieczne generatory" często nie są obudowane takimi przydatnymi funkcjami.

Jeśli wpis ten czyta ktoś, kto nie do końca potrafi zrozumieć różnicę między "zwykłym" i "bezpiecznym" generatorem liczb pseudolosowych, krótkie wyjaśnienie.

Ten "zwykły" generator liczb pseudolosowych ma to do siebie, że liczby przez niego generowane wcale nie są losowe (w sensie - nieprzewidywalne). Owszem, spełniają określone wymagania statystyczne, ale jeśli zainicjujemy generator w ten sam sposób (seed), to otrzymamy taką samą sekwencję na wyjściu. Taka powtarzalność jest wymagana choćby w symulacjach numerycznych (patrz też: Metoda Monte Carlo). W takich przypadkach powtarzalność symulacji jest nie tyle pożądana co wręcz niezbędna.

Zupełnie inaczej jest w przypadku, gdy wartości muszą być "prawdziwie" losowe. W tym wypadku każda generowana wartość powinna być nieprzewidywalna, atakujący obserwujący wcześniejsze wyjście generatora nie powinien móc przewidzieć kolejnej wygenerowanej wartości. By to osiągnąć generatory zbierają dane (entropię) z różnych źródeł (ruchy myszką, znaki wprowadzane na klawiaturze, ruch sieciowy, praca dysków, itp.) i uwzględniają je przy generowaniu kolejnych wartości.