#Pyth, 11 bytes
WOyG~ZtOT)Z
Note: this program will probably crash with a memory error on any real computer. To test it, try replacing G
with a shorter string, such as in this code, which generates numbers averaging around 28000:
pyth -c 'WOy"abcdefghijklm"~ZtOUT)Z'
This code loops, adding a random number from -1 to 8 to Z
, with a 2^-26 probability of exiting the loop on each repetition. The 2^-26 probability is attained by selecting a random element (O
) of the set of all subsets (y
) of the alphabet (G
).
SinceTechnical details & justification:
The probability 2^-26 is derived from two facts: y
, when called on sequences, is the power-set function, an averageconstructs the list of 3all subsets of the input.5 Since the input, G
, is added26 characters long, this power-set, yG
has 2^26 entries. OyG
selects a random element from those 2^26 entries. Exactly one of those entries, the empty string, will evaluate as falsy when passed to W
, the while loop. Therefore, there is a 2^-26 probability of exiting the loop each time.
In any fixed number of loop cycles K, the probability of getting the number K3.5 + m and getting K3.5 - m are equal, because each sequences of addends that achieves one total can be inverted, -1 -> 8, 0 -> 7, etc., to achieve the other. Additionally, numbers average 2^26 * 3closer to K*3.5 are clearly more likely than numbers farther away. Thus, if K > 2000000/3.5 = 234881024571428.5 the probability of getting a number over 1000000 is greater than 75%, because some of the results above that number can be put into a one-to-one correspondence with all of the results below that number, and the upper less-than-half, can be put into a one-to-one correspondence with those under 1000000. The probability of getting at least 571429 loops is (1-2^-26)^571429, which is no less than (1-2^-26 * 571429), the expected number of times leaving the loop over the first 571429 tries, which is 99.1%. Thus, on 99.1% or more of trials, there is a 75% or more chance of getting at least 1000000, so there is more than a 50% chance of getting over 1000000.
This code relies on a behavior of O
where a bug was accidentally introduced 3 days ago and was fixed today. It should work on any version of Pyth 3 from before Dec 22nd, or after today. The following code is equivalent, and has always worked:
WOyG~ZtOUT)Z