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

Suponga que tiene una bolsa con $n$ fichas, cada una con una letra. Hay $n_A$ azulejos con la letra 'A', $n_B$ 'B', y así sucesivamente, y $n_*$'comodín' azulejos (tenemos $n = n_A + n_B + \ldots + n_Z + n_*$). Suponga que tiene un diccionario con un número finito de palabras. Eliges $k$ fichas de la bolsa sin reemplazo. ¿Cómo calcularías (o estimarías) la probabilidad de que puedas formar cero palabras del diccionario dadas las $k$ fichas seleccionadas?

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'.

Para dar una idea de la escala del problema, $k$ es pequeño, como 7, $n$ es alrededor de 100, y el diccionario contiene alrededor de 100,000 palabras de tamaño $k$ o menor.

editar: Por 'formar una palabra', me refiero a una palabra de longitud no mayor que $k$ . Por lo tanto, si la palabra [ A ] está en el diccionario, al extraer incluso una sola 'A' de la bolsa, uno ha 'formado una palabra'. El problema de los comodines se simplifica radicalmente si se puede suponer que hay palabras de longitud 1 en el diccionario. Si lo hay, cualquier sorteo de un comodín puede coincidir automáticamente con una longitud de 1 palabra y, por lo tanto, uno puede concentrarse en el caso donde no hay comodines. Por lo tanto, la forma más resbaladiza del problema no tiene palabras de 1 letra en el diccionario.

Además, debo decir explícitamente que el orden en que se extraen las letras de la bolsa es irrelevante. No es necesario dibujar las letras en el orden "correcto" de la palabra.

Este es un comentario (¡largo!) Sobre el buen trabajo que @vqv ha publicado en este hilo. Su objetivo es obtener una respuesta definitiva. Ha hecho el trabajo duro de simplificar el diccionario. Todo lo que queda es explotarlo al máximo. Sus resultados sugieren que una solución de fuerza bruta es factible . Después de todo, incluido un comodín, hay como máximo $27^7 = 10,460,353,203$ palabras que se pueden formar con 7 caracteres, y parece que menos de 1/10000 de ellos, digamos, alrededor de un millón, serán no incluye alguna palabra válida.

El primer paso es aumentar el diccionario mínimo con un carácter comodín, "?". 22 de las letras aparecen en palabras de dos letras (todas menos c, q, v, z). Adjunte un comodín a esas 22 letras y agréguelas al diccionario: {a ?, b ?, d ?, ..., y?} Ahora están dentro. De manera similar, podemos inspeccionar las palabras mínimas de tres letras, causando algunas palabras adicionales para aparecer en el diccionario. Finalmente, agregamos "??" al diccionario Después de eliminar las repeticiones que resultan, contiene 342 palabras mínimas.

Una forma elegante de proceder, una que utiliza una cantidad muy pequeña de codificación, es ver este problema como algebraico . Una palabra, considerada como un conjunto desordenado de letras, es solo un monomio. Por ejemplo, "spats" es el monomio . El diccionario, por lo tanto, es una colección de monomios. Parece que$a p s^2 t$

$$\{a^2, a b, a d, ..., o z \psi, w x \psi, \psi^2\}$$

(donde, para evitar confusiones, he escrito $\psi$ para el carácter comodín).

Un bastidor contiene una palabra válida si y solo si esa palabra divide el bastidor.

Una forma más abstracta, pero extremadamente poderosa, de decir esto es que el diccionario genera un ideal en el anillo polinomial R = Z [ a , b , ... , z , ψ ] y que los bastidores con palabras válidas se convierten en cero en el cociente suena R / I , mientras que los bastidores sin palabras válidas permanecen distintos de cero en el cociente. Si formamos la suma de todos los bastidores en R y la calculamos en este anillo de cociente, entonces el número de bastidores sin palabras es igual al número de monomios distintos en el cociente.$I$$R = \mathbb{Z}[a, b, \ldots, z, \psi]$$R/I$$R$

Además, la suma de todos los bastidores en es fácil de expresar. Sea α = a + b + ⋯ + z + ψ ser la suma de todas las letras del alfabeto. α 7 contiene un monomio para cada rack. (Como una ventaja adicional, sus coeficientes cuentan la cantidad de formas en que se puede formar cada estante, lo que nos permite calcular su probabilidad si lo deseamos).$R$$\alpha = a + b + \cdots + z + \psi$$\alpha^7$

