Ожидаемое число: я буду после розыгрыша карт, пока не получу туза, 2, 3 и т. Д.

12

У меня возникли проблемы с решением следующего.

Вы берете карты из стандартной колоды из 52 карт без замены, пока не получите туза. Вы вытягиваете из того, что осталось, пока не получите 2. Вы продолжаете с 3. Какое ожидаемое число вы будете иметь после того, как закончится вся колода?

Было естественно позволить

  • Ti=first position of card whose value is i
  • Ui=last position of card whose value is i

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

Pr(T1<<TkUk+1<Tk)

Я это вижу

Pr(T1<<Tk)=1/k!andPr(Uk+1<Tk)=1/70

но не мог получить дальше ...

счет
источник
1
Что произойдет, если вы уже разыграли все секунды к моменту, когда вы разыграли своего первого туза? 2
gung - Восстановить Монику
Действительно ли «ожидаемое» число означает «наиболее вероятное» число?
whuber
Это интересная проблема, но я не уверен насчет математики, которую вы пишете после того, как «проблема, по сути, составляет». В первом утверждении вы хотели написать а не ? Однако даже тогда я не уверен, что утверждение верно. Рассмотрим начало последовательности . У нас есть и т. Д. , но если я правильно понимаю ваше текстовое описание, мы все равно можем выбрать туза во второй позиции, а затем 2 в пятой позиции? И поэтому не является необходимым условием? T 1 = 2 , Т 2 = 1 Т 1 > Т 2 Т 1 < Т 22AAA2T1=2,T2=1T1>T2T1<T2
TooTone
@ ToTone О, я имел в виду как ты сказал, и ты прав; не является обязательным условием ...T 1 < T 2T1<T2
счет
@gung В этом случае ваша колода иссякнет, и вы все равно будете на 2.
счет

Ответы:

0

Следуя идее @ Gung, я думаю, что ожидаемое значение будет 5,84? и из моей интерпретации комментариев я предполагаю, что «А» является почти невозможным значением (если только последние четыре карты в колоде не являются тузами). Вот результаты моделирования 10000 итераций Монте-Карло

results
    2     3     4     5     6     7     8     9     J     K     Q     T 
 1406  7740 16309 21241 19998 15127  9393  4906   976   190   380  2334 

и вот код R на тот случай, если вы захотите поиграть с ним ..

# monte carlo card-drawing functions from here
# http://streaming.stat.iastate.edu/workshops/r-intro/lectures/5-Rprogramming.pdf

# create a straightforward deck of cards
create_deck <-
    function( ){
        suit <- c( "H" , "C" , "D" , "S" )
        rank <- c( "A" , 2:9 , "T" , "J" , "Q" , "K" )
        deck <- NULL
        for ( r in rank ) deck <- c( deck , paste( r , suit ) )
        deck
    }

# construct a function to shuffle everything
shuffle <- function( deck ){ sample( deck , length( deck ) ) }

# draw one card at a time
draw_cards <-
    function( deck , start , n = 1 ){
        cards <- NULL

        for ( i in start:( start + n - 1 ) ){
            if ( i <= length( deck ) ){
                cards <- c( cards , deck[ i ] )
            }
        }

        return( cards )
    }

# create an empty vector for your results
results <- NULL

# run your simulation this many times..
for ( i in seq( 100000 ) ){
    # create a new deck
    sdeck <- shuffle( create_deck() )

    d <- sdeck[ grep('A|2' , sdeck ) ]
    e <- identical( grep( "2" , d ) , 1:4 )

    # loop through ranks in this order
    rank <- c( "A" , 2:9 , "T" , "J" , "Q" , "K" )

    # start at this position
    card.position <- 0

    # start with a blank current.draw
    current.draw <- ""

    # start with a blank current rank
    this.rank <- NULL

    # start with the first rank
    rank.position <- 1

    # keep drawing until you find the rank you wanted
    while( card.position < 52 ){

        # increase the position by one every time
        card.position <- card.position + 1

        # store the current draw for testing next time
        current.draw <- draw_cards( sdeck , card.position )

        # if you draw the current rank, move to the next.
        if ( grepl( rank[ rank.position ] , current.draw ) ) rank.position <- rank.position + 1

        # if you have gone through every rank and are still not out of cards,
        # should it still be a king?  this assumes yes.
        if ( rank.position == length( rank ) ) break        

    }

    # store the rank for this iteration.
    this.rank <- rank[ rank.position ]

    # at the end of the iteration, store the result
    results <- c( results , this.rank )

}

