Prawdopodobieństwo narysowania danego słowa z worka liter w Scrabble

Załóżmy, że masz torbę z płytkami, z których każda zawiera literę. Są kafelki z literą „A”, z „B” itd. , „symbole wieloznaczne” (mamy ). Załóżmy, że masz słownik ze skończoną liczbą słów.n A n B n ∗ n = n A + n B + … + n Z + n $n$$n_A$$n_B$$n_*$$n = n_A + n_B + \ldots + n_Z + n_*$

Z torby wybierasz płytek bez wymiany.$k$

Jak obliczysz (lub oszacujesz) prawdopodobieństwo, że możesz utworzyć dane słowo o długości (z 1 < l = < k ) ze słownika, biorąc pod uwagę wybrane k płytek?l $l$$l$$k$$k$

W przypadku osób niezaznajomionych ze Scrabble (TM) można użyć znaku zastępczego, aby dopasować dowolną literę. Zatem słowo „BOOT” może być „ortograficzne” z kafelkami „B”, „*”, „O”, „T”. Kolejność rysowania liter nie ma znaczenia.

Sugestia: aby uprościć pisanie odpowiedzi, lepiej po prostu odpowiedzieć na pytanie: jakie jest prawdopodobieństwo, że słowo „BOOT” będzie wśród twoich możliwych ruchów po wyciągnięciu 7 liter ze świeżej torby.

(wprowadzenie problemu zostało skopiowane z tego podobnego pytania )

Wymagana jest formuła . Niestety sytuacja jest tak skomplikowana, że ​​wydaje się, że każda formuła będzie jedynie okrężnym sposobem wyliczenia wszystkich możliwości. Zamiast tego ta odpowiedź oferuje algorytm, który jest (a) równoznaczny ze wzorem obejmującym sumy iloczynów współczynników dwumianowych i (b) może być przeniesiony na wiele platform.

---

Aby uzyskać taką formułę, podziel możliwości na wzajemnie rozłączne grupy na dwa sposoby: w zależności od liczby liter spoza słowa wybranych w stojaku (niech to będzie ) i według liczby symboli wieloznacznych (pustych) niech to będzie wagowo ). Gdy w stojaku znajduje się r = 7 płytek, N dostępnych płytek, M dostępnych płytek z literami niewymienionymi w słowie, a W = 2 puste pola, liczba możliwych wyborów podana przez ( m , w ) wynosi$m$$w$$r=7$$N$$M$$W=2$$(m,w)$

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

ponieważ wybory liter niebędących słowami, spacji i liter są niezależne od$(m,w,r).$

Zmniejsza to problem ze znalezieniem liczby sposobów przeliterowania słowa przy wybieraniu tylko z kafelków reprezentujących litery słowa, biorąc pod uwagę, że są dostępne puste pola i zostaną płytki . Sytuacja jest chaotyczna i wydaje się, że nie ma zamkniętej formuły. Na przykład, jeśli pustych pól i niesymetryczne litery zostaną narysowane, pozostaną dokładnie cztery litery, które przeliterują „boot”, które zostały narysowane z kafelków „b”, „o” i „t” . Biorąc pod uwagę, że są „b”, „o” ir - m - w w = 0 m = 3 2 8 $w$$r-m-w$$w=0$$m=3$$2$$8$$6$„t” w zestawie kafelków Scrabble, istnieją pozytywne prawdopodobieństwa rysowania (multisetów) „bboo”, „bbot”, „bbtt”, „booo”, „boot”, „bott”, „bttt”, „oooo ”,„ ooot ”,„ oott ”,„ ottt ”i„ tttt ”, ale tylko jedno z tych zaklęć„ boot ”. I to był łatwy przypadek! Na przykład, zakładając, że stojak zawiera pięć losowo wybranych kafelków z płytek „o”, „b” i „t”, wraz z oboma pustymi polami, istnieje wiele innych sposobów na przeliterowanie „rozruchu” - i nie przeliterowanie go. Na przykład „boot” można przeliterować z „__boott” i „__bbttt”, ale nie z „__ttttt”.

Liczenie to - sedno problemu - można rozwiązać rekurencyjnie. Opiszę to na przykładzie. Załóżmy, że chcemy policzyć pisownię „boot” z jednym pustym i czterema dodatkowymi kafelkami z kolekcji płytek „b”, „o” i „t” (skąd pozostałe dwa kafelki pokazują niepuste litery nie w { „b”, „o”, „t”}). Rozważ pierwszą literę „b”:

1. „B” można narysować na z dwóch dostępnych kafelków „b”. Zmniejsza to problem do zliczania liczby sposobów przeliterowania przyrostka „oot” przy użyciu obu pustych pól i tylko trzech kolejnych płytek z kolekcji płytek „o” i „t”.$\binom{2}{1}$

2. Jeden pusty może być oznaczony jako „b”. Zmniejsza to problem do zliczania liczby sposobów pisowni „oot” przy użyciu pozostałego pustego miejsca i tylko trzech kolejnych kafelków z kolekcji płytek „o” i „t”.

