# CJam, <s>16</s> <s>14</s> 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<sup>12</sup>) 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<sup>5</sup>). 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).