hey this is pressure locker you have a
fair coin that shows heads fifty percent
of the time and Tails fifty percent of
the time you and a friend play a coin
flipping game can you create a rule
classifying the coin flips so that you
win with probability exactly equal to P
and your friend wins with probability
exactly equal to one minus P the
probability can be any rational or
irrational number between 0 & 1
the game has to end in a finite number
of coin flips with probability one can
you figure it out you can also try this
extension to the problem now you have a
coin that shows heads with probability Q
between 0 and 1 but unfortunately the
value Q is unknown to you
in other words you have a biased coin
but you don't know the bias can you-now
figure out a game where you win with
probability P the value of P is known to
you the same restrictions apply the game
has to end in a finite number of coin
flips with probability one can you
figure out these problems give them a
try
and when you're ready keep watching the
video for the solution let's get started
with some examples imagine you wanted to
win a game with probability
three-fourths one way to do this is you
could imagine flipping the coin two
times this generates for equally likely
sequences of coin tosses we can classify
three of those sequences as a win for
you and one of those sequences as a loss
for you this will be game in which you
win three fourths of the time now
imagine instead you wanted to win a game
with probability 1 3rd we can slightly
modify this procedure we have for coin
tosses
what we do is we classify one of them as
a win two of them as a loss and we say
the third sequence two tails in row we
can just classify that as disregard
these two tosses and start all over
so flip two times again and we can have
the same roles on what you do with the
coin tosses you will win this game with
probability 1 3rd we can generalize this
procedure imagine you wanted to win a
game with probability x over Y you would
need to flip the coin just enough times
that you get to a value that's more than
why we can classify x of the sequences
as a win-win classified y minus x of the
sequences as a loss and then we can
classify the rest of the sequences as
starting over
just disregard them and start over
according the same roles you'll win this
game with the probability of x over Y
but what if you wanted to win a game
with probability 1/2 since 1 over pi is
irrational
we cannot write it exactly as x over Y
for integers X & Y so this procedure is
not going to be easily modified to
figure out things where we need an
irrational probability so we're going to
use a different procedure
the solution is to use binary numbers so
we'll write the probability P in terms
of its binary expansion so this will be
a sequence of fractions that are powers
of two
this can be written as zero point b1 b2
b3 and so on so just like we write
decimal numbers these are going to be
fractional numbers that are in binary
each of these fractional numbers b1 b2
these represent powers of one-half so
how's this going to be useful for us
I'll give some examples of binary
numbers so we have the fraction one-half
this can be written as one-half plus 0 /
2 to the power of 2 plus 0 / 2 to the
power 3 and so on so in binary form this
will be 0.1 and then there will be zeros
after that the number one third will be
written as point 0101 repeating it will
be 0 1 0 1 and so on 1 over pi also will
have a binary expansion this will go on
forever but there is a binary expansion
to this number
so how's this going to help us we have
the probability in its binary form
here's the game we're going to define
flip a coin until it lands on heads for
the first time let's say that's toss
number n the rule of the game is that if
B sub n equals 1 you win the game if B
sub n equals 0 then you lose the game
so for example let's say the probability
is one-third this will be 0 1 0 1 and so
on
you win if the first time the coin shows
heads is on an even number toss 246 etc
and you lose the game otherwise so how
come this game has a probability of
one-third of you winning the game
let's prove that it always has a
probability of P the probability you win
the game is the probability that the
first heads shows on toss number k times
the value of the binary digit in the
value K so the probability that you get
the first heads showing on toss k is 1
over 2 to the power of k and the
probability that the binary digit is
equal to one in that spot is exactly the
binary digit because the binary digit
and spot k is either going to be 0 or 1
what we have is we have come up with
exactly the binary representation of P
therefore the probability you win this
game is exactly equal to P so there's
another way you can use binary numbers
to create a game in which you win with
probability P we started with our binary
representation of Pee Wee now do
something slightly different for each
flip of the coin we record a one if we
flipped a heads and we record a zero if
we flipped tales we're going to keep
flipping the coin as long as flip k
equals the binary digit on k once we get
to a point where the flip differs say
that's toss n we're going to define that
you win the game if your flip was tails
and you're going to lose the game if the
flip was heads so why does this
procedure work let's go through the
example where p is equal to one-third we
have our binary representation so here's
how the game would work
let's imagine we flip tails heads heads
the first two digits 0 1 are the same as
the 01 in one-third but that third value
in one-third is equal to 0 and we
flipped a heads on our last one which
was different so we're going to stop
flipping after this third flip and the
last flip we had was a heads so we
differed and it was a heads so we're
going to define this as a loss if
instead we flipped tails tails that
would mean our second toss was different
from the binary expansion of one-third
and in this case the last flip differed
as a tails so in this case we would win
the game
so this may sound like a strange
procedure but there's an intuitive way
too
see why it works intuitively the coin
flips will define a random number Z
that's between 0 and 1 if this number Z
that we get to by flipping ends up being
less than P we are winning the game and
if it's more than P we lose the game
so basically we're creating with our
coin flips a random number between 0 and
1 and if this number ends up being in
the interval 0 to P we're going to win
so we win this game with probability P
here's a graphical way to see what's
going on in this game we start out with
our interval 0 1 let's suppose we have a
probability of P of one-third so we're
saying the winning interval is numbers
that end up between 0 and 1 3rd now the
first toss of a coin suppose it's a
heads so we know that our number Z is
going to start out with point one
well a number that starts out point one
is going to define something between
one-half and one it's going to at least
be one-half because point 1 means were
adding one-half to whatever remains so
if our first toss is a heads
we're going to end up in something
that's larger than one-third and there's
no way that we could end up in the
interval between 0 and 1 3rd so our
number differs in the very first spot
and it differs to be larger so we're
going to lose the game for sure
let's suppose we continued where the
first hostels details this instead would
define a number between 0 and 1 half we
can never get a number larger than
one-half because the first spot in our
expansion of z is equal to point zero so
in order to see where z ends up we're
going to have to flip again so let's say
at this point we flip tails so we're
point zero zero so now we're going to
define an interval that's actually
between 0 and 1 40 has to be less than
one-fourth from its form
furthermore we have a number Z for that
second digit 0 0 that's different from
the second digit of p but in this case
the differing digit is a tails so we
know that we are going to win this game
for sure to give one more example
suppose that we had tosses of tails
heads heads now the first time we
differed was the third toss
however we differed by being a heads so
we actually ended up in an interval
that's larger than one-third so we're
going to lose this game for sure
so now let's tackle the extension we
have a biased coin that shows with
probability heads with probability Q how
can we solve the game now what we're
going to do is we're going to make a
fair toss from the biased coin we're
going to flip the biased coin two times
this creates for possible different
tosses we don't know the probability of
each of these tosses but we're going to
classify them as follows
we're going to say if you toss two heads
or two tails just disregard that outcome
and start over if however you toss heads
tails classify that as a heads and if
you clap tossed tails heads classify
that as a tails so while we don't know
the exact probability of these outcomes
we can calculate the theoretical
probability because we know the coin
shows heads with probability Q so if we
wanted so the probability of heads will
be tossing a heads followed by a tails
so this will be Q times 1 minus Q the
probability of tossing a tails will be
the probability of tossing t followed by
H so this will be 1 minus Q times q what
you'll notice here is that the
probability of HT is exactly equal to
the probability of tea
eh in other words we have a game which
ends with heads or tails exactly fifty
percent of the time for each of those
two cases the probability of heads is
equal to the probability of tails in
other words we have made a fair coin out
of a biased coin so now the problem
reduces so what do we do if we have a
fair coin and we need to win the game
with probability P well we just solve
that problem we can use one of the
binary number procedures that have just
been described and we can get to a game
which we win with probability P so it's
an absolutely stunning result we can
simulate any probability P that we want
rational or irrational from a coin and
it can be a biased coin where we don't
even know the bias did you figure out
this problem thanks for watching this
video please subscribe to my channel and
make videos on Matt in game theory you
can catch me on my blog mind your
decisions you can fall on facebook
google+ and patreon you can catch me on
social media app pressure locker and if
you like this video please check out my
books their links in the video
description