3
\$\begingroup\$

Problem

Starting with a set of 10 coins at the start where all coins are tails up, and given n number of integers \$x_1, x_2, x_3... x_n\$ representing n rounds of coin flipping.

At each round, we randomly flip \$x_i\$ number of coins at random. i.e Coins that were heads become tails, and vice versa. Within each round, every coin can be flipped at most once, i.e no repeats.

Objective Write the shortest function that takes as input a list of integers, and calculates the expected number of heads at the end of all rounds.

Assume that the inputs will always correct, i.e every element is between 0 to 10.

Example 1:

# 3 coins chosen at random were flipped over one round, hence E(Heads) = 3
Input = [3]
Output = 3

Example 2:

# 5 coins chosen at random were flipped in the first round
# At the second round, only 1 was random flipped with 50% chance of 
# picking a head/tail. E(Heads) = 0.5*6 + 0.5*4

# Hence E(Heads) = 5
Input = [5, 1]
Output = 5
\$\endgroup\$
4
  • 1
    \$\begingroup\$ By "We randomly flip x_i number of coins in sequence in each of the n rounds", do you mean that a random x_i-size-subset of the 10 coins (so a coin can't be flipped more than once in the same round), and they are each flipped once? Or do you mean that x_i times, a coin is chosen and flipped (so a coin might be flipped more than once in the same round)? \$\endgroup\$
    – pxeger
    Sep 12, 2021 at 5:57
  • \$\begingroup\$ That is a good catch. Coins are flipped without repeats within each round. Will refine the question to reflect this. \$\endgroup\$
    – gamerx
    Sep 12, 2021 at 7:03
  • \$\begingroup\$ This seems clear now so I've reopened this. Nice challenge, thanks for sticking with it. (btw if you want to reply to someone you can use @<their name> at the beginning so they will be notified) \$\endgroup\$
    – Wheat Wizard
    Sep 12, 2021 at 14:18
  • \$\begingroup\$ @WheatWizard thanks for the inputs as well. \$\endgroup\$
    – gamerx
    Sep 12, 2021 at 14:34

7 Answers 7

4
\$\begingroup\$

Python 2, 40 bytes

r=0
for c in input():r+=c-r*c/5.
print r

Try it online!

Let \$Z_i, 1 \le i \le 10 \$ be random variables indicating the state of the \$i\$-th coin after all flips, \$1\$ for heads and \$0\$ for tails. The number we are interested in is:

$$ E \left[ \sum_{i=1}^{10} Z_i \right] = \sum_{i=1}^{10} E \left[ Z_i \right] = 10 E\left[ Z_1 \right] $$

(We can do these two equalities because the expected value is linear and all \$Z_i\$ are identically distributed)

This means it is enough to compute the expected value for a single coin, which leads to the following program, where the formula can be simplified to the above:

r=0.0
for c in input():r=r*(10-c)/10+(1-r)*c/10
print r*10

Try it online!

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 10 bytes

Uses a formula I got by plugging sympy into my Python solution.

5(/æ¦PO5(*

Try it online!

$$ \sum_{A \subseteq X, A \ne \emptyset} (-5)^{1-\left| A \right|} \prod_{a\in A} a = -5 \sum_{A \subseteq X, A \ne \emptyset} \prod_{a\in A} {a \over -5} $$

where \$X\$ is the multiset \$\left\{ x_1, x_2, \cdots, x_n\right\}\$.

5(/         # divide each value by -5
   æ¦       # get all non-empty subsets
     P      # take the product of each subset
      O     # sum all values
       5(*  # multiply result by -5

A direct port of the Python answer is the same length:

Îv1y5/-*y+

Try it online!

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

JavaScript (V8), 29 bytes

x=>x.reduce((a,b)=>a+b-a*b/5)

Try it online!

Based on ovs's answer.

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

Vyxal, 10 bytes

λ₌+*5/-;dR

Try it Online!

port of 05AB1E answer’s formula

and also, wholesomely rekted by lyxal with 5 bytes saved

\$\endgroup\$
5
  • \$\begingroup\$ 13 bytes \$\endgroup\$
    – lyxal
    Sep 13, 2021 at 1:55
  • \$\begingroup\$ 11 bytes \$\endgroup\$
    – lyxal
    Sep 13, 2021 at 1:56
  • \$\begingroup\$ 10 bytes \$\endgroup\$
    – lyxal
    Sep 13, 2021 at 2:00
  • \$\begingroup\$ 9 bytes \$\endgroup\$
    – lyxal
    Sep 13, 2021 at 2:04
  • \$\begingroup\$ (the 9 bytes is a port of Jelly) \$\endgroup\$
    – lyxal
    Sep 13, 2021 at 2:13
1
\$\begingroup\$

Jelly, 7 bytes

÷5CPC×5

Try it online!

$$ 5\times(1-\prod_{i=1}^n 1-{x_i \over 5}) $$

Read this from right to left to get the Jelly code. The formula is derived from the same sympy output as the 05AB1E answer. This has a nice symmetry to it as C×5 is the inverse of ÷5C.


Jelly, 8 bytes

Port of my Python answer

+_×÷5ɗɗ/

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ It would be nice to see some proper reasoning why this works, instead of "this implements the correct formula". Maybe I'll find some time to think about this later. \$\endgroup\$
    – ovs
    Sep 14, 2021 at 8:19
0
\$\begingroup\$

MathGolf, 9 bytes

0ë{‼+*5/-

Port of @Yousername's JavaScript answer, which is based on @ovs' answers.

Try it online.

Explanation:

0         # Start with 0
 ë        # Push the input-integers as float-array
  {       # Foreach over these floats:
   ‼      #  Apply the following two commands separated to the stack:
    +     #   Sum the top two values
    *     #   Multiply the top two values
     5/   #  Divide the product by 5
       -  #  And then subtract it from the sum
          # (after the loop, the entire stack is output implicitly as result)
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 16 bytes

≔⁰ηFθ≧⁻×ι⊖∕η⁵ηIη

Try it online! Link is to verbose version of code. Explanation: Port of @ovs' Python solution, except with a slightly rearranged formula r-=c*(r/5-1) which saves a byte when written in Charcoal.

≔⁰η

Start with zero heads.

Fθ

Loop through the numbers of flips.

≧⁻×ι⊖∕η⁵η

Calculate the expected number of heads.

Iη

Output the expected number of heads.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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