Probabilistically fair prize splitting for two-player coin toss

Question

Introduction

Adam (A) and Bubbler (B) are playing coin toss, where the one who wins 5 times first would win the prize of $32. If the game is aborted when the scores are A:B = 4:3, how should they distribute the prize? Assume the coin toss is fair, so the winning chance of either player is 1/2 for each game.

The answer is:

Adam should take $24 and Bubbler should take $8. Possible cases are as follows:

A wins (score 5:3, chance 1/2): A wins the prize
B wins (score 4:4) then A wins (score 5:4, chance 1/4): A wins the prize
B wins (score 4:4) then B wins (score 4:5, chance 1/4): B wins the prize

Therefore, the chance of A winning is 3/4 and that of B is 1/4.

Challenge

In order to do the fair splitting of prizes, we should compute the chance of winning the prize for each player. Given the following information,

• X, how many times a player should win coin toss to win the prize
• Wa, how many times player A has already won
• Wb, how many times player B has already won

compute the chance of player A winning the prize.

Input and output

You can assume the three input numbers X, Wa, Wb satisfy the following:

• All numbers are non-negative integers.
• X > max(Wa, Wb), i.e. the game hasn't finished already.

You can choose to output a fraction or a floating-point number.

Scoring and winning criterion

Standard code-golf rules apply. Shortest code in bytes wins.

Test cases

X Wa Wb => Expected output
--------------------------
5  4  3 =>  3/4  = 0.75
5  3  4 =>  1/4  = 0.25
1  0  0 =>  1/2  = 0.5
4  3  1 =>  7/8  = 0.875
4  2  1 => 11/16 = 0.6875
6  4  2 => 13/16 = 0.8125

Answer 1

R, 36 32 bytes

function(X,A,B)pbeta(.5,X-A,X-B)

Try it online!

The closed formula from this answer suggested a natural probability distribution to use -- this is a Negative Binomial with \$X - W_b - 1\$ failures and \$X - W_a\$ successes, i.e., the probability that there are \$X - W_a\$ "successes" before there are \$X - W_b\$ "failures".

Further identities reduce the CDF of the negative binomial to the CDF of a beta distribution or in terms of the (regularized) incomplete beta function.

Answer 2

Wolfram Language (Mathematica), 44 bytes

Binomial[g=#-#2+t,k]~Sum~{k,0,t=#-#3-1}/2^g&

Try it online!

Not super short, but uses an algorithm that might lead to shorter code in other languages: the code calculates the sum of binomial coefficients which is the closed form for the result of the path-counting algorithms in other solutions.

Answer 3

Python 2, 62 56 bytes

f=lambda n,a,b:a<n>b and(f(n,a+1,b)+f(n,a,b+1))/2.or a>b

Try it online!

Returns a float. Uses a recursive approach.

Ungolfed:

def f(n,wa,wb):
    if wa<n and wb<n:
        return (f(n, wa+1, wb) + f(n, wa, wb+1))/2.0
    elif wa==n: return 1
    else: return 0

Answer 4

MATL, 24 bytes

x"TF1GEZ^!Ys@+1G<~s]P>Ym

Try it online! Or verify all test cases.

Input is X, then [Wa Wb]. Output is a floating-point number.

How it works

This enumerates all possible paths of length 2*X that emanate from the initial conditions defined by Wa and Wb. This length is enough to ensure that someone wins (actually length 2*X-Wa-Wb-1 would suffice).

For each path, the code determines who wins as follows. It keeps a cumultive sum of score for each player, computes how long each player has had score X or more along the path, and the winner is the player who has maintained that condition for longer. This is equivalent to, but golfier than, asking who reached X earlier in that path. Note that there can be no ties.

The result is the proportion of paths in which player A wins.

x      % Implicit input: X. Delete it
"      % Implicit input: [Wa Wb]. For each
  TF   %   Push [0 1]
  1G   %   Push X
  E    %   Multiply by 2
  Z^   %   Cartesian power of [0 1] with exponent 2*X. Gives a matrix with each
       %   Cartesian tuple contained in a row. Rows are in lexicographical order
       %   Each column is a step in the path, containing 1 if the user wins or 0
       %   otherwise
  !    %   Transpose. Each tuple is now a column
  Ys   %   Cumulative sum of each column. This is the accumulated gain along each
       %   path. Note that the matrix has more than one row; otherwise the
       %   cumulative sum would work along the single row
  @    %   Push Wa (first iteration) or Wb (second iteration)
  +    %   Add. This gives the total accumulated score along each path, including
       %   the initial score
  1G   %   Push X
  <~   %   Not less than?
  s    %   Sum of each column. This indicates for how long the score X has been
       %   reached, or exceeded, in each path
]      % End
P      % Flip. This reverses the results for player B, to reflect the fact that
       % the paths of the two users are complementary: user B increases their 
       % score when user A doesn't. Reversing the vector is equivalent to
       % replacing each path by its complement, thanks to the lexicographical
       % order of the Cartesian tuples
