Qual é a probabilidade de um aluno obter uma nota melhor do que outro em um teste com perguntas selecionadas aleatoriamente?

Suponha que exista um conjunto de perguntas e que haja alunos e .$S$$100$$2$$a$$b$

Vamos ser a probabilidade de que responde à pergunta corretamente, e o mesmo para .$P_{ai}$$a$$i$$P_{bi}$$b$

Todos e são dados para .$P_{ai}$$P_{bi}$$i = 1...100$

Suponha que um exame é feita tomando perguntas aleatórias de .$E$$10$$S$

Como posso encontrar a probabilidade de obter uma pontuação melhor do que ?$a$$b$

Pensei em verificar as combinações e comparar as probabilidades, mas é um número muito grande e levará uma eternidade, então fiquei sem ideias.

Um programa dinâmico fará pouco trabalho com isso.

Suponha que administremos todas as perguntas aos alunos e depois selecionemos aleatoriamente um subconjunto $\mathcal{I}$ do $k=10$ dentre todos $n=100$questões. Vamos definir uma variável aleatória$X_i$ comparar os dois alunos em questão $i:$ configure para $1$ se o aluno A estiver correto e o aluno B não, $-1$ se o aluno B estiver correto e o aluno A não, e $0$de outra forma. O total

é a diferença nas pontuações para as perguntas em $\mathcal I.$ Desejamos calcular $\Pr(X_\mathcal{I} \gt 0).$ Essa probabilidade é assumida sobre a distribuição conjunta de e$\mathcal I$$X_i.$

A função de distribuição de é prontamente calculada$X_i$ sob a suposição de que os alunos respondem independentemente:

Como uma abreviação, vamos chamar essas probabilidades de e respectivamente. Escreva$a_i,$ $b_i,$$d_i,$

Esse polinômio é uma função geradora de probabilidade para o$X_i.$

Considere a função racional

(Na verdade, é um polinômio: é uma função racional bastante simples.) $x^n\psi_n(x,t)$

Quando é expandido como um polinômio em , o coeficiente de consiste na soma de todos os produtos possíveis de distintos Essa será uma função racional com coeficientes diferentes de zero apenas para potências de de aComo é selecionado uniformemente aleatoriamente, os coeficientes desses poderes de quando normalizados para somar à unidade, fornecem a função geradora de probabilidade para a diferença nas pontuações. Os poderes correspondem ao tamanho de$\psi_n$$t$$t^k$$k$$f_i(x).$$x$$x^{-k}$$x^k.$ $\mathcal{I}$$x,$$\mathcal{I}.$

O ponto desta análise é que podemos calcular facilidade e eficiência razoável:$\psi(x,t)$ basta multiplicar os polinômios sequencialmente. Para isso, é necessário reter os coeficientes de em para(é claro que podemos ignorar todos os poderes superiores de que aparecem em qualquer um desses produtos parciais). Assim, todas as informações necessárias transportadas por podem ser representadas por uma matriz , com linhas indexadas pelos poderes de (de a ) e colunas indexadas por$n$$1, t, \ldots, t^k$$\psi_j(x,t)$$j=0, 1, \ldots, n.$$t$$\psi_j(x,t)$$2k+1\times n+1$$x$$-k$$k$$0$ a .$k$

Cada etapa da computação requer um trabalho proporcional ao tamanho dessa matriz, escalando como Contabilizando o número de etapas, esse é um algoritmo de espaço , espaço . Isso torna muito rápido para pequeno Isso foi executado com em (não conhecido para o excesso de velocidade) para a -se a e -se a onde leva nove segundos (em um único núcleo). Na configuração da questão com e o cálculo leva segundos.$O(k^2).$$O(k^2n)$$O(kn)$$k.$R$k$$100$$n$$10^5,$$n=100$$k=10,$$0.03$

Aqui está um exemplo em que são valores aleatórios uniformes entre e e são seus quadrados (que são sempre menores que , favorecendo fortemente o aluno A). Simulei 100.000 exames, como resumido por este histograma das pontuações líquidas:$P_{ai}$$0$$1$$P_{bi}$$P_{ai}$

