Probabilidade de desenhar uma determinada palavra de um saco de letras no Scrabble

Suponha que você tenha uma sacola com ladrilhos, cada uma com uma letra. Existem blocos com a letra 'A', com 'B' e assim por diante, e 'curinga' (temos ). Suponha que você tenha um dicionário com um número finito de palavras.$n$$n_A$$n_B$$n_*$$n = n_A + n_B + \ldots + n_Z + n_*$

Você escolhe ladrilhos da sacola sem reposição.$k$

Como você calcularia (ou estimaria) a probabilidade de formar uma determinada palavra, de comprimento $l$ (com 1 < $l$ = < $k$ ) do dicionário, considerando os $k$ blocos selecionados?

Para aqueles que não estão familiarizados com o Scrabble (TM), o caractere curinga pode ser usado para corresponder a qualquer letra. Assim, a palavra 'BOOT' pode ser 'soletrada' com os blocos 'B', '*', 'O', 'T'. A ordem na qual as letras são desenhadas não importa.

Sugestão: para simplificar a redação das respostas, talvez seja melhor responder apenas à pergunta: qual é a probabilidade de ter a palavra 'BOOT' entre seus possíveis movimentos depois de desenhar 7 letras de uma sacola nova.

(a introdução do problema foi copiada desta pergunta semelhante )

Uma fórmula é solicitada. Infelizmente, a situação é tão complicada que parece que qualquer fórmula será apenas uma maneira indireta de enumerar todas as possibilidades. Em vez disso, esta resposta oferece um algoritmo que é (a) equivalente a uma fórmula que envolve somas de produtos de coeficientes binomiais e (b) pode ser portado para muitas plataformas.

---

Para obter essa fórmula, divida as possibilidades em grupos separados entre si de duas maneiras: de acordo com quantas letras que não estão na palavra são selecionadas no rack (seja ) e de acordo com quantos curingas (espaços em branco) são selecionados ( que isso seja ). Quando há blocos no rack, blocos disponíveis, blocos disponíveis com letras que não estão na palavra e espaços em branco disponíveis, o número de opções possíveis dadas por éw r = 7 N M W = 2 ( m , w $m$$w$$r=7$$N$$M$$W=2$$(m,w)$

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

porque as opções de letras que não sejam palavras, espaços em branco e letras de palavras são dependentes de$(m,w,r).$

Isso reduz o problema de encontrar o número de maneiras de soletrar uma palavra ao selecionar apenas os blocos que representam as letras da palavra, considerando que espaços em branco estão disponíveis e os mosaicos serão selecionados. A situação é confusa e nenhuma fórmula fechada parece disponível. Por exemplo, com branco e letras fora da palavra, são desenhadas exatamente quatro letras para soletrar "boot" que foram extraídas dos blocos "b", "o" e "t" . Dado que existem "b", "o" er - m - w w = 0 m = 3 2 8 $w$$r-m-w$$w=0$$m=3$$2$$8$$6$"t" está no conjunto de blocos Scrabble, há probabilidades positivas de desenhar (multisets) "bboo", "bbot", "bbtt", "booo", "boot", "bott", "bttt" e "oooo "," ooot "," oott "," ottt "e" tttt ", mas apenas um desses feitiços" boot ". E esse foi o caso fácil! Por exemplo, supondo que o rack contenha cinco peças escolhidas aleatoriamente entre as peças "o", "b" e "t", junto com os dois espaços em branco, existem muitas outras maneiras de soletrar "boot" - e não soletrar. Por exemplo, "boot" pode ser escrito em "__boott" e "__bbttt", mas não em "__ttttt".

Essa contagem - o cerne do problema - pode ser tratada recursivamente. Vou descrevê-lo com um exemplo. Suponha que desejemos contar as maneiras de soletrar "boot" com um espaço em branco e mais quatro peças da coleção de peças "b", "o" e "t" (onde as duas peças restantes mostram letras não em branco que não estão em { "robô"}). Considere a primeira letra, "b":

1. Um "b" pode ser desenhado de nos dois blocos "b" disponíveis. Isso reduz o problema de contar o número de maneiras de escrever o sufixo "oot" usando os dois espaços em branco e apenas mais três peças da coleção de peças "o" e "t".$\binom{2}{1}$

2. Um espaço em branco pode ser designado como "b". Isso reduz o problema de contar o número de maneiras de escrever "oot" usando o espaço em branco restante e apenas mais três peças da coleção de peças "o" e "t".

Em geral, as etapas (1) e (2) - que são disjuntas e, portanto, contribuem de maneira adicional aos cálculos de probabilidade - podem ser implementadas como um loop sobre o número possível de espaços em branco que podem ser usados ​​para a primeira letra. O problema reduzido é resolvido recursivamente. O caso base ocorre quando resta uma letra, existe um certo número de blocos com essa letra disponível e também pode haver alguns espaços em branco no rack. Só precisamos garantir que o número de espaços em branco no rack mais o número de peças disponíveis seja suficiente para obter a quantidade desejada dessa última letra.

Aqui está o Rcódigo para a etapa recursiva. rackgeralmente é igual a , é uma matriz de contagens de letras (como ), é uma estrutura semelhante que fornece os números de blocos disponíveis com essas letras e é o número de espaços em branco que se supõe que ocorrem no rack.$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))
}

Uma interface para essa função especifica os blocos Scrabble padrão, converte uma determinada palavra em sua estrutura de dados de vários conjuntos e executa a soma dupla sobre e . Aqui é onde os coeficientes binomiais e são calculados e multiplicados.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)))
}

---

Vamos experimentar esta solução e cronometrá-la à medida que avançamos. O teste a seguir utiliza as mesmas entradas empregadas nas simulações do @Rasmus Bååth :

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

