Repetitive Coin Flip Probability

[Trevortni]

I don't remember what made me start wondering this, but I thought I could post it before I go to bed tonight, and if nobody figures it out before I get a chance, maybe I'll take a stab at it.

<Scenario 1> Suppose I have a special quarter on my dining room table that I leave heads up before I go on vacation. Since all my family knows how precious *gollum* it is to me, they are loath to touch it; however, there is still a 5% chance that someone will flip it by the end of the day (of course, flipping it more than once a day is just unthinkable). What is the chance that it will be heads up by the time I get home from vacation at the end of the 20th day?

<Scenario 2> I'm going on a 20 day vacation again, but I'm taking my entire family with me this time, so we've invited my best friend to housesit. This friend is a bit of a joker, however; each day he has a 95% chance to flip my quarter (though even he couldn't bring himself to flip it more than once a day). If the quarter started heads up again, what is the probability of will be heads up when we get home? Is there any reason to expect that a general inverse probability like this will always result in either a direct or inverse final result (i.e. If f(x%) = y%, then f(100% - x%) = either y% or 100% - y%)?

<General> Given an x% chance of flipping every day, what is the chance that the quarter will be in the starting state at the end of n days?

EDIT: For the purposes of this problem, a flip is defined to be turning the coin over a single time, so that a heads becomes a tails and a tails becomes a heads. It is not performing a random flip of the coin.

[SuicideJunkie]

Well, the raw thing to do is just add up all the probabilities of it being flipped an odd number of times.

I'd also note that for the 95% case, it smells like it should be the inverse probability of the 5% case but only on odd numbered days. While being the same as the 5% case on even numbered days.

[doogly]

You give the probability of flipping as y, but let's use x=1-y, the probability it is undisturbed on a given day.
So the probability it is never flipped over your entire n day vacation is now simple to calculate, it is
x^n
And the probability of at least one flip is 1-x^n

As long as there has been at least one flip, we get to ignore all the flips except the most recent one. It's a fair coin and fair flip after all. So the probability it is heads after at least one flip is 1/2, probability it is tails is 1/2.

So the probability you return to see a heads is
x^n + (1 - x^n)/2 or
1 - (1 - x^n)/2

and these simplify to
1/2 + (x^n)/2
And this (x^n)/2 represents your (decaying) advantage from having started in the desired state.

If there's only a 95% chance it's undisturbed on a day, after 20 days there's down to a 36% chance it's been entirely undisturbed, and you have a 68% chance of seeing your beloved heads.

[Eebster the Great]

Let p be the probability of flipping the coin in a given day and d be the number of days. Let n be the number of times the coin has flipped. So for instance, in scenario one (p=0.05, d=20), there is a 0.05²⁰ probability of zero flips the whole vacation, i.e. P(n=0) = 0.05²⁰. Similarly, P(n=1) = 20 • 0.95 • 0.05¹⁹, and so on; it follows the binomial distribution. In general,
P(n=m) = (d choose m)p^d-m(1-p)^m if 0 ≤ m ≤ d and 0 otherwise.

Now, the probability that n is odd is the sum of the probabilities that it is 1, 3, 5, ..., d (or d-1 if d is even). That is, the sum from k=0 to (d-1)/2 of P(n=2k+1). Finally, plugging in the specific scenarios, we find,

Scenario 1: d=20, p=0.05
P(n is odd) = ∑_k,0,9 P(n=2k+1) =
∑_k,0,9 (20 choose 2k+1) .05^20-(2k+1) .95^2k+1 = 0.439211672704715355995 exactly.

Scenario 2: d=20, p=0.95
P(n is odd) = ∑_k,0,9 P(n=2k+1) =
∑_k,0,9 (20 choose 2k+1) .95^20-(2k+1) .05^2k+1 = 0.439211672704715355995 exactly.

This should not surprise you, as the scenarios are exactly symmetrical for even d. For odd d, you don't have this symmetry. So for instance, if d=21, p=0.05, then P = 0.5547094945657561796045, but if d=21, p 0.95, then P = 0.4452905054342438203955, the complement. Obviously for d=0, P=0, and for d=1, P=p.


Edit: I was assuming every "flip" was just turning the coin over from one face to the other to mess with you. If it's a fair flip, none of this applies and the arithmetic is much easier.

[Flumble]

If you express the problem as a transition matrix, you can parametrize it completely:

(wolfram clickity)
with t the chance that it'll be touched on a day, b the chance that the coin faces the other side after touching (either 1 or 0.5 depending on what the OP meant with "flip") and n the number of days. The [1 0] means the coin was facing 100% heads and 0% tails before you left. The first entry of the result is the chance that it's heads after you come back, the second tails.

If 'flip' means 'turn over to the other side' as is 3 out of 4 interpretations now, the formula simplifies a lot:

As usual, wikipedia is better at explaining the concept of markov chains as used here.

[Trevortni]