Zasadniczo kroki (1) i (2) - które są rozłączne, a zatem przyczyniają się dodatkowo do obliczeń prawdopodobieństwa - mogą zostać zaimplementowane jako pętla nad możliwą liczbą odstępów, które mogą być użyte dla pierwszej litery. Ograniczony problem rozwiązano rekurencyjnie. Podstawowy przypadek występuje, gdy pozostała jedna litera, dostępna jest pewna liczba płytek z tą literą, a także mogą być pewne puste miejsca w stojaku. Musimy tylko upewnić się, że liczba pustych miejsc w stojaku plus liczba dostępnych płytek wystarczą, aby uzyskać pożądaną ilość tej ostatniej litery.

Oto Rkod kroku rekurencyjnego. rackzwykle wynosi , jest tablicą zliczeń liter (np. ), jest podobną strukturą podającą liczbę dostępnych płytek z tymi literami i jest liczbą założonych pustych miejsc w szafie.$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))
}

Interfejs tej funkcji określa standardowe kafelki Scrabble, konwertuje dane słowo na wielosetową strukturę danych i wykonuje podwójną sumę na i w . Oto gdzie współczynniki dwumianowe ($m$$w$ i ($\binom{M}{m}$ są obliczane i mnożone.$\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)))
}

---

Wypróbujmy to rozwiązanie i zmierzmy je do końca. Poniższy test wykorzystuje te same dane wejściowe wykorzystane w symulacjach @Rasmus Bååth :

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

To urządzenie podaje całkowity czas, który upłynął sekundy: dość szybko. Wyniki?$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

Prawdopodobieństwo dla „bagażnik” z dokładnie równa wartości 2381831 / +333.490.850 uzyskanego w innym moją odpowiedź (który używa podobnej metody, ale kanapy go w mocniejszy ramach wymagającego symboliczną platformę algebra obliczeniowej). Prawdopodobieństwa dla wszystkich czterech słów są dość blisko do symulacji Baas (który nie mógł się spodziewać, aby dać dokładną wartość „zoologia” ze względu na jego niskie prawdopodobieństwo 11840 / 16007560800 , który jest mniej niż jedna na milion).$114327888/16007560800$$2381831/333490850$$11840/16007560800,$

Odpowiedzi na przytoczone pytanie mają tutaj zastosowanie bezpośrednio: utwórz słownik składający się tylko ze słowa docelowego (i jego możliwych pisowni symboli wieloznacznych), oblicz szansę, że losowy stojak nie może utworzyć celu i odejmij go od . To obliczenie jest szybkie.$1$

Symulacje (pokazane na końcu) obsługują obliczone odpowiedzi.

---

Detale

Podobnie jak w poprzedniej odpowiedzi, Mathematica służy do wykonywania obliczeń.

1. Określ problem: słowo (lub słowa, jeśli chcesz), litery, ich liczbę i rozmiar szafy. Ponieważ nie wszystkie litery w słowie działać tak samo, to znacznie przyspiesza obliczenia zastąpić je wszystkie za pomocą pojedynczego symbolu reprezentujący „żadnego listu nie w słowie”.$\chi$

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

2. Utwórz słownik tego słowa (lub słów) i rozszerz go, aby zawierał wszystkie możliwe pisowni symboli wieloznacznych.

   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. Oblicz słowa niezwiązane:

   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$

   (W tym przypadku jest nie-słów.)$185$

4. Oblicz szanse. Aby pobrać próbkę z zamiennikiem, wystarczy zastąpić liczbę płytek zmiennymi:

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

   $\frac{207263413}{39062500000}$

   Ta wartość wynosi około $0.00756036.$

   Do pobierania próbek bez zamiany użyj mocy silnych zamiast mocy:

   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}$

   Ta wartość wynosi około Obliczenia były praktycznie natychmiastowe.$0.00714212.$

---

Wyniki symulacji

$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$

Porównaj go z obliczoną wartością w stosunku do jego błędu standardowego:

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

$-1.41259$

Umowa jest w porządku, zdecydowanie popierając obliczony wynik.

$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$

Dokonaj porównania:

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

$0.331106$

Zgodność w tej symulacji była doskonała.

$12$

To jest rozwiązanie Monte Carlo , to znaczy, będziemy symulować rysowanie kafelków zillion razy, a następnie obliczymy, ile z tych symulowanych losowań spowodowało, że jesteśmy w stanie uformować dane słowo. Napisałem rozwiązanie w języku R, ale możesz użyć dowolnego innego języka programowania, na przykład Python lub Ruby.

Najpierw opiszę, jak symulować jedno losowanie. Najpierw zdefiniujmy częstotliwości kafelków.

# 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

Następnie zakoduj słowo jako wektor liczenia liter.

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 

Teraz narysuj próbkę siedmiu płytek i zakoduj je w taki sam sposób, jak słowo.

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 

Na koniec obliczyć, jakich liter brakuje ...

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 

... i zsumuj liczbę brakujących liter i odejmij liczbę dostępnych spacji. Jeśli wynik wynosi zero lub mniej, udało nam się przeliterować słowo.

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

W tym konkretnym przypadku nie zrobiliśmy tego ... Teraz musimy tylko powtórzyć to wiele razy i obliczyć odsetek udanych losowań. Wszystko to odbywa się za pomocą następującej funkcji 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)
}

Oto repsliczba symulowanych losowań. Teraz możemy wypróbować to na kilku różnych słowach.

> 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}}$$ With wildcards, it becomes more tedious. Let $p_k$ indicate the probability of being able to play "BOOT" with $k$ wildcards: $$\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})!}$