17
\$\begingroup\$

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

18 Answers 18

16
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ Based on your profile name, it's almost as if you were born to do this problem! \$\endgroup\$
    – dirvine
    Jun 26, 2023 at 19:06
9
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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 .

\$\endgroup\$
4
  • 6
    \$\begingroup\$ (∨-∧)´ \$\endgroup\$
    – att
    Jun 24, 2023 at 8:44
  • \$\begingroup\$ @att I knew was doing multiplication, but wasn't aware was extended outside of boolean values as well, thanks! \$\endgroup\$
    – ovs
    Jun 24, 2023 at 9:10
  • \$\begingroup\$ The Run online! link seems to be to an earlier version \$\endgroup\$ Jun 30, 2023 at 5:13
  • \$\begingroup\$ @CommandMaster thanks, should be fixed now \$\endgroup\$
    – ovs
    Jun 30, 2023 at 6:42
5
\$\begingroup\$

R, 27 bytes

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

Try it online!

Based on @xnor's Haskell answer.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ 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? \$\endgroup\$
    – Neil
    Jun 24, 2023 at 11:03
  • 1
    \$\begingroup\$ @Neil I can't, but I've expanded my own derivation, HTH. \$\endgroup\$ Jun 24, 2023 at 12:09
3
\$\begingroup\$

Charcoal, 9 7 bytes

I⊘⊕Π⊖⊗A

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.

      A Input list
     ⊗  Vectorised doubled
    ⊖   Vectorised decremented
   Π    Take the product
  ⊕     Incremented
 ⊘      Halved
I       Cast to string
        Implicitly print

Previous 9-byte answer that uses p for I/O:

I⊘⁻¹Π⁻¹⊗A

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
        A   Input list
       ⊗    Vectorised Doubled
    Π       Product
 ⊘          Halved
I           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:

≔⁰ηFθ≧⁺×ι⁻¹⊗ηηIη

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

Fθ≧⁺×ι⁻¹⊗ηη

For each variable, update the chances that the total parity is odd.

Iη

Output the final parity.

My original approach was 27 bytes:

⊞υ¹Fθ≔⁺×υ⁻¹ι×υιυIΣΦυ﹪Σ⍘겦²

Try it online! Link is to verbose version of code. Explanation:

⊞υ¹

Start with a 100% chance of 0 variables.

Fθ≔⁺×υ⁻¹ι×υιυ

For each variable, calculate the chances of that variable being 0 or 1, given the chances of the previous variables.

IΣΦυ﹪Σ⍘겦²

Sum the chances where the parity (in the computing sense) is odd.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – xnor
    Jun 25, 2023 at 20:17
  • \$\begingroup\$ 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? \$\endgroup\$
    – Neil
    Jun 27, 2023 at 18:37
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
0
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Why reduce when you can cumulatively reduce and output the last item? :P \$\endgroup\$
    – noodle man
    Jun 24, 2023 at 13:22
  • \$\begingroup\$ @noodleman lol we don't have a reduce in Thunno 2 :p \$\endgroup\$
    – The Thonnu
    Jun 24, 2023 at 13:44
  • \$\begingroup\$ It was a shielded complaint :P (why is reduce-right two bytes???) \$\endgroup\$
    – noodle man
    Jun 24, 2023 at 13:45
  • \$\begingroup\$ @noodleman see this chat message. I didn't think any of the reduces except scanl were important enough for a single-byte command. \$\endgroup\$
    – The Thonnu
    Jun 24, 2023 at 13:46
1
\$\begingroup\$

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

enter image description here

\$\endgroup\$
1
\$\begingroup\$

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)
  }
}
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ 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! \$\endgroup\$
    – DanTheMan
    Jul 3, 2023 at 20:11
  • \$\begingroup\$ Thanks for the suggestion! \$\endgroup\$
    – dirvine
    Sep 5, 2023 at 19:33
0
\$\begingroup\$

JavaScript (Node.js), 30 bytes

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

Try it online!

Port

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.