1
$\begingroup$

Suppose $k$ digits are chosen at random (with replacement) from the set $\{0, 1, 2, \ldots, 9\}$. What is the probability that $0$ will not be chosen?

In several other counting probability problems, one can formulate the answer in terms of permutations and combinations. To illustrate this, the common example I've found is the blue and red marble problem. So given $10$ marbles, $6$ being red, and $4$ being blue, one can say that the probability of picking $2$ blue marbles is $\frac{4 \choose 2}{10 \choose 2}$, or equivalently, we can say it's $\frac{4 \times 3}{10 \times 9}$.

Now the difference between the two problems is that we are considering choices with replacement in the title problem. I was able to solve it using the permutation formulation, namely by saying that out of $10^k$ possible length-k strings, we have $9^k$ possible length-k strings not containing zero, and thus the solution is $(\frac{9}{10})^k$.

Now I am interested in reaching this answer using combinations. First, is that possible? If so, then the only relevant fact that I can think of is that the number of length-$k$ subsets of an $n$-set with replacement is given by ${n+k-1 \choose k}$. However I don't seem to be able to come up with the correct way of formulating the solution using combinations. Any hints?

1 Answers 1

1

Its because you aren't accounting for order. Suppose we take $k=2$. Then it is clear there should be $100$ different sets of $2$ digits you can pick. However, $\dbinom{10+2-1}{2} = 55$, which is not $100$.

The correct way to do this is there are $10^k$ selections from the ten digit set. However, there are only $9^k$ ways to pick from the set once $0$ is removed. Thus the probability is $\frac{9^k}{10^k}$ as desired.

  • 0
    @perfect6 If you insist on doing it without order, that's fine. The quotient probability measure will give the same answer. It just won't have a uniform law anymore. For example, for $k=3$ the unordered $k$-tuple {9,9,9} is obviously much less likely than the unordered $k$-tuple {1,2,3} (there's only one way to pick {9, 9, 9}, but six ways to pick {1, 2, 3}). The problem tells you that the P-measure is the $k$-fold product of the uniform P-measure on 0 through 9, so dinoboy used that directly. You are welcome to pass through the quotient if you like to make your work harder for yourself.2014-11-16