MaxLevs
@MaxLevs

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

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

Первый - обычный 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)


Может кто объяснить?
  • Вопрос задан
  • 135 просмотров
Решения вопроса 1
@deliro
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]]
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@Stormx480
Python Backend Developer
Ну если тебе нужно что бы этого не происходило ты можешь это ограничить. Сначала "заролять" одну функцию, потом другую с условием что бы результат не был равен результату предыдущей функции.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы