Почему это не кажется случайным?

Question

Я выполнял процедуру, чтобы быть похожей на одну из этих игр, когда люди пытались угадать число от 0 до 100, где угадывают 100 человек. Затем я усреднил количество различных догадок.

import random 
def averager(times): 
    tests=[] 
    for i in range(times): 
     l=[] 
     for i in range(0,100): 
      l.append(random.randint(0,100)) 
     tests.append(len(set(l))) 
    return (sum(tests))/len(tests) 

print(averager(1000)) 

По какой-то причине, число различных догадок в среднем составляет 63,6

Почему это? Является ли это из-за недостатка в питон случайной библиотеке?

В сценарии, где люди гадали число между 1 и 10

Первый человек имеет 100% шанс угадать ранее unguessed номер

Второй человек имеет 90% шанс угадать ранее unguessed номер

Третий человек имеет 80% шанс угадать ранее unguessed номер

и так далее ...

Средний шанс угадать новый номер (по моим рассуждениям) составляет 55%. Но данные не отражают это.

Answer 1

Ваш кода для нахождения средних ряда уникальных догадок из 100 людей каждых угадать число от 1 до 100. А почему она сходится к ряду около 63 ... Вы должны опубликовать свой вопрос математическая стековая биржа.

Answer 2

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

Все, что вы здесь делаете, измеряет какую-то уникальность в пределах очень малых множеств: т.е. 1000 повторений эксперимента, включающего 100 случайных значений. Вы можете лучше оценить это, если вы используете какой-то алгоритм начальной загрузки для выборки.

Кроме того, если вы увеличиваете количество повторений до миллионов и, возможно, измеряете распределение выборки (а не только среднее значение), вы получите немного больше уверенности в результатах, которые вы получаете.

Возможно, что псевдослучайный генератор имеет характеристику, которая дает примерно 60-70% не повторяющихся значений внутри последовательности той же длины, что и диапазон. Однако вам нужно будет экспериментировать с гораздо большим количеством образцов, а также с разными случайными семенами. В противном случае ваши результаты не имеют смысла.

Answer 3

Я изменил свой код, чтобы он бы уже сгенерированную последовательность в качестве входных данных, а не расчета случайных чисел:

def averager(seqs): 
    tests = [] 
    for s in seqs: 
     tests.append(len(set(s))) 
    return float(sum(tests))/len(tests) 

Тогда я сделал функцию, чтобы вернуть все возможные варианты для любого заданного числа людей и диапазон догадка:

def combos(n, limit): 
    return itertools.product(*((range(limit),) * n)) 

(Одна из вещей, которые я любовь о Python является то, что это так легко распадаться функцию в тривиальные части.)

Тогда я начал тестирование с увеличением числа:

for n in range(2,100): 
    x = averager(combos(n, n)) 
    print n, x, x/n 

2 1.5 0.75 
3 2.11111111111 0.703703703704 
4 2.734375 0.68359375 
5 3.3616 0.67232 
6 3.99061213992 0.66510202332 
7 4.62058326038 0.660083322911 
8 5.25112867355 0.656391084194 

Этот алгоритм имеет ужасный сложность, поэтому на данный момент я получил MemoryError. Как вы можете видеть, процент уникальных результатов продолжает снижаться по мере увеличения количества людей и диапазона гаданий.

Повторение теста со случайными числами:

def rands(repeats, n, limit): 
    for i in range(repeats): 
     yield [random.randint(0, limit) for j in range(n)] 

for n in range(10, 101, 10): 
    x = averager(rands(10000, n, n)) 
    print n, x, x/n 

10 6.7752 0.67752 
20 13.0751 0.653755 
30 19.4131 0.647103333333 
40 25.7309 0.6432725 
50 32.0471 0.640942 
60 38.3333 0.638888333333 
70 44.6882 0.638402857143 
80 50.948 0.63685 
90 57.3525 0.63725 
100 63.6322 0.636322 

Как вы можете видеть, что результаты согласуются с тем, что мы видели ранее, и с вашим собственным наблюдением. Я уверен, что комбинаторная математика может объяснить все это.