# print the final results
table( results )

# make A, T, J, Q, K numerics
results[ results == 'A' ] <- 1
results[ results == 'T' ] <- 10
results[ results == 'J' ] <- 11
results[ results == 'Q' ] <- 12
results[ results == 'K' ] <- 13
results <- as.numeric( results )

# and here's your expected value after 100,000 simulations.
mean( results )
Энтони Дамико
источник
Почему Aневозможно? Рассмотрим последовательность из 48 карт, а затем, AAAAнапример.
TooTone
вы правы .. это один из 270725 - или с кодом R1/prod( 48:1 / 52:5 )
Энтони Дамико
1
Этот ответ неверен. Рассмотрим счет для «2»: поскольку это может произойти только тогда, когда все 2 встречаются до любого из 1, его вероятность равна единице в каждом и поэтому его ожидание в вашей симуляции равно со стандартной ошибкой . Ваш вывод превышает шесть стандартных ошибок слишком высоко, что делает его почти наверняка ошибочным. Точное значение для среднего значения (на основе другого моделирования с итерациями) составляет . 105/ ( 8(84)=70105/(84)1428.637.510 6 5,833 ± 0,00416601065.833±0.004
whuber
1
К сожалению, ваш сильно документированный код в несколько раз длиннее и медленнее, чем нужно. Я продемонстрировал, что его вывод неверен; хотя я бы хотел, чтобы у меня было время для отладки вашего кода, у меня его нет, и это не моя задача. Мой аргумент таков: вы все равно будете работать с «2» в конце, если и только если все «2» предшествуют всем «А». Среди одинаково вероятных способов расстановки четырех «2» и четырех «А» точно один из них удовлетворяет этому критерию. Поэтому ваше значение под заголовком «2» должно быть близко к , но это не так. 105/70=1429(4+44)=70results105/70=1429
whuber
1
Даже модераторы не могут удалить голоса других людей :-). Тест хи-квадрат теперь предполагает, что ваши результаты согласуются с моими, но было бы неплохо узнать, как вы тестировали симуляцию, потому что это повысило бы уверенность в вашем ответе. В самом деле, согласно редактированию вы сделали первый абзац в своем ответе, в настоящее время оба наших результаты не так: как я интерпретировал ваш вопрос, это не никогда возможно еще будет работать над тузом , когда все карты будут исчерпаны.
whuber
7

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

#
# Simulate one play with a deck of `n` distinct cards in `k` suits.
#
sim <- function(n=13, k=4) {
  deck <- sample(rep(1:n, k)) # Shuffle the deck
  deck <- c(deck, 1:n)        # Add sentinels to terminate the loop
  k <- 0                      # Count the cards searched for
  for (j in 1:n) {
    k <- k+1                          # Count this card
    deck <- deck[-(1:match(j, deck))] # Deal cards until `j` is found
    if (length(deck) < n) break       # Stop when sentinels are reached
  }
  return(k)                   # Return the number of cards searched
}

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

> set.seed(17);  system.time(d <- replicate(10^5, sim(13, 4)))
   user  system elapsed 
   5.46    0.00    5.46

Это медленно, но достаточно быстро, чтобы проводить довольно длительные (и, следовательно, точные) симуляции многократно без ожидания. Есть несколько способов показать результат. Давайте начнем с его значения:

> n <- length(d)
> mean(d)
[1] 5.83488

> sd(d) / sqrt(n)
[1] 0.005978956

