# XOR of independent Bernoulli variables

In probability theory, a Bernoulli variable is a random variable which has a single parameter $$\p\$$, and is equal to 1 with probability $$\p\$$, and 0 with probability $$\1-p\$$.

In this challenge, there are a bunch of independent Bernoulli variables with parameters $$\p_1, p_2, ... , p_n\$$, and their XOR is calculated. The XOR is 1 if an odd number of variables are 1, and 0 if an even number of variables are 1. Your task is to calculate the probability the XOR is 1.

# Test cases

# Format: [p1, p2, ..., pn] -> probability XOR is 1
[0.123] -> 0.123
[0.123, 0.5] -> 0.5
[0, 0, 1, 1, 0, 1] -> 1
[0, 0, 1, 1, 0, 1, 0.5] -> 0.5
[0.75, 0.75] -> 0.375
[0.75, 0.75, 0.75] -> 0.5625
[0.336, 0.467, 0.016, 0.469] -> 0.499350386816
[0.469, 0.067, 0.675, 0.707] -> 0.4961100146
[0.386, 0.224, 0.507, 0.099, 0.742] -> 0.499658027097344
[0.796, 0.019, 0, 1, 0.217] -> 0.338830368
[0.756, 0.924, 0.001, 0.046, 0.962, 0.001, 0.144] -> 0.6291619858201004


# Rules

• The input list will never be empty, $$\1\leq n\$$.
• You can use any reasonable I/O format. Some particular examples:
• You can choose whether to take $$\p_i\$$ or $$\1-p_i\$$.
• You can choose whether to output $$\p\$$ or $$\1-p\$$.
• You can take the list of probabilities in any reasonable format.
• You can take the length of the list as an additional input.
• You can take the probabilities as fractions instead of floating-point numbers.
• You can assume the probabilities are sorted.
• You can take the probabilities as a multiset, or a map from probability to number of appearances.
• Your algorithm must in theory output exactly the correct answer, assuming its floating point calculations were perfect. In particular, you can't just simulate a finite number of trials.
• Standard loopholes are disallowed.

