All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 All 10 digits (Posted on 2012-07-06)
Pi takes 33 digits to get all 10 digits.
3.14159265358979323846264338327950
However, e only takes 21 digits.
2.71828182845904523536
Suppose you pick random digits from 0 to 9 with probability 1/10 of each digit. What is the average number of digits required to get all 10 digits?

 See The Solution Submitted by Math Man Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution the hard way and the easy way | Comment 3 of 5 |

The hard way:

The idea here is to calculate the probability that all the digits will have been achieved at a after a given number of digit choices. If the probability is, say, p1 after 20 digits have been chosen and p2 after 21 digits have been chosen, then the probability that it takes exactly 21 chosen digits to complete the set is p2-p1.

This then breaks down into finding the probability, for various n, that by that time all 10 digits will have been chosen at least once at some time. This can be done by the inclusion/exclusion formula. In one of its simpler forms, for just three events, p(a and b and c) = p(a)+p(b)+p(c) - p(a or b) - p(b or c) - p(a or c) + p(a or b or c). You get the idea: the sum of all the individual probabilities minus the probabilities of all the pairs of events plus the probabilities of all the triplets, and continuing in this manner if there are more than three events.  In this case we have ten events: getting each digit at least once.

When these probabilities are found, and then successive ones subtracted to get the probabilities of completion exactly at individual counts, each of those individual probabilities are multiplied by the respective count, and when the products are added together, you get the expected value.

A trial shows that the overall probability comes close enough to 1 when n = 330 to round to 1.000000000000000 to the implied accuracy of those zeros.  The following program implements the calculation. It uses the fact that all the digits have the same probability of being chosen to enable multiplication by a combination of 10 things taken n at a time to take the place of using individual terms in the summations.

DECLARE FUNCTION combi# (n#, r#)
DECLARE FUNCTION fact# (x#)
DECLARE FUNCTION probAnyOf# (trials#, particip#)
DEFDBL A-Z
CLS
exVal = 0
FOR tr = 1 TO 333
tot = 0
FOR n = 1 TO 10
tot = tot - (-1) ^ n * probAnyOf(tr, n) * combi(10, n)
NEXT
IF tr > 9 AND tr < 55 THEN PRINT USING "## #.######"; tr; tot - prev
exVal = exVal + tr * (tot - prev)
prev = tot
NEXT tr
PRINT USING "###.######"; exVal

FUNCTION combi (n, r)
combi = fact(n) / (fact(r) * fact(n - r))
END FUNCTION

FUNCTION fact (x)
f = 1
FOR i = 2 TO x
f = f * i
NEXT
fact = f
END FUNCTION

FUNCTION probAnyOf (trials, particip)
'prob of any of the #of participants out of the 10 given #of trials
' equals 1 minus prob of none
probNone = ((10 - particip) / 10) ^ trials
probAnyOf = 1 - probNone
END FUNCTION

The probabilities of requiring exactly n choices to achieve all the ten digits are shown for n=10 through 54:

` n    p10 0.00036311 0.00163312 0.00419113 0.00808314 0.01304615 0.01863416 0.02436017 0.02978518 0.03457819 0.03852920 0.04153621 0.04358722 0.04473323 0.04506824 0.04470725 0.04377226 0.04238227 0.04064828 0.03867029 0.03653130 0.03430331 0.03204332 0.02979633 0.02759734 0.02547335 0.02344236 0.02151637 0.01970238 0.01800539 0.01642540 0.01496041 0.01360742 0.01236243 0.01121844 0.01017145 0.00921346 0.00834047 0.00754448 0.00682149 0.00616350 0.00556751 0.00502652 0.00453653 0.00409354 0.003692`

The resulting expected value, using all n up to 333, is 29.289683, which would be the answer.

The easy way:

We expect to get one of the digits on just one trial.

After getting that one digit, we need the remaining nine digits. Each trial has 9/10 probability of getting a new digit (other than the first chosen). The expected length of time to get the second digit is 10/9.

Likewise the expected number of selections to achieve the third digit is 10/8.

In all, getting all ten digits would then be expected to take

10/10 + 10/9 + 10/8 + 10/7 + 10/6 + 10/5 + 10/4 + 10/3 + 10/2 + 10/1

which equals 7381/252 = 29.28968253968253968253....

 Posted by Charlie on 2012-07-06 13:22:55

 Search: Search body:
Forums (0)