[seqfan] Re: Digit scanning question

[israel at math.ubc.ca]

I assume this is in base 10. This is an approximate calculation: I expect 
the correct answer to be very complicated.

There are 10^n n-digit strings. If after scanning x (>= n) digits you have 
seen k different n-digit substrings, each additional digit scans completes 
a new n-digit substring with probability approximately 1 - k/10^n. Thus the 
expected number of digits to scan to go from k to k+1 substrings is 
approximately 1/(1 - k/10^n). The total expected number of digits to scan 
is then approximately sum_{k=0}^{10^n-1} 1/(1 - k/10^n) = sum_{j=1}^{10^n} 
10^n/j ~ 10^n log(10^n)

Cheers,
Robert

On Oct 20 2015, Giovanni Resta wrote:

>On 10/20/2015 10:16 AM, Christian Lawson-Perfect wrote:
>> Some quick computation suggests it's proportional to log(n).
>
>I think it is something around 10^n*log(10^n).
>
>Giovanni
>
>
>Mon, 19 Oct 2015 at 22:59 David Wilson <davidwwilson at comcast.net> wrote:
>
>>> Over all infinite strings of digits, what is the expected number of 
>>> digits you must scan before seeing every n-digit substring?
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>>
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/
>
>