Como un ejemplo simple (para ver cómo funciona esto), suponga que (a) no usamos comodines y (b) todas las letras desde "a" hasta "x" se consideran palabras. Entonces, los únicos bastidores posibles a partir de los cuales no se pueden formar palabras deben consistir enteramente en y's y z's. Calculamos módulo el ideal generado por { a , b , c , ... , x } un paso a la vez, por lo tanto:$\alpha=(a+b+c+\cdots+x+y+z)^7$$\{a,b,c, \ldots, x\}$

$$\eqalign{ \alpha^0 &= 1 \cr \alpha^1 &= a+b+c+\cdots+x+y+z \equiv y+z \mod I \cr \alpha^2 &\equiv (y+z)(a+b+\cdots+y+z) \equiv (y+z)^2 \mod I \cr \cdots &\cr \alpha^7 &\equiv (y+z)^6(a+b+\cdots+y+z) \equiv (y+z)^7 \mod I \text{.} }$$

Podemos leer la posibilidad de obtener un rack que no sea de palabras de la respuesta final, : cada coeficiente cuenta las formas en que se puede dibujar el rack correspondiente. Por ejemplo, hay 21 (de 26 ^ 7 posibles) formas de dibujar 2 y's y 5 z's porque el coeficiente de $y^7 + 7 y^6 z + 21 y^5 z^2 + 35 y^4 z^3 + 35 y^3 z^4 + 21 y^2 z^5 + 7 y z^6 + z^7$$y^2 z^5$ es igual a 21.

De los cálculos elementales, es obvio que esta es la respuesta correcta. El punto es que este procedimiento funciona independientemente del contenido del diccionario.

Observe cómo reducir el módulo de potencia, el ideal en cada etapa, reduce el cálculo: ese es el atajo revelado por este enfoque. (Fin del ejemplo).

Los sistemas de álgebra polinómica implementan estos cálculos . Por ejemplo, aquí está el código de Mathematica :

alphabet =  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 + \[Psi];
dictionary = {a^2, a b, a d, a e, ..., w z \[Psi], \[Psi]^2};
next[pp_] := PolynomialMod[pp alphabet, dictionary];
nonwords = Nest[next, 1, 7];
Length[nonwords]

(El diccionario se puede construir de una manera directa a partir de min.dict de @ vqv; pongo una línea aquí que muestra que es lo suficientemente corto como para especificarlo directamente si lo desea).

La salida, que lleva diez minutos de cálculo, es 577958. ( NB en una versión anterior de este mensaje, cometí un pequeño error al preparar el diccionario y obtuve 577940. He editado el texto para reflejar lo que espero ahora) ¡los resultados correctos!) Un poco menos del millón que esperaba, pero del mismo orden de magnitud.

Para calcular la posibilidad de obtener dicho bastidor, debemos tener en cuenta la cantidad de formas en que se puede dibujar el bastidor. Como vimos en el ejemplo, esto es igual a su coeficiente en . La posibilidad de dibujar algunos de estos bastidores es la suma de todos estos coeficientes, que se encuentran fácilmente al establecer todas las letras iguales a 1:$\alpha^7$

