Expected number of lessons to collect the required cards.

Question

Gottfried has been collecting cards in a competition to win 10 free stats lessons. Each lesson you attend, you get a letter card (S, T or A). To win you need to spell the word (STATS). There is 1000 S, T and A to start with so the chance of getting a S, T and A is equal throughout.

What is the theoretical number of lessons needed to win the competition? And how did you get to this answer? Saw a similar question at: Expected time to roll all 1 through 6 on a die

But did not help with this one.

Answer 1

I will write $E(a,b,c)$ to be the expected number of draws to get $a$ of one card, $b$ of another, and $c$ of a third, so that the problem calls for computing $E(1,2,2)$.

We have $$E(1,2,2)= 1 + \frac13E(2,2,0) +\frac23E(1,1,2)\tag{1}$$ because we have to draw a card, and with probability $\frac13$ it is an A so we need $2$ of each of $2$ different cards, and with probability $\frac23$ we draw and S or a T and then we need $1$ of each of $2$ cards and $2$ of another.

Now we continue, expanding the terms on the right-hand side of $(1).$ We have $$E(2,2,0) = 1+\frac13E(2,2,0)+\frac23E(1,2,0)\tag{2}$$ Again, we must draw a card, and with probability $\frac23$ it's one of the cards we need, but with probability $\frac13$ it's the card we don't want and we still need $2$ of each of $2$ cards. So we can rewrite $(2)$ as $$ \frac23E(2,2,0) = 1+\frac23E(1,2,0)\tag{2'}$$

In the same way, we expand the other term on the right-hand side of $(1)$ to get $$ E(1,1,2)=1+\frac23E(1,2,0)+\frac13E(1,1,1)\tag{3}$$

You just have to keep doing this until you get down to terms with known values. It is well-known that the expected number of trials to get a success in repeated Bernoulli trials with probability of success $p$ is ${1\over p},$ so that $E(1,0,0)=3.$ Also, $E(2,0,0)=6,$ because on average we have to draw $3$ card to get the first S, say, and then another $3$ cards to get the second S.

I'm sure you will be able to finish the problem now.

Answer 2

If $9$ is the correct answer then the expected probability of getting two Ss, two Ts and an A in $9$ lessons would be at or very slightly above $0.5$.

$$P(9) = \frac{\text{Number of ways of getting at least 2 Ss, 2 Ts and an A}}{3^9}$$

$$P(9) = \frac{[\frac{9!}{6!2!}\cdot 2 + \frac{9!}{5!3!}\cdot 2 + \frac{9!}{4!4!}]+2[\frac{9!}{6!2!}+\frac{9!}{5!2!2!}\cdot 2 + \frac{9!}{4!3!2!}\cdot 2]}{3^9} = .5441244$$

Answer 3

The answer is $\frac{311}{36}$. Here is some python code to compute it.

import sympy
I = sympy.Integer

def e1(n1, N) :
  return N * n1

def e2(n1, n2, N) :
  if n1 == 0:
    return e1(n2, N)
  if n2 == 0:
    return e1(n1, N)

  e = (I(1)/N * (e2(n1-1, n2, N) + 1) + I(1)/N * (e2(n1, n2-1, N) + 1) + I(N-2)/N) * I(N)/2
  return e

def e(n1,n2,n3) :
  n1,n2,n3 = sorted((n1,n2,n3))
  if n1 == 0 :
    return e2(n2,n3, 3)
  r = 1 + I(1)/3 * (e(n1-1,n2,n3) + e(n1,n2-1,n3) + e(n1,n2,n3-1))
  return r

Here is a more generic version that can handle any number of items:

class memorize(dict):
  def __init__(self, func):
    self.func = func

  def __call__(self, *args):
    return self[args]

  def __missing__(self, key):
    result = self[key] = self.func(*key)
    return result

@memorize
def expected(ns, N) :
  """ Expected number of draws to collect ns[k] items of type k,
      with unifor probability of 1/N for each type.
  expected((2,2,1),3) => 311/36
  """
  assert len(ns) <= N
  if sum(ns) == 0:
    return 0
  ns = sorted(ns)
  while ns[0] == 0 :
    ns = ns[1:]
  n = len(ns)
  if n == 1 :
    return N * ns[0]

  s = 0
  for k in range(n):
    ns[k] -= 1
    s += expected(tuple(ns), N)
    ns[k] += 1
  return (I(N) + s)/n