>      % Greater than? This indicates for which paths player A wins
Ym     % Mean. Implicit display

Answer 5

MATL, 11 bytes

.5ii-Z}3$Yg

Try it online!

This is a port of my R answer. Thanks to Luis Mendo for helping golf it down.

.5     # push .5
ii     # push both inputs, X, and [Wa, Wb]
-      # subtract, so stack is [.5, [X - Wa, X - Wb]]
Z}     # split array onto stack
       # so stack is [.5, X - Wa, X - Wb]
3$Yg   # (regularized) incomplete beta function with 3 arguments
       # implicitly output the probability

Also a nice short Octave solution:

Octave, 27 bytes

@(X,A,B)betainc(.5,X-A,X-B)

Try it online!

Answer 6

Jelly,  17 16  14 bytes

-2 thanks to Kevin Cruijssen

_µS’2*ḶB§‘>ḢÆm

A dyadic Link accepting the end-goal, X, on the left and the current state [Wa,Wb] on the right which yields a float of A's chances.

Try it online!

How?

Forms all binary strings of \$X-Wa+X-Wb-1\$ bits, treating 1s as a win for A and 0s as a win for B. Identifies those with at least \$X-Wa\$ 1s and takes the mean (i.e. winCount / total).

_µS’2*ḶB§‘>ḢÆm - Link: X, [Wa, Wb]
_              - subtract (vectorises)   -> V=[X-Wa, X-Wb]
 µ             - start a new monadic chain, f(V)
  S            - sum                          X-Wa+X-Wb
   ’           - decrement                    X-Wa+X-Wb-1
    2*         - two raised to that power     2^(X-Wa+X-Wb-1)
      Ḷ        - lowered range                [0,1,2,3,4,...,2^(X-Wa+X-Wb-1)-1]
       B       - to binary (vectorises)       [[0],[1],[1,0],[1,1],[1,0,0],...,[1,1,...,1]]
        §      - sums                         [0,1,1,2,1,...,X-Wa+X-Wb-1]
         ‘     - increment (vectorises)       [1,2,2,3,2,...,X-Wa+X-Wb]
           Ḣ   - head (V)                     X-Wa
          >    - greater than? (vectorises) A=[0>=X-Wa,1>=X-Wa, ...]
            Æm - mean                         A's win probability

Answer 7

Jelly, 12 bytes

_Ä’Żc@SH⁹¡ʋ/

Try it online!

A dyadic link taking the number to win as left argument and the coin tosses won so far by players b and a respectively as the right argument.

Based on the formula described by @GregMartin so be sure to upvote his answer too!

Explanation

_            | Subtract
 Ä           | Cumulative sum
  ’          | Decrease by 1
          ʋ/ | Reduce using the following as a dyad (left argument represents X - Wb - 1; right argument represents 2X - Wa - Wb - 1)
   Ż         | - Range from 0..left argument
    c@       | - Number of combinations for each using right argument as n
      S      | - Sum
       H⁹¡   | - Half the number of times indicated by the right argument

Jelly, 16 bytes

MḢ’¹2Ṭ+Çɗ€ÆmƊ}Ị?

Try it online!

An alternative Jelly answer that uses a recursive approach. A full program that takes as its argument a list of Wb, Wa, n and returns the answer as a float.

Explanation

M                | Indices of maximum
 Ḣ               | Head
  ’              | Subtract 1
              Ị? | If absolute of this less than or equal to one:
   ¹             | Then: Return this value
            Ɗ}   | Else following as a monad applied to the original argument to this link:
    2            | - Literal 2
        ɗ€       | - Apply the following to the implicit range 1..2 with the original argument as the right argument
     Ṭ           |   - Convert to logical list with 1 at the relevant index
      +          |   - Add to the original argument (effectively increments Wa for 1 and Wb for 2)
       Ç         |   - Call this link with the updated argument
          Æm     | - Arithmetic mean

Answer 8

Wolfram Language (Mathematica), 32 bytes

