What is the expected number of different digits in a random 9-digit string, such as a U.S.

[ Editor: the original question asked for the expected number of
  "unique" digits; the posters read this either as different digits
  (1212234 has four: 1, 2, 3, 4) or as digits that appear only once
  (1212234 has two: 3, 4).  Both are answered below. ]

Consider N, the expected number of digits that don't appear.  For a
0-digit number, this is 10, and for a 1 digit number it is 9.  Each time
you add a digit, it will be new with probability N/10, reducing the
number that don't appear by 1, so the expected value N will be reduced
to 9N/10.

Therefore, the expected number of digits that don't appear in a j-digit
number is 10*(0.9)^j.  The expected number that do appear is 10 -
10*(0.9)^j.  For a truly random 9-digit number, this is about 6.13.

-- Jonathan Dushoff <dushoff@gate.sinica.edu.tw>

Also a lesser solution compared to producing a formula, but good for
verification purposes, I went ahead and enumerated the possibilities.

The first column is the number of unique digits, the second is the
number of occurrences.  Then we calculate the expected value.

1        10   0.000000010 * 1 = 0.000000010
2     22950   0.000022950 * 2 = 0.000045900
3   2178000   0.002178000 * 3 = 0.006534000
4  39160800   0.039160800 * 4 = 0.156643200
5 210198240   0.210198240 * 5 = 1.050991200
6 400075200   0.400075200 * 6 = 2.400451200
7 279417600   0.279417600 * 7 = 1.955923200
8  65318400   0.065318400 * 8 = 0.522547200
9   3628800   0.003628800 * 9 = 0.032659200

                     expected = 6.125795110

(the numbers should be exact.  I also ran this
 with more decimals, which were all zeros.)

Source follows.

#include <stdio.h>

double digitcount[ 10 ];

void
more( long digits, long unique, long weight )
{
    if( digits == 8 ){  /* last one goes into tallies */
        digitcount[ unique     ] +=        unique   * weight;
        digitcount[ unique + 1 ] += ( 10 - unique ) * weight;
        return;
    }

    more( digits + 1, unique,            unique   * weight );
    more( digits + 1, unique + 1, ( 10 - unique ) * weight );
}


main()
{
    int i;
    double expct, pct;

    more( 1, 1, 10 );

    for( expct = 0, i = 1; i < 10; i++ ){
        pct = digitcount[ i ] / 1000000000.0;
        printf( "%d %9.0lf   %11.9lf * %d = %11.9lf\n", i,
            digitcount[ i ], pct, i, i * pct );
        expct += i * pct;
    }
    printf( "\n                     expected = %11.9lf\n", expct );

    exit( 0 );
}

-- Michael Will <7nospam7@tampabay.rr.com>

[ Editor: for the singletons (digits appearing exactly once): ]

I would recommend counting the number of N digit numbers that have i
"singletons" and j "voids".  We can do this recursively.  Consider an N
digit number with i singletons and j voids.  What can be said of the
prefix (i.e. the first N-1 digits)?  Well, if the last digit is a
singleton, then the prefix has i-1 singletons and j+1 voids.  If the
last digit is a doubleton, then the prefix has i+1 singletons and j
voids.  Finally, if the last digit is bigger than a doubleton, then
there are i singletons and j voids.  Counting the number of ways in
which all this can happen, we get:

A(N,i,j) = (j+1)A(N-1,i-1,j+1) + (i+1)A(N-1,i+1,j) + (10-i-j)A(N-1,i,j)

Add a few base conditions, like A(1,1,9) = 10 and A(1,i,j) = 0 for all
i<>1 and j<>9 and you should be good to go.

For the social security question, the number of SSNs that have i
singletons is N(i) = A(9,i,0) + A(9,i,1) + ... + A(9,i,9) and the
expected number of digits is E = (N(1) + 2N(2) + ... + 9N(9))/10^9.

Running all this through a hastily-written program, I get an expectation
of 3.874+ singletons.  If my calculations are correct, about a quarter
of the population has three singletons, and another quarter has five.
On the rare side, 0.78% has no singletons, and 0.36% has all singletons.
(This is assuming that the distribution of SSN's is uniform across all
strings of 9 digits, which isn't typically true but is probably becoming
more true now that we're starting to run out.)

-- Matthew Daly <mwdaly@pobox.com>

[ Editor: a simple derivation of both formulae: ]

Choose a digit, say 7.
Then there are 9^9 SSNs which do not contain 7,
and so there are 10^9-9^9 possible SSNs which do contain 7
as one of their different digits.
Since the same argument applies to any other digit,
the total number of different digits is 10 times this,
and the expected number of different digits is
the total number divided by 10^9, i.e. 10(1-.9^9)

For the other interpretation (expected number of singletons),
there are 9x9^8 SSNs containing a singleton 7
(the 7 may appear in any of the 9 positions, and there are
9 ways of filling each of the other 8 positions),
leading to an answer of 10(.9^9)

-- Rob Hutchings <dlaser@ermine.ox.ac.uk>