XOR of independent Bernoulli variables

Question

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.

Answer 1

Haskell, 23 bytes

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!

Answer 2

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.

Answer 3

BQN, 8 6 bytes^SBCS

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 ∧.

Answer 4

R, 27 bytes

function(p).5-prod(1-2*p)/2

Try it online!

Based on @xnor's Haskell answer.

Answer 5

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

Answer 6

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\$

Answer 7

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.

Answer 8

Arturo, 24 bytes

$=>[0loop&'p->+p-p*2*<=]

Try it!

Port of xnor's Python answer.

$=>[           ; 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

Answer 9

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

Answer 10

C++ (gcc), ⁵³ 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--

Answer 11

05AB1E, 5 bytes

·<P>;

Port of @xnor's third Haskell answer, taking advantage of the \$1-p\$ input probabilities.

Try it online or verify all test cases.

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)

Answer 12

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

Answer 13

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

Answer 14

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 = {
    Iterator.continually(readLine)
      .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)
  }
}

Answer 15

Julia 1.0, 27 bytes

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

Try it online!

Based on xnor's answer

29 bytes with recursion Try it online!

28 bytes with reduce Try it online!

Answer 16

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[].

Answer 17

JavaScript (Node.js), 30 bytes

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

Try it online!

Port

Answer 18

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}[1], [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.