I previously asked a question for how to compute a probability quickly and accurately. However, evidently it was too easy as a closed form solution was given! Here is a more difficult version.
This task is about writing code to compute a probability exactly and quickly. The output should be a precise probability written as a fraction in its most reduced form. That is it should never output 4/8
but rather 1/2
.
For some positive integer n
, consider a uniformly random string of 1s and -1s of length n
and call it A. Now concatenate to A
a copy of itself. That is A[1] = A[n+1]
if indexing from 1, A[2] = A[n+2]
and so on. A
now has length 2n
. Now also consider a second random string of length n
whose first n
values are -1, 0, or 1 with probability 1/4,1/2, 1/4 each and call it B.
Now consider the inner product of B
with A[1+j,...,n+j]
for different j =0,1,2,...
.
For example, consider n=3
. Possible values for A
and B
could be A = [-1,1,1,-1,...]
and B=[0,1,-1]
. In this case the first two inner products are 0
and 2
.
Task
For each j
, starting with j=1
, your code should output the probability that all the first j+1
inner products are zero for every n=j,...,50
.
Copying the table produced by Martin Büttner for j=1
we have the following sample results.
n P(n)
1 1/2
2 3/8
3 7/32
4 89/512
5 269/2048
6 903/8192
7 3035/32768
8 169801/2097152
Score
Your score is the largest j
your code completes in 1 minute on my computer. To clarify a little, each j
gets one minute. Note that the dynamic programming code in the previous linked question will do this easily for j=1
.
Tie breaker
If two entries get the same j
score then the winning entry will be the one that gets to the highest n
in one minute on my machine for that j
. If the two best entries are equal on this criterion too then the winner will be the answer submitted first.
Languages and libraries
You can use any freely available language and libraries you like. I must be able to run your code so please include a full explanation for how to run/compile your code in linux if at all possible.
My Machine The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor. This also means I need to be able to run your code.
Winning entries
j=2
in Python by Mitch Schwartz.j=2
in Python by feersum. Currently the fastest entry.