nonwords /. (# -> 1) & /@ (List @@ alphabet)

La respuesta es igual a 1066056120, dando una posibilidad del 10.1914% de dibujar un estante desde el cual no se puede formar una palabra válida (si todas las letras son igualmente probables).

Cuando las probabilidades de las letras varían, simplemente reemplace cada letra con su posibilidad de ser dibujada:

tiles = {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, 2};
chances = tiles / (Plus @@ tiles);
nonwords /. (Transpose[{List @@ alphabet, chances}] /. {a_, b_} -> a -> b)

El resultado es 1.079877553303%, la respuesta exacta (aunque utilizando un modelo aproximado, dibujo con reemplazo). Mirando hacia atrás, se necesitaron cuatro líneas para ingresar los datos (alfabeto, diccionario y frecuencias del alfabeto) y solo tres líneas para hacer el trabajo: describa cómo tomar la próxima potencia del módulo I , tomar la séptima potencia de forma recursiva y sustituirla. probabilidades para las letras.$\alpha$$I$

Es muy difícil dibujar un estante que no contenga ninguna palabra válida en Scrabble y sus variantes. A continuación hay un programa R que escribí para estimar la probabilidad de que el estante inicial de 7 mosaicos no contenga una palabra válida. Utiliza un enfoque de Monte Carlo y el léxico Words With Friends (no pude encontrar el léxico oficial de Scrabble en un formato fácil). Cada prueba consiste en dibujar un estante de 7 fichas y luego verificar si el estante contiene una palabra válida.

Palabras mínimas

No tiene que escanear todo el léxico para verificar si el estante contiene una palabra válida. Solo necesita escanear un léxico mínimo compuesto por palabras mínimas . Una palabra es mínima si no contiene otra palabra como subconjunto. Por ejemplo, 'em' es una palabra mínima; 'vacío' no lo es. El punto de esto es que si un bastidor contiene la palabra x, entonces también debe contener cualquier subconjunto de x . En otras palabras: un estante no contiene palabras si no contiene palabras mínimas. Afortunadamente, la mayoría de las palabras en el léxico no son mínimas, por lo que pueden eliminarse. También puede fusionar palabras equivalentes de permutación. Pude reducir el léxico Words With Friends de 172,820 a 201 palabras mínimas.

Los comodines se pueden manejar fácilmente tratando los bastidores y las palabras como distribuciones sobre las letras. Verificamos si un rack contiene una palabra restando una distribución de la otra. Esto nos da el número de cada letra que falta en el estante. Si la suma de esos números es el número de comodines, entonces la palabra está en el estante.$\leq$

El único problema con el enfoque de Monte Carlo es que el evento que nos interesa es muy raro. Por lo tanto, debería tomar muchas, muchas pruebas obtener una estimación con un error estándar lo suficientemente pequeño. Me encontré con mi programa (pegado en la parte inferior) con ensayos y tengo una probabilidad estimada de 0.004 que el bastidor inicial no contiene una palabra válida . El error estándar estimado de esa estimación es 0.0002. Me llevó solo un par de minutos ejecutar mi Mac Pro, incluida la descarga del léxico.$N=100,000$

Me interesaría ver si alguien puede llegar a un algoritmo exacto eficiente. Un enfoque ingenuo basado en la inclusión-exclusión parece que podría implicar una explosión combinatoria.

Exclusión inclusión

Creo que esta es una mala solución, pero de todos modos aquí hay un boceto incompleto. En principio, puede escribir un programa para hacer el cálculo, pero la especificación sería tortuosa.

La probabilidad que deseamos calcular es El evento dentro de la probabilidad en el lado derecho es una unión de eventos: P ( k -tile rack contiene una palabra ) = P ( ∪ x ∈ M { k -tile rack contiene  x } ) , donde

$$P(k\text{-tile rack does not contain a word}) = 1 - P(k\text{-tile rack contains a word}) .$$ $$P(k\text{-tile rack contains a word}) = P\left(\cup_{x \in M} \{ k\text{-tile rack contains }x \} \right),$$ $M$$\mathcal{P}(M)$$M$$M$ $$\begin{align} &P(k\text{-tile rack contains a word}) \\ &= P\left(\cup_{x \in M} \{ k\text{-tile rack contains }x \} \right) \\ &= \sum_{j=1}^{|M|} (-1)^{j-1} \sum_{S \in \mathcal{P}(M) : |S| = j} P\left( \cap_{x \in S} \{ k\text{-tile rack contains }x \} \right) \end{align}$$

The last thing to specify is how to calculate the probability on the last line above. It involves a multivariate hypergeometric.

$$\cap_{x \in S} \{ k\text{-tile rack contains }x \}$$ is the event that the rack contains every word in $S$. This is a pain to deal with because of wildcards. We'll have to consider, by conditioning, each of the following cases: the rack contains no wildcards, the rack contains 1 wildcard, the rack contains 2 wildcards, ...

Then

$$\begin{align} &P\left( \cap_{x \in S} \{ k\text{-tile rack contains }x \} \right) \\ &= \sum_{w=0}^{n_{*}} P\left( \cap_{x \in S} \{ k\text{-tile rack contains }x \} | k\text{-tile rack contains } w \text{ wildcards} \right) \\ &\quad \times P(k\text{-tile rack contains } w \text{ wildcards}) . \end{align}$$

I'm going to stop here, because the expansions are tortuous to write out and not at all enlightening. It's easier to write a computer program to do it. But by now you should see that the inclusion-exclusion approach is intractable. It involves $2^{|M|}$ terms, each of which is also very complicated. For the lexicon I considered above $2^{|M|} \approx 3.2 \times 10^{60}$.

Scanning all possible racks

I think this is computationally easier, because there are fewer possible racks than possible subsets of minimal words. We successively reduce the set of possible $k$-tile racks until we get the set of racks which contain no words. For Scrabble (or Words With Friends) the number of possible 7-tile racks is in the tens of billions. Counting the number of those that do not contain a possible word should be doable with a few dozen lines of R code. But I think you should be able to do better than just enumerating all possible racks. For instance, 'aa' is a minimal word. That immediately eliminates all racks containing more than one 'a’. You can repeat with other words. Memory shouldn’t be an issue for modern computers. A 7-tile Scrabble rack requires fewer than 7 bytes of storage. At worst we would use a few gigabytes to store all possible racks, but I don’t think that’s a good idea either. Someone may want to think more about this.

Monte Carlo R program

# 
#  scrabble.R
#  
#  Created by Vincent Vu on 2011-01-07.
#  Copyright 2011 Vincent Vu. All rights reserved.
# 

# The Words With Friends lexicon
# http://code.google.com/p/dotnetperls-controls/downloads/detail?name=enable1.txt&can=2&q=
url <- 'http://dotnetperls-controls.googlecode.com/files/enable1.txt'
lexicon <- scan(url, what=character())

# Words With Friends
letters <- c(unlist(strsplit('abcdefghijklmnopqrstuvwxyz', NULL)), '?')
tiles <- c(9, 2, 2, 5, 13, 2, 3, 4, 8, 1, 1, 4, 2, 5, 8, 2, 1, 6, 5, 7, 4, 
           2, 2, 1, 2, 1, 2)
names(tiles) <- letters

# Scrabble
# tiles <- c(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, 2)


# Reduce to permutation equivalent words
sort.letters.in.words <- function(x) {
  sapply(lapply(strsplit(x, NULL), sort), paste, collapse='')
}

min.dict <- unique(sort.letters.in.words(lexicon))
min.dict.length <- nchar(min.dict)

# Find all minimal words of length k by elimination
# This is held constant across iterations:
#   All words in min.dict contain no other words of length k or smaller
k <- 1
while(k < max(min.dict.length))
{
  # List all k-letter words in min.dict
  k.letter.words <- min.dict[min.dict.length == k]

  # Find words in min.dict of length > k that contain a k-letter word
  for(w in k.letter.words)
  {
    # Create a regexp pattern
    makepattern <- function(x) {
      paste('.*', paste(unlist(strsplit(x, NULL)), '.*', sep='', collapse=''), 
            sep='')
    }
    p <- paste('.*', 
               paste(unlist(strsplit(w, NULL)), 
                     '.*', sep='', collapse=''), 
               sep='')

    # Eliminate words of length > k that are not minimal
    eliminate <- grepl(p, min.dict) & min.dict.length > k
    min.dict <- min.dict[!eliminate]
    min.dict.length <- min.dict.length[!eliminate]
  }
  k <- k + 1
}

# Converts a word into a letter distribution
letter.dist <- function(w, l=letters) {
  d <- lapply(strsplit(w, NULL), factor, levels=l)
  names(d) <- w
  d <- lapply(d, table)
  return(d)
}

# Sample N racks of k tiles
N <- 1e5
k <- 7
rack <- replicate(N,
                  paste(sample(names(tiles), size=k, prob=tiles), 
                        collapse=''))

contains.word <- function(rack.dist, lex.dist)
{
  # For each word in the lexicon, subtract the rack distribution from the 
  # letter distribution of the word.  Positive results correspond to the 
  # number of each letter that the rack is missing.
  y <- sweep(lex.dist, 1, rack.dist)

  # If the total number of missing letters is smaller than the number of 
  # wildcards in the rack, then the rack contains that word
  any(colSums(pmax(y,0)) <= rack.dist[names(rack.dist) == '?'])
}

# Convert rack and min.dict into letter distributions
min.dict.dist <- letter.dist(min.dict)
min.dict.dist <- do.call(cbind, min.dict.dist)
rack.dist <- letter.dist(rack, l=letters)

# Determine if each rack contains a valid word
x <- sapply(rack.dist, contains.word, lex.dist=min.dict.dist)

message("Estimate (and SE) of probability of no words based on ", 
        N, " trials:")
message(signif(1-mean(x)), " (", signif(sd(x) / sqrt(N)), ")")

Srikant is right: a Monte Carlo study is the way to go. There are two reasons. First, the answer depends strongly on the structure of the dictionary. Two extremes are (1) the dictionary contains every possible single-letter word. In this case, the chance of not making a word in a draw of $1$ or more letters is zero. (2) The dictionary contains only words formed out of a single letter (e.g., "a", "aa", "aaa", etc.). The chance of not making a word in a draw of $k$ letters is easily determined and obviously is nonzero. Any definite closed-form answer would have to incorporate the entire dictionary structure and would be a truly awful and long formula.

The second reason is that MC indeed is feasible: you just have to do it right. The preceding paragraph provides a clue: don't just generate words at random and look them up; instead, analyze the dictionary first and exploit its structure.

One way represents the words in the dictionary as a tree. The tree is rooted at the empty symbol and branches on each letter all the way down; its leaves are (of course) the words themselves. However, we can also insert all nontrivial permutations of every word into the tree, too (up to $k!-1$ of them for each word). This can be done efficiently because one does not have to store all those permutations; only the edges in the tree need to be added. The leaves remain the same. In fact, this can be simplified further by insisting that the tree be followed in alphabetical order.

In other words, to determine whether a multiset of $k$ characters is in the dictionary, first arrange the elements into sorted order, then look for this sorted "word" in a tree constructed from the sorted representatives of the words in the original dictionary. This will actually be smaller than the original tree because it merges all sets of words that are sort-equivalent, such as {stop, post, pots, opts, spot}. In fact, in an English dictionary this class of words would never be reached anyway because "so" would be found first. Let's see this in action. The sorted multiset is "opst"; the "o" would branch to all words containing only the letters {o, p, ..., z}, the "p" would branch to all words containing only {o, p, ..., z} and at most one "o", and finally the "s" would branch to the leaf "so"! (I have assumed that none of the plausible candidates "o", "op", "po", "ops", or "pos" are in the dictionary.)

A modification is needed to handle wildcards: I'll let the programmer types among you think about that. It won't increase the dictionary size (it should decrease it, in fact); it will slightly slow down the tree traversal, but without changing it in any fundamental way. In any dictionary that contains a single-letter word, like English ("a", "i"), there is no complication: the presence of a wildcard means you can form a word! (This hints that the original question might not be as interesting as it sounds.)

The upshot is that a single dictionary lookup requires (a) sorting a $k$-letter multiset and (b) traversing no more than $k$ edges of a tree. The running time is $O(k \log(k))$. If you cleverly generate random multisets in sorted order (I can think of several efficient ways to do this), the running time reduces to $O(k)$. Multiply this by the number of iterations to get the total running time.

I bet you could conduct this study with a real Scrabble set and a million iterations in a matter of seconds.

Monte Carlo Approach

The quick and dirty approach is to do a monte carlo study. Draw $k$ tiles $m$ times and for each draw of $k$los azulejos ven si puedes formar una palabra. Indique la cantidad de veces que puede formar una palabra$m_w$. La probabilidad deseada sería:

$$1 - \frac{m_w}{m}$$

Acercamiento directo

Deje que el número de palabras en el diccionario sea dado por $S$. Dejar$t_s$ ser el número de formas en que podemos formar el $s^\mbox{th}$palabra. Deje el número de letras que necesita el$s^\mbox{th}$ la palabra se denota por ${m_a, m_b, ..., m_z}$ (es decir, el $s^\mbox{th}$ necesidades de palabras $m_a$número de letras 'a', etc.). Denote la cantidad de palabras que podemos formar con todos los mosaicos por$N$.

$$N = \binom{n}{k}$$

y

$$t_s = \binom{n_a}{m_a} \binom{n_b}{m_b} ... \binom{n_z}{m_z}$$

(Incluir el impacto de los mosaicos comodín es un poco más complicado. Aplazaré ese problema por ahora).

Por lo tanto, la probabilidad deseada es:

$$1 - \frac{\sum_s{t_s}}{N}$$