Find 'p' for an unfair coin [Editor: "as above" in the original], so that the coin can be used to choose...

probability/flips/unfair.three.choices New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Find 'p' for an unfair coin [Editor: "as above" in the original], so
that the coin can be used to choose between three choices with equal
probability in predetermined and finite number of tosses.

Problem n-1:
Same way, choose between 'n' choices with equal probability, given
arbitrary finite integer 'n'.

-- Risto Lankinen <rlankine@us.oracle.com>

[ Editor: this was Lankinen's Problem 2; his Problem 1, to which "as
above" referred, was not collected.  In the solution, p is the
probability of heads. ]

Show solution

For a given n, define R(m, i) to be the remainder when m!/(i!)(m-i)! is
divided by n-1.  Choose an m such that the equation

sum (i=0 to m) R(m, i)*(p^i)*[(1-p)^(m-i)] = 1/n

has a root between 0 and 1.  We can always find such an m; for
instance, if we choose m large enough so that (m+1)*(n-2)/2^m < 1/n,
then when p = 1/2 the left side of the equation will be smaller than
the right while for p = 0 or 1 the left side is always larger than the
right.  Let p be such a root.  For every i between 0 and m, assign
R(m, i) of the possible sequences of m flips with i heads to the first
outcome, and distribute the other sequences with i heads evenly among
the other outcomes.

For example, if n = 3, m = 4 works.  We have R(4, 0) = R(4, 4) = 1,
R(4, i) = 0 otherwise, so the equation becomes p^4 + (1-p)^4 = 1/3,
which has roots between 0 and 1.  We assign the sequences HHHH
and TTTT to the first outcome, the sequences HHHT, HHTH, HHTT, HTHT,
HTTH, HTTT and THTT (for example) to the second outcome, and all
others to the third.

Nice problem.

-- Adam Stephanides <astephan@students.uiuc.edu>