Последнее является стандартной ошибкой: мы ожидаем, что смоделированное среднее значение будет в пределах двух или трех SE от истинного значения. Это ставит истинное ожидание где-то между и5,8535.8175.853 .

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

u <- table(d)
u.se <- sqrt(u/n * (1-u/n)) / sqrt(n)
cards <- c("A", "2", "3", "4", "5", "6", "7", "8", "9", "T", "J", "Q", "K")
dimnames(u) <- list(sapply(dimnames(u), function(x) cards[as.integer(x)]))
print(rbind(frequency=u/n, SE=u.se), digits=2)

Вот вывод:

                2       3      4      5      6      7       8       9       T       J       Q       K
frequency 0.01453 0.07795 0.1637 0.2104 0.1995 0.1509 0.09534 0.04995 0.02249 0.01009 0.00345 0.00173
SE        0.00038 0.00085 0.0012 0.0013 0.0013 0.0011 0.00093 0.00069 0.00047 0.00032 0.00019 0.00013

Как мы можем знать, что симуляция даже правильна? Одним из способов является его тщательное тестирование на небольшие проблемы. По этой причине этот код был написан, чтобы атаковать небольшое обобщение проблемы, заменяя различных карт на и масти на . Однако для тестирования важно иметь возможность кормить код колодой в заранее определенном порядке. Давайте напишем немного другой интерфейс для того же алгоритма:413n4k

draw <- function(deck) {
  n <- length(sentinels <- sort(unique(deck)))
  deck <- c(deck, sentinels)
  k <- 0
  for (j in sentinels) {
    k <- k+1
    deck <- deck[-(1:match(j, deck))]
    if (length(deck) < n) break
  }
  return(k)
}

(Можно использовать drawвместо simвезде, но дополнительная работа в начале drawделает его в два раза медленнее sim.)

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

n <- 4 # Distinct cards
k <- 2 # Number of suits
d <- expand.grid(lapply(1:(n*k), function(i) 1:n))
e <- apply(d, 1, function(x) var(tabulate(x))==0)
g <- apply(d, 1, function(x) length(unique(x))==n)
d <- d[e & g,]

Теперь dэто фрейм данных, строки которого содержат все тасования. Применить drawк каждой строке и подсчитать результаты:

d$result <- apply(as.matrix(d), 1, draw)
    (counts <- table(d$result))

Выход (который мы будем использовать в формальном тесте на мгновение)

   2    3    4 
 420  784 1316 

