Qual a chance de ganhar um prêmio por porta?

12

Meu capítulo local da ACM oferece prêmios para as pessoas que comparecem às reuniões. Você tem uma chance maior de ganhar se resolver o quebra-cabeça de programação, no entanto (mas eu sempre resolvo esse quebra-cabeça). Assim, algumas pessoas têm 1 entrada, enquanto outras têm 2. Mas espere! A maneira como o programa de sorteio funciona não é adicionando outra entrada quando alguém resolve o quebra-cabeça. Em vez disso, ele controla o número de "vidas" que uma pessoa tem, diminuindo que, se essa pessoa for escolhida em cada passagem do seu algoritmo de amostragem aleatória. Então, funciona assim:

Doorknob: 1.  xnor: 2.  Justin: 2.  Alex: 1.  Dennis: 2.

Em seguida, o programa escolhe aleatoriamente um dos [Doorknob, xnor, Justin, Alex, Dennis], diminui o número (diga que ele escolhe Justin):

Doorknob: 1.  xnor: 2.  Justin: 1.  Alex: 1. Dennis: 2.

E repete. Se o número de "vidas" de alguém for para 0(vamos escolher Justinnovamente), eles serão removidos da lista:

Doorknob: 1.  xnor: 2.  Alex: 1.  Dennis: 2.

Isso continua até que haja uma pessoa; essa pessoa é a vencedora.

Agora, a verdadeira questão é: qual era a probabilidade de ganhar?


Você receberá duas entradas:

  • n. Este é o número de pessoas que participaram do desafio
  • k. Este é o número de pessoas (daquelas n) que têm 2 vidas. Esse número sempre inclui você.

Então, se eu tivesse uma função pe telefonasse p(10, 5), essa seria a probabilidade de ganhar o prêmio onde há 10 pessoas no total, 5 das quais têm apenas 1 vida, enquanto 5 (incluindo você) têm 2 vidas.


Espera-se que você produza a probabilidade de ganhar exatamente ou como um decimal. De qualquer forma, as respostas devem ser até precisos e incluindo a 4 ª casa decimal depois do ponto decimal. Você deve ou não arredondar para esse dígito.

Sua solução pode ser uma solução randomizado que gera a resposta para a 4 ª casa decimal com alta probabilidade . Você pode supor que o RNG incorporado que você usa é verdadeiramente aleatório e deve gerar a resposta correta com pelo menos 90% de probabilidade.

Além disso, seu código precisa apenas funcionar n, k <= 1000, embora eu tenha fornecido casos de teste maiores que os para aqueles curiosos.


Casos de teste

Nota: algumas dessas são fórmulas gerais.

n,    k   |  output
----------+---------
1,    1   |  1
2,    2   |  0.5
2,    1   |  0.75
3,    1   |  11/18 = 0.611111111
1000, 1   |  0.007485470860550352
4,    3   |  0.3052662037037037
k,    k   |  1/k
n,    1   |  (EulerGamma + PolyGamma[1 + n])/n    (* Mathematica code *)
          |  (γ + ψ(1 + n))/n
10,   6   |  0.14424629234373537
300,  100 |  0.007871966408910648
500,  200 |  0.004218184180294532
1000, 500 |  0.0018008560286627948
---------------------------------- Extra (not needed to be a valid answer)
5000, 601 |  0.0009518052922680399
5000, 901 |  0.0007632938197806958

Para mais algumas verificações, faça p(n, 1) * no seguinte:

n     |  output
------+---------
1     | 1
2     | 1.5 
3     | 1.8333333333333335
10    | 2.928968253968254
100   | 5.1873775176396215
-------------------------- Extra (not needed to be a valid answer)
100000| 12.090146129863305
Justin
fonte
Não estou mais familiarizado com as tags deste site; se você pensa em uma tag mais apropriada, edite-a!
Justin
Questão intimamente relacionada no math.se: math.stackexchange.com/q/1669715/72616
Justin
Então, P (n, k) = ((k-1) / n) P (n, k-1) + ((nk) / n) P (n-1, k) + (1 / n) Q ( n, k-1), onde Q (n, k) = ((nk-1) / n) Q (n-1, k) + (k / n) Q (n, k-1) e Q (1 , 0) = 1 ... #
Leaky Nun
@KennyLau Eu não estou indo para tentar interpretá-lo, mas cuidado com o link math.se, uma vez que utiliza uma definição ligeiramente diferente da função (creio que kestá fora por um)
Justin
2
É correto fazer uma simulação aleatória com ensaios suficientes para que a resposta esteja correta até a quarta casa decimal com alta probabilidade, embora, claro, não seja certeza?
Xnor

Respostas:

2

MATL , 42 bytes

:<~QXJx`J`tf1Zry0*1b(-tzq]f1=vts3e8<]6L)Ym