Esta máquina relata um tempo total decorrido de segundos: razoavelmente rápido. Os 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

A probabilidade de "inicialização" de é exatamente igual ao valor obtido na minha outra resposta (que usa um método semelhante, mas o associa a uma estrutura mais poderosa que requer uma plataforma de computação de álgebra simbólica). As probabilidades para todas as quatro palavras estão razoavelmente próximas das simulações de Bååth (que não se poderia esperar fornecer um valor exato para a "zoologia" devido à baixa probabilidade de que é menor que uma em um milhão).2381831 / 333490850 11840 / 16007560800 $114327888/16007560800$$2381831/333490850$$11840/16007560800,$

As respostas à pergunta referenciada se aplicam aqui diretamente: crie um dicionário que consiste apenas na palavra de destino (e em suas possíveis ortografias curinga), calcule a chance de que um rack aleatório não possa formar o alvo e subtraia-o de . Este cálculo é rápido.$1$

As simulações (mostradas no final) suportam as respostas computadas.

---

Detalhes

Como na resposta anterior, o Mathematica é usado para realizar os cálculos.

1. Especifique o problema: a palavra (ou palavras, se desejar), as letras, suas contagens e o tamanho do rack. Como todas as letras que não estão na palavra agem da mesma forma, isso acelera bastante o cálculo, substituindo-as por um único símbolo representa "qualquer letra que não esteja na palavra".$\chi$

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

2. Crie um dicionário dessa palavra (ou palavras) e aumente-o para incluir todas as ortografias curinga possíveis.

   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 as não palavras:

   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$

   (Existem não-palavras neste caso.)$185$

4. Calcule as chances. Para amostragem com substituição, basta substituir as contagens de blocos pelas variáveis:

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

   $\frac{207263413}{39062500000}$

   Este valor é aproximadamente$0.00756036.$

   Para amostragem sem substituição, use poderes fatoriais em vez de poderes:

   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 é aproximadamente Os cálculos foram praticamente instantâneos.$0.00714212.$

---

Resultados simulados

Resultados de iterações com substituição:$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$

Compare-o com o valor calculado relativo ao seu erro padrão:

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

$-1.41259$

O acordo está bom, apoiando fortemente o resultado computado.

Resultados de iterações sem substituição:$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$

Faça a comparação:

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

$0.331106$

O acordo nesta simulação foi excelente.

O tempo total para a simulação foi de segundos.$12$

Portanto, esta é uma solução de Monte Carlo , ou seja, vamos simular o desenho dos ladrilhos um zilhão de vezes e depois calcularemos quantos desses empates simulados resultaram em poder formar a palavra dada. Eu escrevi a solução em R, mas você pode usar qualquer outra linguagem de programação, como Python ou Ruby.

Primeiro, vou descrever como simular um empate. Primeiro vamos definir as frequências do bloco.

# 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

Em seguida, codifique a palavra como um vetor de contagem 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 

Agora desenhe uma amostra de sete blocos e codifique-os da mesma maneira que a palavra.

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 fim, calcule quais letras estão faltando ...

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 

... e somar o número de letras ausentes e subtrair o número de espaços em branco disponíveis. Se o resultado for zero ou menos, conseguimos escrever a palavra.

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

Nesse caso em particular, não o fizemos ... Agora, basta repetir isso várias vezes e calcular a porcentagem de empates bem-sucedidos. Tudo isso é feito pela seguinte função 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)
}

Aqui repsestá o número de empates simulados. Agora podemos experimentá-lo com várias palavras 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$$ .

It's been a while since I looked at how I built my project. And my math may be entirely incorrect below, or correct. I may have it backwards. Honestly, I forget. BUT! Using only binomial combination, without taking into account blank tiles which throws the entire thing out of whack. The simple combination solution without wild.

I asked these questions myself, and built my own scrabble words probability dictionary because of it. You don't need a dictionary of possible words pulled out, only the math behind it and available letters based on letters in tile bag. The array of English rules is below. I spent weeks developing the math just to answer this question for all English words that can be used in a game, including words that can not be used in a game. It may all be incorrect.

The probability of drawing a given word from a bag of letters in Scrabble, requires how many letters are available in the bag, for each letter ( A-Z ) and, whether we're using the wild card as an addition to the math. The blank tiles are included in this math - assuming 100 tiles, 2 of which are blank. Also, how many tiles are available differs based on language of the game, and game rules from around the world. English scrabble differs from Arabic scrabble, obviously. Just alter the available letters, and the math should do the work.

If anyone finds errors, I will be sure to update and resolve them.

Boot: The probability of Boot in a game of scrabble is 0.000386% which is a chance of 67 out of 173,758 hands as shown on the word page for boot.

English Tiles

all is the array of letters in the bag. count is the array of available tiles for that letter, and point is the point value of the letter.

// 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");

There are 100 tiles in an English scrabble game (i.e., the sum of $count). It does not matter how the tiles are pulled, so it's not a permutation.

The Math I Used Determine how many letters are in the word and what letters are in the word, how many of those letters are available in the tile bag ( count for each letter, unique and allchars ). Binomial coefficient of each, divided by binomial coefficient of length word.

Determine the binomial combinations available

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

Foreach letter, what is the binomial coefficient.

There is 1 "B". There are 2 available, a 2% chance of pulling the b.
There is 2 "O". There are 8 available, a 8% chance of pulling the o.
There is 1 "T". There are 6 available, a 6% chance of pulling the t.
BOOT is a 4 letter word, being taken from a 100 tile set with blanks, 98 without.

n = 98. The number of tiles without blank in the English set

$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}$ divided by the binomial coefficient of tilecount $\frac{98!}{98!(98-{\rm length})!}$