( Кстати, значение легко понять: мы все равно будем работать с картой если и только если все двойки предшествуют всем тузам. Вероятность этого (с двумя мастями) равна . Из различных обладают этим свойством.)2 1 / ( 2 + 2420225202520/6=4201/(2+22)=1/625202520/6=420

Мы можем проверить вывод с помощью критерия хи-квадрат. С этой целью я применяю раз для этого случая различных карт в мастях:sim п = 4 к = 210,000n=4k=2

>set.seed(17)
>d.sim <- replicate(10^4, sim(n, k))
>print((rbind(table(d.sim) / length(d.sim), counts / dim(d)[1])), digits=3)

         2     3     4
[1,] 0.168 0.312 0.520
[2,] 0.167 0.311 0.522

> chisq.test(table(d.sim), p=counts / dim(d)[1])

    Chi-squared test for given probabilities

data:  table(d.sim) 
X-squared = 0.2129, df = 2, p-value = 0.899

Поскольку настолько велико, мы не видим существенной разницы между тем, что говорится, и значениями, вычисленными с помощью исчерпывающего перечисления. Повторение этого упражнения для некоторых других (малых) значений и дает сопоставимые результаты, что дает нам достаточно оснований доверять применительно к и .н кpsimnksimк = 4n=13k=4

Наконец, тест хи-квадрат с двумя выборками будет сравнивать выходные данные simс результатами, полученными в другом ответе:

>y <- c(1660,8414,16973,21495,20021,14549,8957,4546,2087,828,313,109)
>chisq.test(cbind(u, y))

data:  cbind(u, y) 
X-squared = 142.2489, df = 11, p-value < 2.2e-16

Огромная статистика хи-квадрат дает p-значение, которое по существу равно нулю: без сомнения, simне согласен с другим ответом. Есть два возможных решения разногласий: один (или оба!) Из этих ответов неверен или они реализуют различные интерпретации вопроса. Например, я интерпретировал «после того, как колода закончилась», чтобы означать после просмотра последней карты и, если это допустимо, обновления «номера, на котором вы будете» перед завершением процедуры. Возможно, этот последний шаг не должен был быть сделан. Возможно, какое-то столь тонкое различие в интерпретации объяснит разногласия, и в этот момент мы сможем изменить вопрос, чтобы сделать его более понятным.

Whuber
источник
4

Существует точный ответ (в виде матричного произведения, представленного в пункте 4 ниже). Существует достаточно эффективный алгоритм для его вычисления, основанный на следующих наблюдениях:

  1. Случайное перемешивание из карт может быть сгенерировано путем случайного перемешивания карт и затем случайным образом перемежая оставшиеся карт в них.Н КN+kNk

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

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

    Представьте себе метку на первом тузе, а затем отметьте первых двух, найденных после него, и так далее. (Если на каком-либо этапе колода заканчивается без отображения карты, которую мы ищем, мы оставим все карты без отметки.) Пусть «место» каждой отметки (если она существует) будет числом карт равного или меньшего значения, которое были сданы, когда была сделана отметка (включая саму помеченную карточку). Места содержат всю необходимую информацию.

  4. Место после метки является случайным числом. Для данной колоды последовательность этих мест образует стохастический процесс. Фактически это марковский процесс (с переменной матрицей перехода). Таким образом, точный ответ можно рассчитать по двенадцати умножениям матриц.ith

Используя эти идеи, эта машина получает значение (вычисление с плавающей запятой двойной точности) за секунды. Это приближение точного значения является точным для всех отображаемых цифр.1 / 9 19826005792658947850269453319689390235225425695.83258855290199651/9

1982600579265894785026945331968939023522542569339917784579447928182134345929899510000000000

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


Генерация случайных тасов колоды

На самом деле концептуально яснее и не сложнее математически рассматривать «колоду» (она же мультимножество ) из карт, из которых самого младшего достоинства, следующего младшего и т. Д. , (Заданный вопрос касается колоды, определяемой вектором .)N=k1+k2++kmk1 13 ( 4 , 4 , , 4 )k213(4,4,,4)

«Случайное перемешивание» из карт - это одна перестановка, взятая равномерно и случайным образом из перестановок из карт. Эти тасования попадают в группы эквивалентных конфигураций, потому что перестановка «тузов» между собой ничего не меняет, перестановка «двойки» между собой также ничего не меняет и так далее. Поэтому каждая группа перестановок, которые выглядят одинаково, когда масти карт игнорируются, содержитПерестановки. Эти группы, число которых определяется множителемN ! = N × ( N - 1 ) × × 2 × 1 N k 1 k 2 k 1 ! × k 2 ! × × k м !NN!=N×(N1)××2×1Nk1k2k1!×k2!××km!

(Nk1,k2,,km)=N!k1!k2!km!,

называются «комбинации» колоды.

Есть еще один способ подсчета комбинаций. Первые карты могут образовывать только комбинация. Они оставляют «слоты» между ними и вокруг них, в которые могут быть помещены следующие карты. Мы могли бы указать это на диаграмме, где " " обозначает одну из карт а " " обозначает слот, который может содержать от до дополнительных карт:k1k1!/k1!=1k1+1k2k1_0k2

_____k1 stars

Когда дополнительные карты чередуются, шаблон звезд и новые карты карты на два подмножества. Число различных таких подмножеств: .k2k1+k2(k1+k2k1,k2)=(k1+k2)!k1!k2!

Повторяя эту процедуру с «тройки», мы обнаруживаем, что есть способы перемежать их среди первых карт. Поэтому общее количество различных способов упорядочить первые таким образом равноk3((k1+k2)+k3k1+k2,k3)=(k1+k2+k3)!(k1+k2)!k3!k1+k2k1+k2+k3

1×(k1+k2)!k1!k2!×(k1+k2+k3)!(k1+k2)!k3!=(k1+k2+k3)!k1!k2!k3!.

После завершения последних карт и продолжения умножения этих телескопических дробей мы находим, что количество полученных различных комбинаций равно общему количеству комбинаций, как было подсчитано ранее, . Поэтому мы не заметили никаких комбинаций. Это означает, что этот последовательный процесс перетасовки карт правильно фиксирует вероятности каждой комбинации, предполагая, что на каждом этапе каждый возможный особый способ разделения новых карт среди старых выбирается с одинаково равной вероятностью.kn(Nk1,k2,,km)

Процесс места

Первоначально есть тузов и, очевидно, отмечен самый первый. На более поздних стадиях есть карт, место (если существует отмеченная карта) равно (некоторое значение от до ), и мы собираемся перемежать карты вокруг них. Мы можем визуализировать это с помощью диаграммы, какk1n=k1+k2++kj1p1nk=kj

_____p1 stars____np stars

где " " обозначает отмеченный символ. Условно по этому значению места мы хотим найти вероятность того, что следующее место будет равно (какое-то значение от до ; по правилам игры следующее место должно идти после , откуда ). Если мы сможем найти, сколько существует способов перебросить новых карт в пробелах так, чтобы следующее место равнялось , то мы можем разделить на общее количество способов перемежать эти карты (равное , как мы видели), чтобы получитьpq1n+kpqp+1kq(n+kk)вероятность перехода, что место меняется с на . (Также будет вероятность перехода к тому, что место полностью исчезнет, ​​когда ни одна из новых карт не будет следовать за отмеченной картой, но нет необходимости вычислять это явно.)pq

Давайте обновим диаграмму, чтобы отразить эту ситуацию:

_____p1 starss stars | ____nps stars

Вертикальная полоса « » показывает , где происходит первое новой карты после отмеченной карты: не новые карты не могут , следовательно , появляется между и (и , следовательно , нет слота не показаны на этом интервале). Мы не знаем, сколько звезд в этом интервале, поэтому я только что назвал его (который может быть нулем). Неизвестные исчезнут, как только мы найдем связь между ним и .||ssq

Предположим, что затем мы разбрасываем новых карт вокруг звезд до а затем - независимо от этого - мы чередуем оставшиеся новые карты вокруг звезд после . Естьjkj1|

τn,k(s,p)=((p1)+jj)((nps)+(kj)1kj1)

способы сделать это. Обратите внимание, что - это самая сложная часть анализа - что место равно потому что|p+s+j+1

  • Есть "старых" карт в или до знака.p
  • Есть старые карты после знака , но перед .s|
  • Перед маркой есть новых карт.j
  • Есть новая карта, представленная самим .|

Таким образом, дает нам информацию о переходе от места к месту . Когда мы тщательно отслеживаем эту информацию для всех возможных значений и суммируем все эти (непересекающиеся) возможности, мы получаем условную вероятность места после места ,τn,k(s,p)pq=p+s+j+1sqp

Prn,k(q|p)=(j(p1+jj)(n+kqkj1))/(n+kk)

где сумма начинается в и заканчивается в . (Переменная длина этой суммы предполагает, что есть вряд ли это будет замкнутая формула для него как функция от и , за исключением особых случаев.)j=max(0,q(n+1))j=min(k1,q(p+1)n,k,q,p

Алгоритм

Первоначально существует вероятность что место будет а вероятность будет иметь любое другое возможное значение в . Это может быть представлено вектором .1102,3,,k1p1=(1,0,,0)

После разбрасывания следующих карт вектор обновляется до путем умножения его (слева) на матрицу перехода . Это повторяется до тех пор, пока не будут размещены все карты . На каждом этапе сумма записей в векторе вероятности - это вероятность того, что какая-либо карта была помечена. То, что осталось сделать значение равным - это вероятность того, что после шага не останется ни одной карты.k2p1p2(Prk1,k2(q|p),1pk1,1qk2)k1+k2++kmjpj1j, Таким образом, последовательные различия в этих значениях дают нам вероятность того, что мы не смогли найти карту типа для отметки: это распределение вероятностей значения карты, которую мы искали, когда колода заканчивается в конце игры. ,j


Реализация

Следующий Rкод реализует алгоритм. Это параллельно предыдущему обсуждению. Во-первых, вычисление вероятностей перехода выполняется t.matrix(без нормализации с делением на , что облегчает отслеживание вычислений при тестировании кода):(n+kk)

t.matrix <- function(q, p, n, k) {
  j <- max(0, q-(n+1)):min(k-1, q-(p+1))
  return (sum(choose(p-1+j,j) * choose(n+k-q, k-1-j))
}

Это используется transitionдля обновления до . Он рассчитывает матрицу переходов и выполняет умножение. Это также заботится о вычислении начального вектора если аргумент является пустым вектором:pj1pjp1p

#
# `p` is the place distribution: p[i] is the chance the place is `i`.
#
transition <- function(p, k) {
  n <- length(p)
  if (n==0) {
    q <- c(1, rep(0, k-1))
  } else {
    #
    # Construct the transition matrix.
    #
    t.mat <- matrix(0, nrow=n, ncol=(n+k))
    #dimnames(t.mat) <- list(p=1:n, q=1:(n+k))
    for (i in 1:n) {
      t.mat[i, ] <- c(rep(0, i), sapply((i+1):(n+k), 
                                        function(q) t.matrix(q, i, n, k)))
    }
    #
    # Normalize and apply the transition matrix.
    #
    q <- as.vector(p %*% t.mat / choose(n+k, k))
  }
  names(q) <- 1:(n+k)
  return (q)
}

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

#
# `k` is an array giving the numbers of each card in order;
# e.g., k = rep(4, 13) for a standard deck.
#
# NB: the *complements* of the p-vectors are output.
#
game <- function(k) {
  p <- numeric(0)
  q <- sapply(k, function(i) 1 - sum(p <<- transition(p, i)))
  names(q) <- names(k)
  return (q)
}

Вот они для стандартной колоды:

k <- rep(4, 13)
names(k) <- c("A", 2:9, "T", "J", "Q", "K")
(g <- game(k))

Выход

         A          2          3          4          5          6          7          8          9          T          J          Q          K 
0.00000000 0.01428571 0.09232323 0.25595013 0.46786622 0.66819134 0.81821790 0.91160622 0.96146102 0.98479430 0.99452614 0.99818922 0.99944610

Согласно правилам, если король был помечен, то мы не будем искать другие карты: это означает, что значение должно быть увеличено до . При этом различия дают распределение «числа, на котором вы будете, когда закончится колода»:0.99944611

> g[13] <- 1; diff(g)
          2           3           4           5           6           7           8           9           T           J           Q           K 
0.014285714 0.078037518 0.163626897 0.211916093 0.200325120 0.150026562 0.093388313 0.049854807 0.023333275 0.009731843 0.003663077 0.001810781

(Сравните это с результатом, о котором я сообщаю в отдельном ответе, описывающем моделирование по методу Монте-Карло: они кажутся одинаковыми, вплоть до ожидаемого количества случайных изменений.)

Ожидаемое значение является немедленным:

> sum(diff(g) * 2:13)
[1] 5.832589

В общем, для этого требовалось всего около десятка строк исполняемого кода. Я проверил это с помощью ручных расчетов для малых значений (до ). Таким образом, если какое-либо несоответствие становится очевидным между кодом и предшествующим анализом проблемы, доверяйте коду (потому что анализ может иметь опечатки).k3


замечания

Отношения с другими последовательностями

Когда есть одна из каждой карты, распределение представляет собой последовательность обратных целых чисел:

> 1/diff(game(rep(1,10)))
[1]      2      3      8     30    144    840   5760  45360 403200

Значение на месте это(начиная с места ). Это последовательность A001048 в онлайн-энциклопедии целочисленных последовательностей. Соответственно, мы могли бы надеяться на закрытую формулу для колод с константой («подходящих» колод), которая обобщала бы эту последовательность, которая сама по себе имеет некоторые глубокие значения. (Например, он подсчитывает размеры наибольших классов сопряженности в группах перестановок и также связан с триномиальными коэффициентами .) (К сожалению, обратные значения в обобщении для обычно не являются целыми числами.)ii!+(i1)!i=1kik>1

Игра как случайный процесс

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

> sapply(1:13, function(i) game(rep(4,i)))

[[1]]
[1] 0

[[2]]
[1] 0.00000000 0.01428571

[[3]]
[1] 0.00000000 0.01428571 0.09232323

[[4]]
[1] 0.00000000 0.01428571 0.09232323 0.25595013

...

[[13]]
 [1] 0.00000000 0.01428571 0.09232323 0.25595013 0.46786622 0.66819134 0.81821790 0.91160622 0.96146102 0.98479430 0.99452614 0.99818922 0.99944610

Например, второе значение окончательного вектора (описывающее результаты с полной колодой из 52 карт) уже появилось после обработки второй группы (и равно ). Таким образом, если вы хотите получить информацию только о разметке через значение карты , вам нужно выполнить расчет только для колоды из карт.1/(84)=1/70jthk1+k2++kj

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

тайминг

Глядя на алгоритм, примененный к вектору , мы видим, что его время должно быть пропорционально и - используя грубую верхнюю границу - не хуже, чем пропорционально . По синхронизации все вычисления для через и через , и анализируя только те , кто принимает относительно длительного времени ( секунды или дольше), я оценить время вычисления приблизительно , поддерживая эту оценку сверху.( к , к , ... , K ) K 2 м 3 K = 1 7 п = 10 30 1 / 2 O ( K 2 н 2.9 )m(k,k,,k)k2m3k=17n=10301/2O(k2n2.9)

Одним из применений этих асимптотик является прогнозирование времени расчета для более крупных задач. Например, учитывая, что случай занимает около секунды, мы оценили бы, что (очень интересный) случай займет около секунды. (На самом деле это занимает секунды.)1,31 к = 1 , п = 100 1,31 ( 1 / 4 ) 2 ( 100 / 30 ) 2,92,7 2,87k=4,n=301.31k=1,n=1001.31(1/4)2(100/30)2.92.72.87

Whuber
источник
0

Взломал простой Монте-Карло в Perl и нашел примерно .5.8329

#!/usr/bin/perl

use strict;

my @deck = (1..13) x 4;

my $N = 100000; # Monte Carlo iterations.

my $mean = 0;

for (my $i = 1; $i <= $N; $i++) {
    my @d = @deck;
    fisher_yates_shuffle(\@d);
    my $last = 0;
        foreach my $c (@d) {
        if ($c == $last + 1) { $last = $c }
    }
    $mean += ($last + 1) / $N;
}

print $mean, "\n";

sub fisher_yates_shuffle {
    my $array = shift;
        my $i = @$array;
        while (--$i) {
        my $j = int rand($i + 1);
        @$array[$i, $j] = @$array[$j, $i];
    }
}
Zen
источник
Учитывая резкое несоответствие между этим и всеми предыдущими ответами, включая два моделирования и теоретический (точный), я подозреваю, что вы интерпретируете вопрос по-другому. В отсутствие каких-либо объяснений с вашей стороны, мы просто должны принять это как неправильное. (Я подозреваю, что вы можете считать на один меньше, и в этом случае ваши 4.8 должны сравниваться с 5.83258 ...; но даже в этом случае ваши две значащие цифры точности не дают дополнительного понимания этой проблемы.)
whuber
1
Ага! Произошла ошибка.
Дзен