foldr1$\x p->x+p-2*p*x  Try it online! If you have two events with probabilities x and p, the probability of their xor is p*(1-x)+x*(1-p), or x+p-2*p*x. foldr1 folds this binary operator over the whole list. A different approach that's longer in Haskell but may be golfier in other languages is to take the list product, but conjugated by the mapping y=1-2*x. (\y->(1-y)/2).product.map(\x->1-2*x)  Try it online! Or, since the challenge allowing inputs and outputs of one minus probabilities, we could conjugate by y=2*x-1 instead: (\y->(y+1)/2).product.map(\x->2*x-1)  Try it online! • Based on your profile name, it's almost as if you were born to do this problem! Jun 26 at 19:06 # Python 2, 39 bytes x=0 for p in input():x+=p-x*p*2 print x  Try it online! Also 39 bytes: lambda l:reduce(lambda x,p:x+p-x*p*2,l)  Try it online! Folds (reduces) the binary function (x,p)->x+p-2*p*x like in my Haskell answer. The built-in reduce was removed in Python 3. # Python, 36 bytes f=lambda p=2,*t:p>1or(1-2*p)*f(*t)+p  Try it online! Takes input splatted, and outputs 1 minus the probability. Works for Python 2 or 3. # BQN, 8 6 bytesSBCS Based on xnor's Haskell answer, 2 bytes saved by att and BQN's extensions of logical functions to real numbers. (∨-∧)´  Run online! Spells the XOR out very literally now: ∨ without ∧. • (∨-∧)´ – att Jun 24 at 8:44 • @att I knew ∧ was doing multiplication, but wasn't aware ∨ was extended outside of boolean values as well, thanks! – ovs Jun 24 at 9:10 • The Run online! link seems to be to an earlier version Jun 30 at 5:13 • @CommandMaster thanks, should be fixed now – ovs Jun 30 at 6:42 # R, 27 bytes function(p).5-prod(1-2*p)/2  Try it online! Based on @xnor's Haskell answer. # Jelly, 5 bytes ḤCPCH  A monadic Link that accepts the probabilities as a list of floats in $$\[0,1]\$$ and yields the XOR probability as a float. Try it online! ### How? ḤCPCH - Link: probabilities, P Ḥ - double {P} (vectorises) C - complement (vectorises) e: 1-e P - product C - complement H - halve  # Python NumPy, 28 bytes lambda i:.5-(1-2*i).prod()/2  Attempt This Online! Takes a numpy array. Essentially a port of @xnor's approach (not the one they use but the one they mention in their Haskell answer). ## How? Writing $$\q_j := 1- p_j\$$ compare the products (1) $$\\prod q_j-p_j\$$ and (2) $$\\prod q_j+p_j\$$. (1) can be rewritten (1') $$\\prod 1-2p_j\$$, (2) is just a fancy way of writing $$\1\$$. If we expand the two products (1,2) we get the same terms up to sign. In (2) all the terms are positive, in (1) it depends on whether there is an odd or even number of $$\p_j\$$'s in the term. If we subtract (1) from (2) the terms with an even number of $$\p_j\$$'s cancel and those with an odd number of $$\p_j\$$ occur twice each. We can therefore compute the desired value by taking the product (1') subtracting it from 1 and dividing by 2 Writing this out in symbols is a bit heavy on notation: $$\2\sum_{I\subseteq \{1,...,n\}:|I|\text{ odd}}\prod_{j\in I}p_j\prod_{j\not\in I}q_j \\ =1-\sum_{I\subseteq \{1,...,n\}}\prod_{j\in I}-p_j\prod_{j\not\in I}q_j \\=1 - \prod q_j-p_j =1 - \prod 1-2p_j\$$ • I found some math.se posts for similar problems but they just quote a formula equivalent to this result; can you point me to a derivation of it? – Neil Jun 24 at 11:03 • @Neil I can't, but I've expanded my own derivation, HTH. Jun 24 at 12:09 # Charcoal, 9 7 bytes Ｉ⊘⊕Π⊖⊗Ａ  Try it online! Link is to verbose version of code. Explanation: Port of @xnor's second Haskell answer, but thanks to @xnor, using q for I/O instead of p.  Ａ Input list ⊗ Vectorised doubled ⊖ Vectorised decremented Π Take the product ⊕ Incremented ⊘ Halved Ｉ Cast to string Implicitly print  Previous 9-byte answer that uses p for I/O: Ｉ⊘⁻¹Π⁻¹⊗Ａ  Try it online! Link is to verbose version of code. Explanation: Port of @xnor's second Haskell answer.  ¹ Literal integer 1 ⁻ Subtract ¹ Literal integer 1 ⁻ Vectorised Subtract Ａ Input list ⊗ Vectorised Doubled Π Product ⊘ Halved Ｉ Cast to string Implicitly print  In succinct mode the input is actually implicit which would save me a byte on the above answers but it makes the verbose code look odd. A port of @xnor's Python answer is 16 bytes: ≔⁰ηＦθ≧⁺×ι⁻¹⊗ηηＩη  Try it online! Link is to verbose version of code. Explanation: ≔⁰η  Start with a 0% chance that 0 variables have odd parity (in the computing sense). Ｆθ≧⁺×ι⁻¹⊗ηη  For each variable, update the chances that the total parity is odd. Ｉη  Output the final parity. My original approach was 27 bytes: ⊞υ¹Ｆθ≔⁺×υ⁻¹ι×υιυＩΣΦυ﹪Σ⍘κ²¦²  Try it online! Link is to verbose version of code. Explanation: ⊞υ¹  Start with a 100% chance of 0 variables. Ｆθ≔⁺×υ⁻¹ι×υιυ  For each variable, calculate the chances of that variable being 0 or 1, given the chances of the previous variables. ＩΣΦυ﹪Σ⍘κ²¦²  Sum the chances where the parity (in the computing sense) is odd. • Since the challenge allows I/O with one minus the probabilities, can you replace the outer ¹- with an increment? Or map 2x-1 in fewer bytes than 1-2x? – xnor Jun 25 at 20:17 • Thanks for pointing out the alternative output format of the @xnor of the input variables. I guess there isn't an easy way of describing the alternative input format though? – Neil Jun 27 at 18:37 # Arturo, 24 bytes $=>[0loop&'p->+p-p*2*<=]


Try it!

