Probabilidad de dibujar una palabra dada de una bolsa de letras en Scrabble

Suponga que tiene una bolsa con fichas, cada una con una letra. Hay mosaicos con la letra 'A', con 'B', etc., y 'comodín' (tenemos ). Suponga que tiene un diccionario con un número finito de palabras.$n$$n_A$$n_B$$n_*$$n = n_A + n_B + \ldots + n_Z + n_*$

Eliges fichas de la bolsa sin reemplazo.$k$

¿Cómo calcularías (o estimarías) la probabilidad de que puedas formar una palabra dada, de longitud (con 1 < = < ) del diccionario dadas las fichas seleccionadas?$l$$l$$k$$k$

Para aquellos que no están familiarizados con Scrabble (TM), el carácter comodín se puede utilizar para que coincida con cualquier letra. Por lo tanto, la palabra 'BOOT' podría ser 'deletreada' con los mosaicos 'B', '*', 'O', 'T'. El orden en que se dibujan las letras no importa.

Sugerencia: para simplificar la escritura de respuestas, podría ser mejor simplemente responder la pregunta: ¿cuál es la probabilidad de tener la palabra 'BOOT' entre sus posibles movimientos después de sacar 7 letras de una bolsa nueva?

(La introducción del problema se ha copiado de esta pregunta similar )

Se solicita una fórmula . Desafortunadamente, la situación es tan complicada que parece que cualquier fórmula será simplemente una forma indirecta de enumerar todas las posibilidades. En cambio, esta respuesta ofrece un algoritmo que es (a) equivalente a una fórmula que involucra sumas de productos de coeficientes binomiales y (b) puede ser portado a muchas plataformas.

---

Para obtener dicha fórmula, divida las posibilidades en grupos mutuamente disjuntos de dos maneras: de acuerdo con la cantidad de letras que no están en la palabra seleccionadas en el estante (deje que esto sea ) y de acuerdo con la cantidad de comodines (espacios en blanco) seleccionados ( deja que esto sea w ). Cuando hay r = 7 mosaicos en el estante, N mosaicos disponibles, M mosaicos disponibles con letras que no están en la palabra y W = 2 espacios en blanco disponibles, el número de opciones posibles dadas por ( m , w ) es$m$$w$$r=7$$N$$M$$W=2$$(m,w)$

$$\binom{M}{m}\binom{W}{w}\binom{N-M-W}{r-m-w}$$

porque las opciones de letras que no son palabras, espacios en blanco y letras de palabras son independientes condicional en$(m,w,r).$

Esto reduce el problema de encontrar la cantidad de formas de deletrear una palabra cuando se selecciona solo de los mosaicos que representan las letras de la palabra, dado que espacios en blanco están disponibles y se mosaicos . La situación es desordenada y no hay una fórmula cerrada disponible. Por ejemplo, con espacios en blanco y letras extrañas se dibujan exactamente cuatro letras restantes para deletrear "boot" que se extrajeron de los mosaicos "b", "o" y "t" . Dado que hay "b" 's, "o"' s, yr - m - w w = 0 m = 3 2 8 $w$$r-m-w$$w=0$$m=3$$2$$8$$6$"t" en el conjunto de mosaicos Scrabble, hay probabilidades positivas de dibujar (bisetos) "bboo", "bbot", "bbtt", "booo", "boot", "bott", "bttt", "oooo "," ooot "," oott "," ottt "y" tttt ", pero solo uno de estos hechizos" boot ". ¡Y ese fue el caso fácil! Por ejemplo, suponiendo que el estante contenga cinco fichas elegidas al azar de las fichas "o", "b" y "t", junto con ambos espacios en blanco, hay muchas más formas de deletrear "arranque" y no deletrearlo. Por ejemplo, "boot" se puede escribir desde "__boott" y "__bbttt", pero no desde "__ttttt".

