...or 11 bytes?

Finally, there's an 11 byte version, which is also not limited by the period of the PRNG, but which will run out of memory pretty much every time. It only generates one random number (based on the timestamp) each iteration, and uses it both for incrementing and terminating. The results from each iteration remain on the stack and are only summed up at the end. Thanks to Dennis for this idea:

{esmr(}h]:+

This will run for a very long time, because it uses the current time step (on the order of 10¹²) to determine if the loop should terminate. The upside is, that this solution is not limited by the period of PRNG and should in theory actually be able to produce any number whatsoever.

Below is an equivalent version that uses 3e5 instead of the timestamp. It's much faster and also complies with all the rules. The explanation and mathematical justification refer to this version.

This will run for a very long time, because it uses the current timestamp (on the order of 10¹²) to determine if the loop should terminate. I'm using this as the submission, as it is the shortest, but there are two 14-byte alternatives, which have their own merits:

0{esmr(+esmr}g

This one is not limited by the period of the PRNG, since the range of all random numbers depends on the current timestamp. Therefore, this should be able to produce any number whatsoever, although the probability for negative, or even small positive numbers vanishingly small.

Below is an equivalent version that uses 3e5 instead of the timestamp. And 20 for the first range (as the 13-byte submission). It's much faster and also complies with all the rules. It is sort of the limiting case to get the 50% probability for numbers beyond 1,000,000 while keeping a reasonable runtime and small code-size. The explanation and mathematical justification refer to this version:

CJam, 16 14 bytes

0{Kmr(+3e5mr}g

This usually takes a few seconds to run. You can replace the 5 with a 2 to make it run faster. But then the requirement on the 50% probability will only be met for 1,000 instead of 1,000,000.

I'm starting at 0. Then I've got a loop, which I break out of with probability 1/(3*10⁵). Within that loop I add a random integer between -1 and 18 (inclusive) to my running total. There is a finite (albeit small) probability that each integer will be output, with positive integers being much more likely than negative ones (I don't think you'll see a negative one in your lifetime). Breaking out with such a small probability, and incrementing most of the time (and adding much more than subtracting) ensures that we'll usually go beyond 1,000,000.

0              "Push a 0.";
 {          }g "Do while...";
  Kmr          "Get a random integer in 0..19.";
     (         "Decrement to give -1..18.";
      +        "Add.";
       3e5mr   "Get a random integer in 0..299,999. Aborts if this is 0.";

Some mathematical justification:

• In each step we add 8.5 on average.

• To get to 1,000,000 we need 117,647 of these steps.

• The probability that we'll do less than this number of steps is

    sum(n=0..117,646) (299,999/300,000)^n * 1/300,000
  

  which evaluates to 0.324402. Hence, in about two thirds of the cases, we'll take more 117,647 steps, and easily each 1,000,000.

• (Note that this is not the exact probability, because there will be some fluctuation about those average 8.5, but to get to 50%, we need to go well beyond 117,646 to about 210,000 steps.)

• If in doubt, we can easily blow up the denominator of the termination probability, up to 9e9 without adding any bytes (but years of runtime).

CJam, 16 14 13 bytes

0{Kmr(+esmr}g

This will run for a very long time, because it uses the current time step (on the order of 10¹²) to determine if the loop should terminate. The upside is, that this solution is not limited by the period of PRNG and should in theory actually be able to produce any number whatsoever.

Below is an equivalent version that uses 3e5 instead of the timestamp. It's much faster and also complies with all the rules. The explanation and mathematical justification refer to this version.

0{Kmr(+3e5mr}g

This usually takes a few seconds to run. You can replace the 5 with a 2 to make it run even faster. But then the requirement on the 50% probability will only be met for 1,000 instead of 1,000,000.

I'm starting at 0. Then I've got a loop, which I break out of with probability 1/(3*10⁵). Within that loop I add a random integer between -1 and 18 (inclusive) to my running total. There is a finite (albeit small) probability that each integer will be output, with positive integers being much more likely than negative ones (I don't think you'll see a negative one in your lifetime). Breaking out with such a small probability, and incrementing most of the time (and adding much more than subtracting) ensures that we'll usually go beyond 1,000,000.

0              "Push a 0.";
 {          }g "Do while...";
  Kmr          "Get a random integer in 0..19.";
     (         "Decrement to give -1..18.";
      +        "Add.";
       3e5mr   "Get a random integer in 0..299,999. Aborts if this is 0.";

Some mathematical justification:

• In each step we add 8.5 on average.

• To get to 1,000,000 we need 117,647 of these steps.

• The probability that we'll do less than this number of steps is

    sum(n=0..117,646) (299,999/300,000)^n * 1/300,000
  

  which evaluates to 0.324402. Hence, in about two thirds of the cases, we'll take more 117,647 steps, and easily each 1,000,000.

• (Note that this is not the exact probability, because there will be some fluctuation about those average 8.5, but to get to 50%, we need to go well beyond 117,646 to about 210,000 steps.)

• If in doubt, we can easily blow up the denominator of the termination probability, up to 9e9 without adding any bytes (but years of runtime).