Unusual RNG

You have an infinite stream of digits from 0-9, each digit produced uniformly at random. You want to produce a random integer in the following, unusual manner:

First, take the first digit of the stream. Then, for each of the next digits, if it's larger than the last digit you took, ignore it. Otherwise, take it as well. This process ends when you take a 0 (since everything else will be 0). Your number is the sum of all the numbers taken.

For example, consider the following stream: 573493205714390...

  1. First, you take the 5.
  2. The next digit is a 7, so you ignore it.
  3. The next digit is a 3, so you take it. Now the last digit you took is 3.
  4. The next digit is a 4. Despite this being less than 5, you ignore it, since the last digit you took is 3 and 4 is larger than 3.
  5. The next digit is a 9, which is also skipped.
  6. The next digit is a 3. This is taken since you only skip strictly larger numbers.
  7. The next digit is a 2, which is also taken.
  8. The next digit is a 0, which ends the process since you're not going to take any other digit than 0. The resulting number produced by your process is 5+3+3+2=135+3+3+2 = 13.

This problem has two parts, both relating to this generator; you need to solve both of them.

  1. It can be proven that not only the process will end, the expected number you'll get is also finite and a rational number. The expected number you get can be represented as ab\frac{a}{b} with a,ba,b positive integers that are relatively prime.
  2. There exists a smallest integer NN such that 99.99% of the time, the obtained number is strictly smaller than NN ((and the obtained number is smaller than N1N-1 less than 99.99% of the time).).

Find 106a+103b+N10^6 a + 10^3 b + N.


Problem Loading...

Note Loading...

Set Loading...