Какова вероятность получить идентичные последовательности?

Question

[sudo rm -rf /]

Есть два варианта получить последовательность чисел

Первый - обычный shuffle

def get_seq1(N=10):
    from random import shuffle
    seq1 = [X for X in range(N)]
    shuffle(seq1)
    return seq1

Второй внешне напоминает работу простого уличного лототрона

def get_seq2(N=10):
    from random import shuffle
    from random import randrange
    seq2 = []
    numbers = [X for X in range(N)]
    for _ in range(N):
        shuffle(numbers)
        seq2.append(numbers.pop(randrange(0, len(numbers))))
    return seq2

Мне интересно, совпадают ли в этих двух подходах вероятности получить идентичные последовательности.

seq11 = get_seq1()
seq12 = get_seq1()
print(seq11 == seq12)

seq21 = get_seq2()
seq22 = get_seq2()
print(seq21 == seq22)

Может кто объяснить?

Answer 1

[Roman K]

get_seq2 не делает ничего полезного, если тебе не нужны какие-то промежуточные результаты. Распределения get_seq1 и get_seq2 совпадают. Только get_seq2 работает в 7 раз медленней.

Очевидно, раз распределения совпадают, то вероятность получить одинаковую последовательность такая же, как вероятность получить её внутри одной функции — P(get_seq1() == get_seq1()) == P(get_seq1() == get_seq2()) == 1 / N * 1 / N-1 * ... * 1/1, где N - длина последовательности

Распределение очень просто измерить:

def measure(fn):
    n = 10
    p = []
    for _ in range(10):
        p.append([0] * n)
        
    for _ in range(10**6):
        seq = fn(n)
        for i, el in enumerate(seq):
            p[el][i] += 1
            
    return p

И получаем матрицы, которые показывают, как часто элемент (строка) встречается на определённом индексе (столбец). При устремлении n к бесконечности, они уравняются и в том, и в другом случае. Значит, распределение у них равное и выбрасывай функцию №2

>>> measure(get_seq1)
[[99919, 100094, 99918, 100106, 100275, 100068, 100154, 99995, 100254, 99217],
 [99766, 100119, 100263, 99692, 99904, 99946, 100378, 99573, 100052, 100307],
 [100470, 100170, 99583, 100699, 99723, 99924, 99743, 100296, 99856, 99536],
 [100373, 100060, 99779, 99566, 99761, 99850, 100135, 100109, 100081, 100286],
 [100187, 99933, 99528, 100120, 99986, 99897, 99798, 100082, 100220, 100249],
 [100357, 99866, 99828, 99928, 100218, 100322, 100546, 99774, 99675, 99486],
 [99533, 99710, 100332, 99507, 100526, 100117, 99435, 100356, 100378, 100106],
 [99571, 100246, 99968, 100280, 100162, 99406, 99907, 100185, 99752, 100523],
 [99913, 99821, 100573, 99876, 99931, 100207, 99895, 99962, 100054, 99768],
 [99911, 99981, 100228, 100226, 99514, 100263, 100009, 99668, 99678, 100522]]

>>> measure(get_seq2)
[[99740, 100055, 99943, 99346, 99970, 100129, 100306, 99887, 100170, 100454],
 [100324, 100029, 99635, 100189, 99822, 100019, 99970, 100613, 99778, 99621],
 [99487, 100227, 100431, 99973, 99767, 99982, 100256, 100325, 99777, 99775],
 [99974, 99739, 100295, 100221, 99926, 100097, 99134, 100275, 99841, 100498],
 [100091, 99770, 99578, 99967, 100364, 100097, 99820, 99565, 100747, 100001],
 [99874, 99914, 100011, 99799, 99947, 99854, 100629, 99938, 100135, 99899],
 [100143, 100200, 99946, 100157, 99754, 99598, 100223, 99860, 99747, 100372],
 [100095, 100058, 100037, 100209, 100549, 100335, 99759, 99231, 100087, 99640],
 [100117, 99971, 99967, 100017, 99682, 99696, 100147, 100634, 99514, 100255],
 [100155, 100037, 100157, 100122, 100219, 100193, 99756, 99672, 100204, 99485]]

Answer 2

[Михаил Трайнин]

Ну если тебе нужно что бы этого не происходило ты можешь это ограничить. Сначала "заролять" одну функцию, потом другую с условием что бы результат не был равен результату предыдущей функции.

Ну а вообще это все ограничивается теорией вероятности. Шанс что тебе выпадет одно число из 10 - 1/10 соответственно. Шанс что тебе выпадет одно и тоже число из 10 дважды - 1/10*10 = 0.01.
Нужно понимать что шанс выпадения у любого элемента списка одинаковый. Т.е. шанс того что выпадет 5 такой же, как шанс того что выпадет 6. Соответственно для получения вероятности последовательности это все надо переумножить, формулу я уже не помню честно говоря, поищи в интернете. Ну попытаюсь логично подумать и просто возвести это все в 10 степень. т.е. 0.01^10 это будет примерно 1.0E-20

Вот тут есть хорошая статья на тему теории вероятности и случайности. Примеры на игральных костях, но думаю Вам она сгодится, на досуге советую почитать, интересная вещь.

Comments

[sudo rm -rf /]

"Мне интересно" (c)
Было бы здорово почитать про оба приведенных мной варианта, а также сравнение.

[Михаил Трайнин]

sudo rm -rf /, Если вы прочитаете мой ответ внимательно, то найдете ответ на свой вопрос. Если вам интересна практическая сторона вопроса, то можете написать скрипт который будет ролять значения до тех пор пока они не совпадут, а потом вывести кол-во попыток. Что то типо:

from random import shuffle
from random import randrange

def get_seq1(N=10):
    seq1 = [X for X in range(N)]
    shuffle(seq1)
    return seq1

def get_seq2(N=10):
    seq2 = []
    numbers = [X for X in range(N)]
    for _ in range(N):
        shuffle(numbers)
        seq2.append(numbers.pop(randrange(0, len(numbers))))
    return seq2


def random():
    att = 0
    seq11 = [7,0,9,3,2,1,4,5,6,8]
    seq12 = [5,6,7,3,9,4,1,2,8,0]
    while seq11 != seq12:
        print(att)
        seq11 = get_seq1()
        seq12 = get_seq2()
        att += 1

if __name__ == "__main__":
    random()