Beta[.5,a=#-#2,b=#-#3]/a~Beta~b&

Try it online!

Yet another port of the negative binomial CDF approach suggested by this answer.

Answer 9

Charcoal, 36 bytes

Ｎθ≔Ｅ⁻θＮ⁰ηＦＥ⁻θＮ¹ＦＬη«≔⊘⁺ι§ηκι§≔ηκι»Ｉ⊟η

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

Ｎθ

Input the desired number of coin tosses.

Ｅ⁻θＮ⁰η

Calculate the number of remaining tosses player A needs, and create an array of that length of zeros. The (1-indexed) nth entry represents that the probability of A winning given that he still has n tosses remaining and B initially has no tosses remaining.

ＦＥ⁻θＮ¹

Loop over the number of remaining tosses player B needs. Start with the probability of A winning given that he still has 0 tosses remaining and B has m tosses remaining as 1.

ＦＬη«

Loop over the probabilities.

≔⊘⁺ι§ηκι

Average the current probability (representing the case where A wins this toss) with the probability from the array (representing the case where B wins this toss).

§≔ηκι

Save this new probability in the array.

»Ｉ⊟η

Output the last probability calculated, which is for n=X-Wa,m=X-Wb.

Answer 10

JavaScript (Node.js), 44 bytes

a=>g=(b,c)=>a==b||a>c&&(g(b+1,c)+g(b,c+1))/2

Try it online!

Answer 11

Perl 6, 45 bytes

{m:g/\-//$_}o{[X+] .[1],|(^2 xx+^.sum)}o&[X-]

Try it online!

Takes arguments as f((a, b), x). Counts 2x-a-b-1-bit numbers with popcount less than x-b.

Explanation

                                        &[X-]  # Compute a-x, b-x
             {                        }o  # Feed into block
                          ^2            # Range 0..1
                             xx         # repeated
                               +^.sum   # ~(a-x+b-x) = 2x-a-b-1 times
                        |(           )  # flattened
                   .[1]   # b-x
              [X+]     ,  # Cartesian product with addition,
                          # computes popcount(i)-(x-b) for all i
{          }o  # Feed into block
 m:g/\-/  # Regex match '-' chars in string representation,
          # counting negative values
        /$_  # Divide by number of values

Answer 12

Java (JDK), 77 bytes

double f(int x,int a,int b){return(a<x&b<x?f(x,a+1,b)+f(x,a,b+1):a>b?2:0)/2;}

Try it online!

Credits

• Port of Chas Brown's Python 2 answer.
• -1 byte, thanks to ceilingcat

Iterative version, 89 bytes

(x,a,b)->{int r=0,i=1<<x*2>>a-~b,n=i;for(;i-->0;)r+=x.bitCount(i)<x-a?0:1;return 1.*r/n;}

Try it online!

Answer 13

05AB1E, 14 bytes

-¤sO<oL<2вO›ÅA

Inputs in the format and order [Wa, Wb], X.

Port of @JonathanAllan's Jelly answer.

Try it online or verify all test cases.

A port of @GregMartin's formula would be 16 bytes:

-¤sO<UFXNc}OXoz*

Try it online or verify all test cases.

Explanation:

-               # Subtract each value of the first (implicit) input-pair from the second
                # (implicit) input: [X-Wa,X-Wb]
 ¤              # Push its last value (without popping the list itself): X-Wb
  s             # Swap to get the list again
   O            # Sum them together: 2X-Wa-Wb
    <           # Decrease it by 1: 2X-Wa-Wb-1
     o          # Take 2 to the power this: 2^(2X-Wa-Wb-1)
      L         # Pop and push a list in the range [1,2^(2X-Wa-Wb-1)]
       <        # Decrease each value by 1 to make it [1,2^(2X-Wa-Wb-1))
        2в      # Convert each to a binary-list
          O     # Sum each inner list of bits
           ›    # Check for each if it's larger than the X-Wb: [X-Wb>1,X-Wb>2,...]
            ÅA  # Take the arithmetic mean of that list
                # (which is output implicitly as result)

-¤sO<           # The same as above
     U          # Pop and store this 2X-Wa-Wb-1 in variable `X`
      F         # Loop `N` in the range [0,X-Wb):
         c      #  Take the binomial coefficient (a.k.a. number of combinations) of:
       X        #   The 2X-Wa-Wb-1 of variable `X`
        N       #   And the loop-index `N`
      }O        # After the loop: sum all values on the stack
        X       # Push 2X-Wa-Wb-1 from variable `X` again
         o      # Take 2 to the power this: 2^(2X-Wa-Wb-1)
          z     # Take the invert of this: 1/(2^(2X-Wa-Wb-1))
           *    # And multiply it with the sum
                # (after which this is output implicitly as result)