As barras azuis indicam os resultados nos quais o aluno A obteve uma pontuação melhor que B. Os pontos vermelhos são o resultado do programa dinâmico. Eles concordam lindamente com a simulação ( , ). A soma de todas as probabilidades positivas fornece a resposta neste caso,$\chi^2$$p=51\%$$0.7526\ldots.$

Observe que esse cálculo gera mais do que o solicitado: produz toda a distribuição de probabilidade da diferença de pontuação em todos os exames de ou menos perguntas selecionadas aleatoriamente.$k$

Para aqueles que desejam uma implementação de trabalho para usar ou portar, aqui está o Rcódigo que produziu a simulação (armazenada no vetor Simulation) e executou o programa dinâmico (com resultados na matriz P). O repeatbloqueio no final existe apenas para agregar todos os resultados raros, de modo que o se torne obviamente confiável. (Na maioria das situações, isso não importa, mas evita que o software se queixe.)$\chi^2$

n <- 100
k <- 10
p <- runif(n) # Student A's chances of answering correctly
q <- p^2      # Student B's chances of answering correctly
#
# Compute the full distribution.
#
system.time({
  P <- matrix(0, 2*k+1, k+1) # Indexing from (-k,0) to (k,k)
  rownames(P) <- (-k):k
  colnames(P) <- 0:k
  P[k+1, 1] <- 1
  for (i in 1:n) {
    a <- p[i] * (1 - q[i])
    b <- q[i] * (1 - p[i])
    d <- (1 - a - b)
    P[, 1:k+1] <- P[, 1:k+1] + 
      a * rbind(0, P[-(2*k+1), 1:k]) + 
      b * rbind(P[-1,  1:k], 0) + 
      d * P[,  1:k]
  }
  P <- apply(P, 2, function(x) x / sum(x))
})
#
# Simulation to check.
#
n.sim <- 1e5
set.seed(17)
system.time(
  Simulation <- replicate(n.sim, {
    i <- sample.int(n, k)
    sum(sign((runif(k) <= p[i]) - (runif(k) <= q[i]))) # Difference in scores, A-B
  })
)
#
# Test the calculation.
#
counts <- tabulate(Simulation+k+1, nbins=2*k+1)
n <- sum(counts)
k.min <- 5
repeat {
  probs <- P[, k+1]
  i <- probs * n.sim >= k.min
  z <- sum(probs[!i]) 
  if (z * n >= 5) break
  if (k.min * (2*k+1) >= n) break
  k.min <- ceiling(k.min * 3/2)
}
probs <- c(z, probs[i])
counts <- c(sum(counts[!i]), counts[i])
chisq.test(counts, p=probs)
#
# The answer.
#
sum(P[(1:k) + k+1, k+1]) # Chance that A-B is positive

Em cada iteração,

$P(A>B)=P(A)∗(1−P(B))$

porque A é melhor apenas quando A está certo e B está errado. Portanto, para uma pergunta em particular, se A estiver certo 90% do tempo e B estiver certo 80% do tempo, então a probabilidade conjunta de que A esteja certo e B esteja errado será

$P(A,B) = 0.9 ∗ 0.2 = 0.18$

Agora você pode escrever um código que passe por todas as dez perguntas escolhidas e atribua um ponto a A ou B com base nessa probabilidade conjunta. No final de cada exame, o vencedor é aquele com mais pontos. Faça isso muitas vezes e observe a probabilidade de A conquistar B.

Eu escrevi um código que faz isso aqui: https://nbviewer.jupyter.org/github/kevinmcinerney/exam_probabilities/blob/master/exam_probabilities.ipynb

O gráfico não é renderizado no link, mas tem a seguinte aparência:

Esta simulação usou os valores$P_{ai} = P_{bi} = 0.5$

Neste exemplo, realizei 1000 exames, cada um composto por 25 perguntas, mas todos formam o mesmo conjunto de 100 perguntas. O eixo y é a probabilidade de que A tenha se saído melhor que B em um exame. O número do exame de (0-1000) está no eixo x

Tanto A como B tiveram P aleatório para obter uma pergunta correta, de modo que o gráfico converge em 50%. Eu usei 25 perguntas, porque 10 não é muito representativo da população que contém 100 perguntas. Usando dez perguntas, é mais provável que o gráfico converja para um% próximo ou próximo de 50%. As três linhas são três tentativas separadas.