# Probabilistically fair prize splitting for two-player coin toss

## 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 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  • Can Wa and Wb be taken as a complex number Wa+j*Wb, where j is the imaginary unit? Dec 23 '19 at 0:44 • @LuisMendo That's OK. I/O is flexible as always. Dec 23 '19 at 1:37 • May i output 6/8 instead of 3/4? – tsh Dec 23 '19 at 2:35 • @tsh Yes, it's fine. Dec 23 '19 at 3:16 • @Bubbler What about binary or hex "decimals"? Dec 23 '19 at 11:21 ## 13 Answers # 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. # 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. • 33 bytes Dec 24 '19 at 4:59 • Alternately, this is the CDF of a negative binomial distribution if that's at all helpful. Dec 24 '19 at 4:59 • @Giuseppe That's a great approach, you should post it as an answer! Note that you can shave off 1 more byte by making the denominator a~Beta~b. Jan 3 '20 at 20:54 • Sure, done. Jan 3 '20 at 21:34 # 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  # MATL, 24 bytes x"TF1GEZ^!Ys@+1G<~s]P>Ym  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  • Poorly golfed, but 14 bytes using the incomplete beta function, as it's the CDF of the negative binomial. Dec 24 '19 at 4:55 • (and the beta distribution too!) Dec 24 '19 at 5:04 • @Giuseppe You should definitely post that! A little shorter: tio.run/##y00syfn/X880M1M3qtZTJTL9/39TrmgTBeNYAA Dec 24 '19 at 10:27 • Ah, Z}, that's what I was looking for. Thanks! Dec 24 '19 at 15:14 # 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! # 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) [,,[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  • I'm not too familiar with Jelly, but isn't µS÷L just Æm? Jan 3 '20 at 10:43 • Indeed sum/length is mean - thanks! Jan 3 '20 at 11:26 # 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  # 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. # 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. # 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! # Perl 6, 45 bytes {m:g/\-//$_}o{[X+] .,|(^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
.   # 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


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

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

# 05AB1E, 14 bytes

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


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

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

-¤sO<UFXNc}OXoz*


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)