Calculate a probability exactly This task is about writing code to compute a probability exactly. 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 its first value. That is A[1] = A[n+1] if indexing from 1.  A now has length n+1. 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.

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 two inner products are 0 and 2.

Now consider the inner product of A[1,...,n] and B and the inner product of A[2,...,n+1] and B.

Your code must output the probability that both inner products are zero.

For n=1 this probability is clearly 1/2.

I don't mind how n is specified in the code but it should be very simple and obvious how to change it.

Languages and libraries

You can use any language and libraries you like. I would like to run your code so please include a full explanation for how to run/compile your code in linux if at all possible.
Mathematica, 159 100 87 86 85 bytes

n=3;1-Mean@Sign[##&amp;@@Norm/@({1,0,0,-1}~t~n.Partition[#,2,1,1])&amp;/@{1,-1}~(t=Tuples)~n]


To change n just change the variable definition at the beginning.

Since it's brute force it's fairly slow, but here are the first eight 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


The last one already took 231 seconds and the runtime is horribly exponential.

Explanation

As I said it's brute force. Essentially, I'm just enumerating all possible A and B, compute the two dot products for every possible pair and then find the fraction of pairs that yielded {0, 0}. Mathematica's combinatorics and linear algebra functions were quite helpful in golfing this:

{1,-1}~(t=Tuples)~n


This generates all n-tuples containing 1 or -1, i.e. all possible A. For n = 3 that is:

{{1, 1, 1}, 
 {1, 1, -1}, 
 {1, -1, 1}, 
 {1, -1, -1}, 
 {-1, 1, 1}, 
 {-1, 1, -1}, 
 {-1, -1, 1}, 
 {-1, -1, -1}}


To compute B we do almost the same:

{1,0,0,-1}~t~n


By repeating 0, we duplicate each tuple for each 0 it contains, thereby making 0 twice as likely as 1 or -1. Again using n = 3 as an example:

{{-1, -1, -1},
 {-1, -1, 0}, {-1, -1, 0},
 {-1, -1, 1},
 {-1, 0, -1}, {-1, 0, -1},
 {-1, 0, 0}, {-1, 0, 0}, {-1, 0, 0}, {-1, 0, 0},
 {-1, 0, 1}, {-1, 0, 1},
 {-1, 1, -1},
 {-1, 1, 0}, {-1, 1, 0},
 {-1, 1, 1},
 {0, -1, -1}, {0, -1, -1},
 {0, -1, 0}, {0, -1, 0}, {0, -1, 0}, {0, -1, 0},
 {0, -1, 1}, {0, -1, 1},
 {0, 0, -1}, {0, 0, -1}, {0, 0, -1}, {0, 0, -1},
 {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0},
 {0, 0, 1}, {0, 0, 1}, {0, 0, 1}, {0, 0, 1},
 {0, 1, -1}, {0, 1, -1},
 {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0},
 {0, 1, 1}, {0, 1, 1},
 {1, -1, -1},
 {1, -1, 0}, {1, -1, 0},
 {1, -1, 1},
 {1, 0, -1}, {1, 0, -1},
 {1, 0, 0}, {1, 0, 0}, {1, 0, 0}, {1, 0, 0},
 {1, 0, 1}, {1, 0, 1},
 {1, 1, -1},
 {1, 1, 0}, {1, 1, 0},
 {1, 1, 1}}


Now, for each possible A, we want the dot product of each of those possible B, both with A[1 .. n] and A[2 .. n+1]. E.g. if our current A is {1, 1, -1}, we want the dot product with both {1, 1, -1} and with {1, -1, 1}. Since all our B are already conveniently the rows of a matrix, we want the two sublists of A as columns of another matrix, so that we can compute a simple dot product between them. But transposing {{1, 1, -1}, {1, -1, 1}} simply gives {{1, 1}, {1, -1}, {-1, 1}} which is just a list of all 2-element cyclic sublists of A. That's what this does:

Partition[#,2,1,1]


So we compute that and take the dot product with our list of B. Since we now get a nested list (since each possible A yields a separate vector), we flatten those with ##&amp;@@.

To find out if a pair {x, y} is {0, 0} we compute Sign[Norm[{x,y}]]  where Norm gives √(x²+y²). This gives 0 or 1.

Finally, since we now just want to know the fractions of 1s in a list of 0s and 1s all we need is the arithmetic mean of the list. However, this yields the probability of both at least one dot product being non-zero, so we subtract it from 1 to get the desired result.