Este conteo, el corazón del problema, se puede manejar de manera recursiva. Lo describiré con un ejemplo. Supongamos que deseamos contar las formas de deletrear "boot" con un espacio en blanco y cuatro mosaicos más de la colección de mosaicos "b", "o" y "t" (de donde los dos mosaicos restantes muestran letras no en blanco que no están en { "b", "o", "t"}). Considere la primera letra, "b":

1. Se puede dibujar una "b" en formas de los dos mosaicos "b" disponibles. Esto reduce el problema a contar la cantidad de formas de deletrear el sufijo "oot" usando ambos espacios en blanco y solo tres fichas más de la colección de fichas "o" y "t".$\binom{2}{1}$

2. Un espacio en blanco puede designarse como una "b". Esto reduce el problema a contar la cantidad de formas de deletrear "oot" usando el espacio en blanco restante y solo tres mosaicos más de la colección de mosaicos "o" y "t".

En general, los pasos (1) y (2), que son disjuntos y, por lo tanto, contribuyen de manera aditiva a los cálculos de probabilidad, pueden implementarse como un bucle sobre el posible número de espacios en blanco que podrían usarse para la primera letra. El problema reducido se resuelve de forma recursiva. El caso base ocurre cuando queda una letra, hay una cierta cantidad de mosaicos con esa letra disponible, y también puede haber algunos espacios en blanco en el estante. Solo tenemos que asegurarnos de que el número de espacios en blanco en el estante más el número de mosaicos disponibles será suficiente para obtener la cantidad deseada de esa última letra.

Aquí hay un Rcódigo para el paso recursivo. rackgeneralmente es igual a , es un conjunto de recuentos de las letras (como ), es una estructura similar que da el número de mosaicos disponibles con esas letras, y es el número de espacios en blanco que se supone que ocurren en el bastidor.$7$wordc(b=1, o=2, t=1)alphabetwild

f <- function(rack, word, alphabet, wild) {
  if (length(word) == 1) {
    return(ifelse(word > rack+wild, 0, choose(alphabet, rack)))
  }
  n <- word[1]
  if (n <= 0) return(0)
  m <- alphabet[1]
  x <- sapply(max(0, n-wild):min(m, rack), 
              function(i) {
                choose(m, i) * f(rack-i, word[-1], alphabet[-1], wild-max(0, n-i))
              })
  return(sum(x))
}