Isso usa uma abordagem probabilística (Monte Carlo). O experimento é realizado um grande número de vezes, a partir do qual a probabilidade é estimada. O número de realizações é selecionado para garantir que o resultado esteja correto até a quarta casa decimal com probabilidade de pelo menos 90%. No entanto, isso leva muito tempo e muita memória. No link abaixo, o número de realizações foi reduzido em um fator de 10 6, para que o programa termine em um período razoável de tempo; e apenas a primeira casa decimal é garantida como precisa com pelo menos 90% de probabilidade.

EDIT (29 de julho de 2016): devido a alterações no idioma, 6Lprecisa ser substituído por 3L. O link abaixo incorpora essa modificação.

Experimente online!

fundo

Vamos p denotar a probabilidade de ser computada. O experimento descrito no desafio vai ser executado por um número n de vezes. Cada vez, você ganha o prêmio (" sucesso ") ou não. Seja N o número de sucessos. A probabilidade desejada pode ser estimada a partir de N e n . Quanto maior n for, mais precisa será a estimativa. A questão principal é como selecionar n para cumprir com a precisão desejada, ou seja, garantir que pelo menos 90% das vezes o erro seja menor que 10 -4 .

Os métodos de Monte Carlo podem ser

  • Tamanho fixo : um valor de n é previamente fixado (e então N é aleatório);
  • Tamanho variável : n é determinado em tempo real pelos resultados da simulação.

Entre a segunda categoria, um método comum usado é fixar N (número desejado de sucessos) e continuar simulando até que esse número seja alcançado . Assim, n é aleatório. Essa técnica, chamada amostragem binomial inversa ou Monte Carlo binomial negativo , tem a vantagem de que a precisão do estimador pode ser limitada. Por esse motivo, será usado aqui.

Especificamente, com Monte Carlo binomial negativo x = ( N −1) / ( n −1) é um estimador imparcial de p ; e a probabilidade de que x se desvie de p em mais de uma dada razão pode ser superior. De acordo com a equação (1) deste artigo (observe também que as condições (2) são satisfeitas), tomar N = 2,75 · 10 8 ou maior garante que p / x pertence ao intervalo [1.0001, 0,9999] com pelo menos 90% probabilidade. Em particular, isso implica que x está correto até a quarta casa decimal com pelo menos 90% de probabilidade, conforme desejado.

Código explicado

O código usa N = 3e8para salvar um byte. Observe que fazer muitas simulações levaria muito tempo. O código no link usa N = 300, que é executado em um período de tempo mais razoável (menos de 1 minuto no compilador online para os primeiros casos de teste); mas isso apenas garante que o primeiro decimal esteja correto com probabilidade de pelo menos 90%.

:        % Take k implicitly. Range [1 ... k]
<~       % Take n implicitly. Determine if each element in the previous array is
         % less than or equal than n
Q        % Add 1. This gives an array [2 ... 2 1 ... 1]
XJx      % Copy to clipboard J. Delete from stack
`        % Do...while. Each iteration is a Monte Carlo realization, until the 
         % desired nunber of successes is reached
  J      %   Push previously computed array [2 ... 2 1 ... 1]
  `      %   Do...while. Each iteration picks one door and decrements it, until
         %   there is only one
    t    %     Duplicate
    f    %     Indices of non-zero elements of array
    1Zr  %     Choose one of them randomly with uniform distribution
    y0*  %     Copy of array with all values set to 0
    1b(  %     Assign 1 to chosen index
    -    %     Subtract
    tzq  %     Duplicate. Number of nonzero elements minus 1. This is falsy if
         %     there was only one nonzero value; in this case the loop is exited
  ]      %   End do...while
  f1=    %   Index of chosen door. True if it was 1 (success), 0 otherwise
  v      %   Concatenate vertically to results from previous realizations
  ts3e8< %   Duplicate. Is the sum less than 3e8? If so, the loop is exited
]        % End do...while
6L)      % Remove last value (which is always 1)
Ym       % Compute mean. This gives (N-1)/(n-1). Implicitly display
Luis Mendo
fonte
Haha Eu não percebi que 90% iria torná-lo tão difícil :-)
Justin
Sim, quarta decimal com 90% de confiança é um requisito muito forte :-)
Luis Mendo
2

Pitão, 34 bytes

Mc|!*HJ-GHch*J+*tHgGtH*gtGHKh-GHKG

Suíte de teste

Define uma função recursiva memorizada determinística, gtomando n , k como argumentos. g 1000 500retorna 0.0018008560286627952em cerca de 18 segundos (não incluído no conjunto de testes acima, pois o tempo excede o intérprete online).

Uma tradução aproximada do Python 3 seria

@memoized
def g(n,k):
    return (not k*(n-k) or (1+(n-k)*((k-1)*g(n,k-1)+g(n-1,k)*(n-k+1)))/(n-k+1))/n
Anders Kaseorg
fonte
1

JavaScript (ES6), 65 bytes

f=(n,k,d=n-k)=>(!d||(f(n-1,k)*++d*--d+1+(--k&&f(n,k)*k*d))/++d)/n

Não tente com os grandes números; até f (30, 10) leva um tempo notável.

Neil
fonte