Probabilidad - XOR del subconjunto

Question

Hay 15 números (546,861,69,868,751,562,755,43,989,120,35,947,601,651,935) y tienes que crear un subconjunto de ellos. 0,5,0,5,0,1,0,4,0,6,0,5,0,2,0,1,0,1,0,8,0,8,0,2,0,3,0,5,0,7 son las probabilidades respectivas para incluirlos en el subconjunto.

Encuentra el XOR esperado del subconjunto.

Estoy utilizando este algoritmo para resolver: https://discuss.codechef.com/t/expxor-editorial/25883 ya que las dos preguntas son muy similares, pero no consigo la respuesta correcta.

511,5 es lo que tengo, pero es incorrecto. Edición: Esto resultó ser correcto, el verificador de respuestas tenía un fallo.

Se agradecerá cualquier ayuda.

Answer 1

Si crees que cada uno de los diez bits tiene una probabilidad de aproximadamente $0.5$ de sobrevivir a los XORs entonces la expectativa debe ser de alrededor de $\frac{2^{10}-1}2=511.5$

Si crees que cada uno de los diez bits tiene una probabilidad de exactamente $0.5$ de sobrevivir a los XOR, entonces la expectativa debería ser exactamente $\frac{2^{10}-1}2=511.5$

Cuatro de los valores tienen una probabilidad de $0.5$ de entrar en el $XOR$ cálculo. Escritos en binario son

546   1000100010
861   1101011101
562   1000110010
651   1010001011

y por observación cada uno de los diez bits aparece en al menos uno de ellos.

Así que podemos concluir que $511.5$ es la respuesta correcta. Para confirmarlo, aquí hay un código R que considera todas las $2^{15}$ posibilidades y sus probabilidades asociadas, confirmando $511.5$

values <- c(546,861,69,868,751,562,755,43,989,120,35,947,601,651,935)
probs <- c(0.5,0.5,0.1,0.4,0.6,0.5,0.2,0.1,0.1,0.8,0.8,0.2,0.3,0.5,0.7)
combovalues <- 0
comboprobs <- 1

for (n in 1:length(values)){
  combovalues <- c(combovalues, bitwXor(combovalues, values[n]))
  comboprobs <- c(comboprobs * (1 - probs[n]), comboprobs * probs[n])
  }

sum(combovalues * comboprobs) 
# 511.5

Answer 2

Esta fue una pregunta en el evento de decodificación de código de haywire dude. Soy de mcs y esto es hacer trampa. ¡Gracias por participar!