Una interfaz para esta función especifica los mosaicos estándar de Scrabble, convierte una palabra dada en su estructura de datos de múltiples conjuntos y realiza la suma doble sobre y . Aquí es donde se calculan y multiplican los coeficientes binomiales y .w ($m$$w$($\binom{M}{m}$$\binom{W}{w}$

scrabble <- function(sword, n.wild=2, rack=7, 
              alphabet=c(a=9,b=2,c=2,d=4,e=12,f=2,g=3,h=2,i=9,j=1,k=1,l=4,m=2,
                         n=6,o=8,p=2,q=1,r=6,s=4,t=6,u=4,v=2,w=2,x=1,y=2,z=1),
              N=sum(alphabet)+n.wild) {
  word = sort(table(strsplit(sword, NULL))) # Sorting speeds things a little
  a <- sapply(names(word), function(s) alphabet[s])
  names(a) <- names(word)
  x <- sapply(0:n.wild, function(w) {
    sapply(sum(word):rack-w, 
           function(i) {
             f(i, word, a, wild=w) *
               choose(n.wild, w) * choose(N-n.wild-sum(a), rack-w-i)
           })
  })
  return(list(numerator = sum(x), denominator = choose(N, rack),
              value=sum(x) / choose(N, rack)))
}

---

Probemos esta solución y cronometremos a medida que avanzamos. La siguiente prueba utiliza las mismas entradas empleadas en las simulaciones de @Rasmus Bååth :

system.time(x <- sapply(c("boot", "red", "axe", "zoology"), scrabble))

Esta máquina reporta segundos de tiempo total transcurrido: razonablemente rápido. ¿Los resultados?$0.05$

> x
            boot        red         axe         zoology     
numerator   114327888   1249373480  823897928   11840       
denominator 16007560800 16007560800 16007560800 16007560800 
value       0.007142118 0.07804896  0.0514693   7.396505e-07

La probabilidad de "arranque" de es exactamente igual al valor obtenido en mi otra respuesta (que utiliza un método similar pero lo formula en un marco más potente que requiere una plataforma de computación de álgebra simbólica). Las probabilidades para las cuatro palabras son razonablemente cercanas a las simulaciones de Bååth (que no podría esperarse que proporcione un valor exacto para "zoología" debido a su baja probabilidad de que es menos de uno en un millón).2381831 / 333490850 11840 / 16007560800 $114327888/16007560800$$2381831/333490850$$11840/16007560800,$

Las respuestas a la pregunta a la que se hace referencia se aplican aquí directamente: cree un diccionario que consista solo en la palabra objetivo (y sus posibles deletreos comodín), calcule la posibilidad de que un estante aleatorio no pueda formar el objetivo y reste eso de . Este cálculo es rápido.$1$

Las simulaciones (que se muestran al final) admiten las respuestas calculadas.

---

Detalles

Como en la respuesta anterior, Mathematica se usa para realizar los cálculos.

1. Especifique el problema: la palabra (o palabras, si lo desea), las letras, sus recuentos y el tamaño del estante. Debido a que todas las letras que no están en la palabra actúan de la misma manera, acelera enormemente el cálculo para reemplazarlas por un solo símbolo representa "cualquier letra que no esté en la palabra".$\chi$

   word = {b, o, o, t};
   letters = {b, o, t, \[Chi], \[Psi]};
   tileCounts = {2, 8, 6, 82, 2};
   rack = 7;

2. Cree un diccionario de esta palabra (o palabras) y aumente para incluir todas las posibles ortografías comodín.

   dict[words_, nWild_Integer] := Module[{wildcard, w},
      wildcard = {xx___, _, yy___} -> {xx, \[Psi], yy};
      w = Nest[Flatten[ReplaceList[#, wildcard] & /@ #, 1] &, words, nWild];
      Union[Times @@@ Join[w, Times @@@ words]]];
   dictionary = dict[{word}, 2]

   $\left\{b o^2 t, b o^2 \psi ,b o t \psi ,o^2 t \psi ,b o \psi ^2,o^2 \psi ^2,b t \psi ^2,o t \psi ^2\right\}$

3. Calcule las no palabras:

   alphabet = Plus @@ letters;
   nonwords = Nest[PolynomialMod[# alphabet, dictionary] &, 1, rack]

   $b^7 + 7 b^6 o + 21 b^5 o^2 + \cdots +7 \chi \psi ^6+\psi ^7$

   (Hay no palabras en este caso).$185$

4. Calcule las posibilidades. Para el muestreo con reemplazo, simplemente sustituya los recuentos de mosaico por las variables:

   chances = (Transpose[{letters, tileCounts/(Plus @@ tileCounts)}] /. {a_, b_} -> a -> b);
   q = nonwords /. chances;
   1 - q

   $\frac{207263413}{39062500000}$

   Este valor es aproximadamente$0.00756036.$

   Para el muestreo sin reemplazo, use potencias factoriales en lugar de potencias:

   multiplicities = MapThread[Rule, {letters, tileCounts}];
   chance[m_] :=  (ReplaceRepeated[m , Power[xx_, n_] -> FactorialPower[xx, n]] 
                  /. multiplicities);
   histor = chance /@ MonomialList[nonwords];
   q0 = Plus @@ histor  / FactorialPower[Total[tiles], nn];
   1 - q0

   $\frac{2381831}{333490850}$

   Este valor es aproximadamente Los cálculos fueron prácticamente instantáneos.$0.00714212.$

---

Resultados de la simulación

Resultados de iteraciones con reemplazo:$10^6$

simulation = RandomChoice[tiles -> letters, {10^6, 7}];
u = Tally[Times @@@ simulation];
(p = Total[Cases[Join[{PolynomialMod[u[[All, 1]], dictionary]}\[Transpose], 
       u, 2], {0, _, a_} :> a]] / Length[simulation] ) // N

$0.007438$

Compárelo con el valor calculado en relación con su error estándar:

(p - (1 - q)) / Sqrt[q (1 - q) / Length[simulation]] // N

$-1.41259$

El acuerdo está bien, apoyando firmemente el resultado calculado.

Resultados de iteraciones sin reemplazo:$10^6$

tilesAll = Flatten[MapThread[ConstantArray[#1, #2] &, {letters, tiles}] ]
    (p - (1 - q)) / Sqrt[q (1 - q) / Length[simulation]] // N;
simulation = Table[RandomSample[tilesAll, 7], {i, 1, 10^6}];
u = Tally[Times @@@ simulation];
(p0 = Total[Cases[Join[{PolynomialMod[u[[All, 1]], dictionary]}\[Transpose], 
       u, 2], {0, _, a_} :> a]] / Length[simulation] ) // N

$0.00717$

Haz la comparación:

(p0 - (1 - q0)) / Sqrt[q0 (1 - q0) / Length[simulation]] // N

$0.331106$

El acuerdo en esta simulación fue excelente.

El tiempo total para la simulación fue de segundos.$12$

Entonces, esta es una solución de Monte Carlo , es decir, vamos a simular dibujar los mosaicos un millón de veces y luego vamos a calcular cuántos de estos dibujos simulados resultaron en que podamos formar la palabra dada. He escrito la solución en R, pero puedes usar cualquier otro lenguaje de programación, como Python o Ruby.

Primero voy a describir cómo simular un sorteo. Primero definamos las frecuencias de mosaico.

# The tile frequency used in English Scrabble, using "_" for blank.
tile_freq <- c(2, 9 ,2 ,2 ,4 ,12,2 ,3 ,2 ,9 ,1 ,1 ,4 ,2 ,6 ,8 ,2 ,1 ,6 ,4 ,6 ,4 ,2 ,2 ,1 ,2 ,1)
tile_names <- as.factor(c("_", letters))
tiles <- rep(tile_names, tile_freq)
## [1] _ _ a a a a a a a a a b b c c d d d d e e e e e e
## [26] e e e e e e f f g g g h h i i i i i i i i i j k l
## [51] l l l m m n n n n n n o o o o o o o o p p q r r r
## [76] r r r s s s s t t t t t t u u u u v v w w x y y z
## 27 Levels: _ a b c d e f g h i j k l m n o p q r ... z

Luego codifique la palabra como un vector de recuento de letras.

word <- "boot"
# A vector of the counts of the letters in the word
word_vector <- table( factor(strsplit(word, "")[[1]], levels=tile_names))
## _ a b c d e f g h i j k l m n o p q r s t u v w x y z 
## 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0 0 

Ahora dibuje una muestra de siete mosaicos y codifíquelos de la misma manera que la palabra.

tile_sample <- table(sample(tiles, size=7))
## _ a b c d e f g h i j k l m n o p q r s t u v w x y z 
## 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 

Por fin, calcule qué letras faltan ...

missing <- word_vector - tile_sample
missing <- ifelse(missing < 0, 0, missing)
## _ a b c d e f g h i j k l m n o p q r s t u v w x y z 
## 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 

... y suma el número de letras que faltan y resta el número de espacios en blanco disponibles. Si el resultado es cero o menos, logramos deletrear la palabra.

sum(missing) - tile_sample["blank"] <= 0
## FALSE

En este caso particular, no lo hicimos ... Ahora solo tenemos que repetir esto muchas veces y calcular el porcentaje de sorteos exitosos. Todo esto se realiza mediante la siguiente función R:

word_prob <- function(word, reps = 50000) {
  tile_freq <- c(2, 9 ,2 ,2 ,4 ,12,2 ,3 ,2 ,9 ,1 ,1 ,4 ,2 ,6 ,8 ,2 ,1 ,6 ,4 ,6 ,4 ,2 ,2 ,1 ,2 ,1)
  tile_names <- as.factor(c("_", letters))
  tiles <- rep(tile_names, tile_freq)
  word_vector <- table( factor(strsplit(word, "")[[1]], levels=tile_names))
  successful_draws <- replicate(reps, {
    tile_sample <- table(sample(tiles, size=7))
    missing <- word_vector - tile_sample
    missing <- ifelse(missing < 0, 0, missing)
    sum(missing) - tile_sample["_"] <= 0
  })
  mean(successful_draws)
}

Aquí repsestá el número de sorteos simulados. Ahora podemos probarlo con varias palabras diferentes.

> word_prob("boot")
[1] 0.0072
> word_prob("red")
[1] 0.07716
> word_prob("axe")
[1] 0.05088
> word_prob("zoology")
[1] 2e-05

$$p_0=\frac{\binom{n_b}{1}\binom{n_o}{2}\binom{n_t}{1}\binom{n-4}{3}}{\binom{n}{7}}$$ $p_k$$k$ $$\begin{eqnarray*} p_0&=&\frac{\binom{n_b}{1}\binom{n_o}{2}\binom{n_t}{1}\binom{n-4}{3}}{\binom{n}{7}} \\ p_1&=&p_0 +\frac{\binom{n_*}{1}\binom{n_o}{2}\binom{n_t}{1}\binom{n-4}{3}}{\binom{n}{7}} + \frac{\binom{n_b}{1}\binom{n_o}{1}\binom{n_*}{1}\binom{n_t}{1}\binom{n-4}{3}}{\binom{n}{7}} + \frac{\binom{n_b}{1}\binom{n_o}{2}\binom{n_*}{1}\binom{n-4}{3}}{\binom{n}{7}}\\ &=&p_0 +\frac{\binom{n_*}{1}\binom{n-4}{3}}{\binom{n}{7}}(\binom{n_o}{2}\binom{n_t}{1} + \binom{n_b}{1}\binom{n_o}{1}\binom{n_t}{1} + \binom{n_b}{1}\binom{n_o}{2})\\ p_2&=&p_1 + \frac{\binom{n_*}{2}\binom{n-4}{3}}{\binom{n}{7}}(\binom{n_b}{1}\binom{n_o}{1} + \binom{n_b}{1}\binom{n_t}{1} + \binom{n_o}{2} + \binom{n_o}{1}\binom{n_t}{1})\\ p_3&=&p_2 + \frac{\binom{n_*}{3}\binom{n-4}{3}}{\binom{n}{7}}(\binom{n_b}{1} + \binom{n_o}{1} + \binom{n_t}{1})\\ p_4&=&p_3 + \frac{\binom{n_*}{4}\binom{n-4}{3}}{\binom{n}{7}}\\ p_i&=&p_4, i\ge4 \end{eqnarray*}$$

Meh

$$\frac{\partial \gamma}{\partial c} = b_0x^c ln(x) \sum_{r=0}^{\infty}\frac{(c+y-1)(c+\alpha)_r(c+\beta)_r}{(c+1)_r(c+\gamma)_r}x^r+$$

$$+b_0x^c\sum_{r=0}^{\infty}\frac{(c+\gamma-1)(c+\alpha)_r(c+\beta)_r}{(c+1)_r(c+\gamma)_r}(\frac{1}{c+\gamma-1}+$$

$$+\sum_{k=0}^{r-1}(\frac{1}{c+\alpha+\kappa}+\frac{1}{c+\beta+\kappa}+\frac{1}{c+1+\kappa}-\frac{1}{c+\gamma+\kappa}))x^r$$

$$=b_0x^c\sum_{r=0}^{\infty}\frac{(c+\gamma-1)(c+\alpha)_r(c+\beta)_r}{(c+1)_r(c+\gamma)_r}(ln \ x+\frac{1}{c+\gamma-1}+$$

$$+\sum_{k=0}^{r-1}(\frac{1}{c+\alpha+\kappa}+\frac{1}{c+\beta+\kappa}-\frac{1}{c+1+\kappa}-\frac{1}{c+\gamma+\kappa}))x^r$$

Ha pasado un tiempo desde que vi cómo construí mi proyecto. Y mis matemáticas pueden ser completamente incorrectas a continuación, o correctas. Puedo tenerlo al revés. Sinceramente, lo olvido. ¡PERO! Usando solo una combinación binomial, sin tener en cuenta los mosaicos en blanco que arrojan todo fuera de control. La solución de combinación simple sin comodín.

Yo mismo hice estas preguntas y por eso construí mi propio diccionario de probabilidad de palabras de scrabble . No necesita un diccionario de posibles palabras extraídas, solo las matemáticas detrás de él y las letras disponibles basadas en letras en una bolsa de azulejos. El conjunto de reglas en inglés está abajo. Pasé semanas desarrollando las matemáticas solo para responder esta pregunta para todas las palabras en inglés que se pueden usar en un juego, incluidas las palabras que no se pueden usar en un juego. Todo puede ser incorrecto.

La probabilidad de sacar una palabra dada de una bolsa de letras en Scrabble, requiere cuántas letras están disponibles en la bolsa, para cada letra (AZ) y, si estamos usando el comodín como una adición a las matemáticas. Las fichas en blanco se incluyen en esta matemática, suponiendo 100 fichas, 2 de las cuales están en blanco. Además, la cantidad de fichas disponibles varía según el idioma del juego y las reglas del juego de todo el mundo. El scrabble inglés difiere del scrabble árabe, obviamente. Simplemente modifique las letras disponibles, y las matemáticas deberían hacer el trabajo.

Si alguien encuentra errores, me aseguraré de actualizarlos y resolverlos.

Arranque : La probabilidad de Arranque en un juego de scrabble es 0.000386%, que es una probabilidad de 67 de 173,758 manos como se muestra en la página de palabras para arranque .

Azulejos ingleses

todo es el conjunto de letras en la bolsa. count es la matriz de mosaicos disponibles para esa letra, y point es el valor en puntos de la letra.

// All arranged by letter, number of letters in scrabble game, and point for the letter.
$all = array("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z");
    $count = array("9", "2", "2", "4", "12", "2", "3", "2", "9", "1", "1", "4", "2", "6", "8", "2", "1", "6", "4", "6", "4", "2", "2", "1", "2", "1");
$point = array("1", "3", "3", "2", "1", "4", "2", "4", "1", "8", "5", "1", "3", "1", "1", "3", "10", "1", "1", "1", "1", "4", "4", "8", "4", "10");

Hay 100 fichas en un juego de scrabble en inglés (es decir, la suma de $count). No importa cómo se tomen las fichas, por lo que no es una permutación.

Las matemáticas que utilicé Determine cuántas letras hay en la palabra y qué letras hay en la palabra, cuántas de esas letras están disponibles en la bolsa de fichas (cuente para cada letra, únicas y todas). Coeficiente binomial de cada uno, dividido por el coeficiente binomial de longitud de palabra.

Determinar las combinaciones binomiales disponibles.

let C(n,r) be binomial coefficient: n!/[n!(n-r)!], or 0 if r > n

Para cada letra, cuál es el coeficiente binomial.

Hay 1 "B". Hay 2 disponibles, un 2% de posibilidades de sacar el b.
Hay 2 "O". Hay 8 disponibles, un 8% de posibilidades de tirar de la o.
Hay 1 "T". Hay 6 disponibles, un 6% de posibilidades de tirar de la t.
BOOT es una palabra de 4 letras, tomada de un conjunto de 100 fichas con espacios en blanco, 98 sin ellas.

n = 98. El número de mosaicos sin espacio en blanco en el conjunto de inglés

$B = {2 \choose 1} = \frac{2!}{2!(2-1)!}$
$O = {8 \choose 2} = \frac{8!}{8!(8-2)!}$
$T = {6 \choose 1} = \frac{6!}{6!(6-1)!}$

${B \times O \times T}$$\frac{98!}{98!(98-{\rm length})!}$