It looks like I overlooked a definition in my original post. For the purposes of this setting, a flip is not flipping the coin to a random side, but is turning the coin over, so that a heads becomes a tails, and a tails becomes a heads. I will be updating my original post to reflect this. It looks like most replies have correctly assumed this, but I think I spotted at least one that assumed the random definition of flip.

[Trevortni]

Internets to Flumble for a solution that accounts for eitherany definition of "flip". (After all, what if it's a random flip on a weighted coin?)

[Eebster the Great]

It looks like I overlooked a definition in my original post. For the purposes of this setting, a flip is not flipping the coin to a random side, but is turning the coin over, so that a heads becomes a tails, and a tails becomes a heads. I will be updating my original post to reflect this. It looks like most replies have correctly assumed this, but I think I spotted at least one that assumed the random definition of flip.

Junkie's and my posts were directed at the "changes face every time" interpretation, while doogly's is based on the "flips to a random face every time" interpretation, and Flumble's gives space to both.

[Flumble]

Internets to Flumble for a solution that accounts for eitherany definition of "flip". (After all, what if it's a random flip on a weighted coin?)

Do note that if b≠0.5, the coin has a really weird bias that tends to favour landing on the same side it was (b<0.5) or landing on the opposing side (b>0.5) rather than favouring heads or tails specifically. Now, I vaguely recall that throwing dice (in a specific way?) may favour the side that was up at the start of the throw (can't find the research though, so if anyone knows, please tell), but a normal biased coin would result in

with h the chance to land on heads.

Then again, for randomized flips doogly's approach is much more concise. And after some initial confusion, of course it works for unfair coins as well as fair ones.

[Eebster the Great]

A coin that is extremely asymmetrical could easily have a bias toward heads or tails. The normal process of flipping real coins tends to make them pretty resistant to those sorts of biases, but not completely so.

[doogly]

Right, the hard one is a bias towards "whatever I was just on."

[Eebster the Great]

Seems like that kind of bias would have to be in the method of flipping rather than the coin itself.

[Soupspoon]

(Eebster ninjas me. More pithily.)

An extremely consistent (and low-spin) flipping mechanism/technique and capture process in a highly controlled environment. Though you'd probably have to try harder to get close enough tolerances to be deliberately repeatable than you would to add in further sufficient statistical noise to overcome any inherent bias towards a given starting position upon the flipper(/hand) leading to a particular final landed state.

I've seen it done (a 'blank' coin in a low-pressure bell-jar, just to reduce other elements of uncontrollability). But even then it was difficult to make it consistent and was quite obviously an unfair toss but far from a guaranteed one.

(Fictional example)

Spoiler:

In a book I read a long time ago now, a "scientist class" character (one of several core protagonists, with interwoven storylines) fresh from a science enclave in the strange dystopia of the book's setting finds himself out in the 'real' world of the plebs, where it seems life was at least partly based around gambling on one-arm bandits so that those lucky enough to win it big would survive/whatever.

Stranded in this strange new world, he is opportunistically either gifted or finds a coin/token/cashcard sufficient to try out the slot machines himself. And gets a win (improbably early on, IIRC, but that's just bog-standard Plot Luck). Now being a trained scientist rather then the Gambling Class (or whatever the Elois/Morlock-like distinction was, in this setting) he does exactly the same thing again to win again. It helps him survive his (previously) fish-out-of-water situation, obviously, though may have then brought him to the attention of whatever Authorities there were, but I forget most of the rest of the tale.

Obviously, that has many flaws. Those machines wouldn't work like that. If they did, how could an intellectually-led newbie to the situation really chance upon the Vulcan-like fine-motor-control. If the Morlock community had been living and (perhaps) dying by the ability to 'get lucky', there surely would have been others who developed the 'feel' of the machines, even if they couldn't differentiate an inverse tensor in a rotating frame of reference, or tell you why they'd want to.

Still, the principle is the same. Give or take huge liberties taken in the name of moving the plot along, not to be taken too seriously. Unlike Roullette computers, that actually exist.

[jaap]

Seems like that kind of bias would have to be in the method of flipping rather than the coin itself.

Quite so.
Here's a demonstration of tossing a coin ten times in a row, getting heads each time.

(For full disclosure: that is me, and it took me only about 7 or 8 takes. Sorry, I couldn't resist posting it since it is kind of relevant.)

[Cauchy]

We can calculate the probability using generating functions.

Let p be the probability that the coin is flipped over on a given day. (In the opening post, this is p = .05 for the first problem and p = .95 for the second problem.) Then, the probability that the coin is flipped exactly k times across n days is (n choose k)*p^k*(1-p)^{n-k}, which is the coefficient of x^k in f(x) = (px + (1-p))^n. The total probability that the coin is in its initial position at the end of the n days is the sum of the even coefficients in this polynomial, which you can calculate easily as {f(1) + f(-1)}/2, or {1 + (1-2p)^n}/2.

In our specific cases of n = 20, and p = .05 or p=.95, this evaluates to {1 + (.9)^20}/2, or 0.560788327295284644005.

[Eebster the Great]

We can calculate the probability using generating functions.

Let p be the probability that the coin is flipped over on a given day. (In the opening post, this is p = .05 for the first problem and p = .95 for the second problem.) Then, the probability that the coin is flipped exactly k times across n days is (n choose k)*p^k*(1-p)^{n-k}, which is the coefficient of x^k in f(x) = (px + (1-p))^n. The total probability that the coin is in its initial position at the end of the n days is the sum of the even coefficients in this polynomial, which you can calculate easily as {f(1) + f(-1)}/2, or {1 + (1-2p)^n}/2.

In our specific cases of n = 20, and p = .05 or p=.95, this evaluates to {1 + (.9)^20}/2, or 0.560788327295284644005.

That is exactly what I posted:

Spoiler:

Let p be the probability of flipping the coin in a given day and d be the number of days. Let n be the number of times the coin has flipped. So for instance, in scenario one (p=0.05, d=20), there is a 0.05²⁰ probability of zero flips the whole vacation, i.e. P(n=0) = 0.05²⁰. Similarly, P(n=1) = 20 • 0.95 • 0.05¹⁹, and so on; it follows the binomial distribution. In general,
P(n=m) = (d choose m)p^d-m(1-p)^m if 0 ≤ m ≤ d and 0 otherwise.

Now, the probability that n is odd is the sum of the probabilities that it is 1, 3, 5, ..., d (or d-1 if d is even). That is, the sum from k=0 to (d-1)/2 of P(n=2k+1). Finally, plugging in the specific scenarios, we find,

Scenario 1: d=20, p=0.05
P(n is odd) = ∑_k,0,9 P(n=2k+1) =
∑_k,0,9 (20 choose 2k+1) .05^20-(2k+1) .95^2k+1 = 0.439211672704715355995 exactly.

Scenario 2: d=20, p=0.95
P(n is odd) = ∑_k,0,9 P(n=2k+1) =
∑_k,0,9 (20 choose 2k+1) .95^20-(2k+1) .05^2k+1 = 0.439211672704715355995 exactly.

This should not surprise you, as the scenarios are exactly symmetrical for even d. For odd d, you don't have this symmetry. So for instance, if d=21, p=0.05, then P = 0.5547094945657561796045, but if d=21, p 0.95, then P = 0.4452905054342438203955, the complement. Obviously for d=0, P=0, and for d=1, P=p.


Edit: I was assuming every "flip" was just turning the coin over from one face to the other to mess with you. If it's a fair flip, none of this applies and the arithmetic is much easier.

[Cauchy]

We can calculate the probability using generating functions.

Let p be the probability that the coin is flipped over on a given day. (In the opening post, this is p = .05 for the first problem and p = .95 for the second problem.) Then, the probability that the coin is flipped exactly k times across n days is (n choose k)*p^k*(1-p)^{n-k}, which is the coefficient of x^k in f(x) = (px + (1-p))^n. The total probability that the coin is in its initial position at the end of the n days is the sum of the even coefficients in this polynomial, which you can calculate easily as {f(1) + f(-1)}/2, or {1 + (1-2p)^n}/2.

In our specific cases of n = 20, and p = .05 or p=.95, this evaluates to {1 + (.9)^20}/2, or 0.560788327295284644005.

That is exactly what I posted:

Spoiler:

Let p be the probability of flipping the coin in a given day and d be the number of days. Let n be the number of times the coin has flipped. So for instance, in scenario one (p=0.05, d=20), there is a 0.05²⁰ probability of zero flips the whole vacation, i.e. P(n=0) = 0.05²⁰. Similarly, P(n=1) = 20 • 0.95 • 0.05¹⁹, and so on; it follows the binomial distribution. In general,
P(n=m) = (d choose m)p^d-m(1-p)^m if 0 ≤ m ≤ d and 0 otherwise.

Now, the probability that n is odd is the sum of the probabilities that it is 1, 3, 5, ..., d (or d-1 if d is even). That is, the sum from k=0 to (d-1)/2 of P(n=2k+1). Finally, plugging in the specific scenarios, we find,

Scenario 1: d=20, p=0.05
P(n is odd) = ∑_k,0,9 P(n=2k+1) =
∑_k,0,9 (20 choose 2k+1) .05^20-(2k+1) .95^2k+1 = 0.439211672704715355995 exactly.

Scenario 2: d=20, p=0.95
P(n is odd) = ∑_k,0,9 P(n=2k+1) =
∑_k,0,9 (20 choose 2k+1) .95^20-(2k+1) .05^2k+1 = 0.439211672704715355995 exactly.

This should not surprise you, as the scenarios are exactly symmetrical for even d. For odd d, you don't have this symmetry. So for instance, if d=21, p=0.05, then P = 0.5547094945657561796045, but if d=21, p 0.95, then P = 0.4452905054342438203955, the complement. Obviously for d=0, P=0, and for d=1, P=p.


Edit: I was assuming every "flip" was just turning the coin over from one face to the other to mess with you. If it's a fair flip, none of this applies and the arithmetic is much easier.

It's similar, but I a) used a different summing method, which b) gave a closed form general formula.