$=>[ ; a function where input is assigned to & 0 ; push 0 to stack loop&'p-> ; loop over input, assign current element to p <= ; duplicate top of stack 2* ; double p* ; multiply by p p- ; subtract from p + ; add to sum (the 0 we pushed) ] ; end function  # Pyth, 8 bytes .U_-*Zty  Try it online! ### Explanation .U_-*ZtybbQ # implicitly add the bbQ sauce # implicitly assign Q = eval(input()) .U Q # reduce Q on lambda b, Z with no starting value yb # 2*b t # 2*b-1 *Z # Z*(2*b-1) - b # Z*(2*b-1)-b _ # -(Z*(2*b-1)-b) = b-Z*(2*b-1) # = b-Z*2*b+Z # = b+Z-2*b*Z  # C++ (gcc), 53 47 bytes [](auto&v,auto&x){x=0;for(auto p:v)x+=p-x*p*2;}  Try it online! Port of xnor's Python answer Saved 6 bytes thanks to c-- # 05AB1E, 5 bytes ·<P>;  Port of @xnor's third Haskell answer, taking advantage of the $$\1-p\$$ input probabilities. Explanation: · # Double each value in the (implicit) input-list < # Decrease each value by 1 P # Pop and push the product of the list > # Increase it by 1 ; # Halve it # (after which the result is output implicitly as result)  # Thunno 2, 5 bytes Ḍ⁻p⁺½  Attempt This Online! Port of xnor's third Haskell answer. #### Explanation Ḍ⁻p⁺½ # Implicit input Ḍ # Double the input ⁻ # Decrement each p # Take the product ⁺ # Increment it ½ # Halve # Implicit output  • Why reduce when you can cumulatively reduce and output the last item? :P Jun 24 at 13:22 • @noodleman lol we don't have a reduce in Thunno 2 :p Jun 24 at 13:44 • It was a shielded complaint :P (why is reduce-right two bytes???) Jun 24 at 13:45 • @noodleman see this chat message. I didn't think any of the reduces except scanl were important enough for a single-byte command. Jun 24 at 13:46 # Nibbles, 9 bytes (18 nibbles) /$:-+!$_**(!_*~  Nibbles natively supports neither floating-point arithmetic nor fractions, so input is a list of 2-element lists of integers representing the numerator & denominator of each probability expressed as a fraction. We then reduce the list with (in pseudocode): function( [xnum, xden], [pnum, pden] ) = [xnum*pden + pnum*xden - 2*xnum*pnum, xden*pden] and output the final probability as (non-reduced) numerator & denominator. /:-+!$_**(!$_*~ # full program /$:-+!$_**(!_*~ # with implicit arg added; / # fold over input with this function: + # first, get the sum of ! # zipping together$                #       reverse of left element
_               #       and right element
*              #     by multiplication
-                    #   now, subtract from this
*      ~      #     2x
(           #     first element
#     (and remember 2nd element) of
!          #     zipping together
\$         #       left element
_        #       and right element
*       #     by multiplication
:                      #   and join to the rememebered 2nd element # Scala, 30 bytes

Golfed version. Attempt this online!

_.reduceLeft((x,p)=>x+p-2*p*x)


Ungolfed version. Attempt this online!

import scala.io.StdIn.readLine
import scala.util.Try

object Main {
def main(args: Array[String]): Unit = {
.takeWhile(_ != null)
.map(parseDoubles)
.collect { case Some(list) => list }
.map(compute)
.foreach(println)
}

def parseDoubles(input: String): Option[List[Double]] = {
val strippedInput = input.stripPrefix("[").stripSuffix("]")
Try(strippedInput.split(',').map(_.trim.toDouble).toList).toOption
}

def compute(numbers: List[Double]): Double = {
numbers.reduceLeft((x, p) => x + p - 2 * p * x)
}
}


# Julia 1.0, 27 bytes

p>t...=(t.|>i->p+=i-2p*i;p)


Try it online!

29 bytes with recursion Try it online!

28 bytes with reduce Try it online!

# Mathematica (Wolfram Language) 18 bytes

This is an infix example of xnor's idea.

#1+#2-2#1#2&~Fold~


This gives the correct output on all the test cases. I would be interested to know if the arguments could be shortened using some kind of Sequence[].

• You can use # instead of #1 to save 2 bytes. It doesn't save any bytes, but I also personally like using the operator form of Fold to give a self-contained function: Fold[#+#2-2#2#&]. Try it online! Jul 3 at 20:11
• Thanks for the suggestion! Sep 5 at 19:33

# JavaScript (Node.js), 30 bytes

a=>a.map(p=>x+=p-x*p*2,x=0)&&x


Try it online!

Port

# ARM64 machine code, 32 bytes

This function takes as input a pointer to an array of 64-bit doubles in x0, and a pointer to the end of the array (one past last element) in x1. It returns the result in d0. This is consistent with standard calling conventions for a C function declared as double xor_bernoulli(const double *array, const double *end);, to be called like xor_bernoulli(arr, arr+len).

2f00e400
fc408401
1f418002
1f418403
1e632840
eb01001f
54ffff63
d65f03c0


Assembly source:

    .global xor_bernoulli
.text
.balign 4
// x0 = pointer to input
// x1 = pointer to end

// d0 will accumulate the probability
xor_bernoulli:
movi d0, 0  // = 0.0
continue:

// Compute p(1-q) + q(1-p) = (p-pq) + (q-pq)
// let d0 = p
ldr d1, [x0], #8       // d1 = q, x0 += 8
fmsub d2, d0, d1, d0   // d2 = p-pq
fmsub d3, d0, d1, d1   // d3 = q-pq
fadd d0, d2, d3        // d0 = d2 + d3 = (p-pq) + (q-pq)

cmp x0, x1
b.lo continue

ret


The fused multiply-subtract instruction is quite helpful here. It seems a little inefficient that we compute pq twice, thus doing two multiplies where only one is really needed, but I couldn't find a way to avoid it without more instructions.

I thought about trying to use SIMD instructions, but the best I could come up with was the following for the loop body:

continue:
// on entry, v0 = [0, p]
ld1 {v0.d}, [x0], #8          // v0 = [q, p]
ext v1.16b, v0.16b, v0.16b, #8   // v1 = [p, q]
fmls v0.2d, v0.2d, v1.2d         // v0 = [q-qp, p-pq]
faddp d0, v0.2d                  // v0 = [0, q-qp + p-pq]


which is the same length. We can do both multiply-subtracts in parallel with vector fmls, but we need the extra ext shuffle instruction to make a copy with p and q swapped.