More Challenging Problems

Problem # 1 :

Suppose you repeatedly toss a fair coin until you get two heads in a row. What is the probability that you stop on the 10th toss?


I am now getting a solution to problem #1 that differs from the posted answers.


Method 1 : Write a program that goes through all 1024 HT combinations. I did this. 880 of the combinations had a HH in them. Of those 880, only 34 had HH for the last two tosses and no previous HH. So the probability that HH occurs after the 10th toss, but not previously is 34/1024 = 3.3%


Method 2 : "Markov chain"

Assume that after each toss, there are 3 possible states


S1) Last Toss was Tails.

S2) Last Toss was Heads, but two consecutive heads have not been tossed.

S3) Two consecutive heads have been tossed.


The trasitions probabilities are


50% for S1->S1, S1-> S2, S2->S1, S2->S3,

100% for S3->S3,

0 otherwise.


To compute the probabilities the first n tosses, you can use the matrix


[0.5 0.5 0]^n

[0.5 0.0 0]

[0.0 0.5 1]


times the vector [ 1 0 0].


Computing this matrix for n = 9 and n = 10 gives


n = 9 S1 = 55/512 S2 = 17/256, S3 =423/512

n = 10 S1 = 89/1024 S2 = 55/1024, S3 =55/64.


So the probability of an HH occuring amoung the first 9 tosses is 432/512. The probability of an HH occuring among the first 10 tosses is 55/64. So the probability that the first HH will occur after 10 tosses is


55/64 - 423/512 = 17/512 = 3.3%

All 1024 combinations is not an appropriate sample space because sometimes we stop before we get to 10 flips, and the sequences have varying probabilities depending on how long they are. Both of your methods suffer from this problem.


What the posted solution is saying is that since after each number of flips only one sequence terminates, then if f(n) is the number of outcomes after n flips, then


f(2) = 4

f(n) = 2[f(n-1)-1]


f(10) is the size of the sample space.

This is not as mathematically interesting, but I always feel a good old sledgehammer can show that for small numbers anyone can do maths....


We know that the series must finish THH and any series of ten tosses will finish this way 1/8 of the time.


Now we only have to look at seven tosses, out comes the hammer.

There are 128 possible tosses:


0 heads: 1 combination

1 heads: 7 combinations

2 heads: 21 combinations

3 heads: 35 combinations

4 heads: 35 combinations

5 heads: 21 combinations

6 heads: 7 combinations

7 heads: 1 combination


Picture the individual tosses as a series of boxes labelled:

1 2 3 4 5 6 7


for 0 and 1 heads, we know there are never two heads together.

for two heads, there are 6 ways of arranging so that two are together. (12,23,34,45,56,67)

for three heads there are 30 ways, but five are duplicated as triples, so 25 ways. (1,2*5,2,3*5 etc)

for four heads there is only one way not to have them together (1,3,5,7)

for five, six and seven, obviously none


so there are 0+0+6+25+34+21+7+1 ways = 94 combinations from 128 where there are heads together.

Therefore only 34/128 of the combinations have no heads together for seven tosses.

and we said at the start that this only works once in eight, so we get the figure 34/1024 as already shown.


I hope this inspires some hope in those with a passing interest in probability and only a light foundation in maths (I have massive interest in probability and a light foundation in maths [img]/images/smile.gif[/img] )

we can still make all ten tosses, its just the ones where we should have stopped dont "win"

B17—Germany Problem


During WWII, Boeing B17 bombers “nicknamed Flying Fortresses” were heavily used to bomb Germany Industry. It was rough sledding and many B17’s were lost in battle. During one period of the war, the average combat life of the B17 was 18 missions. A B17 pilot and crew were required to complete 25 combat missions. Assuming a constant probability or success or failure for all missions during the period in question, what is the probability for of success or failure for one mission?


I tried to solve this problem and didn’t come up with a good closed solution or problem definition. Although a different problem, the two heads in a row problem on the tenth toss reminded me of this problem. In the coin problem we know the probability of the coin flipping is 0.5. In this “B17—Germany” problem we can think of the B17 as a biased coin which flips success most of the time, but fails on the average after 18 flips. What is the probability? Is there an uncertainly in this problem definition because the coin is only flipped at the most 25 times for a specific crew – I don’t know? Maybe some of you guys can come up with a good logical definition and solution to this probably simple but slightly vague problem.


The simplifying assumptions to make this problem amenable to analysis are: (1) the average life of the B17 is 18 missions: that is, the coin is flipped on average 18 times before it loses; and (2) all planes and crews have identical ability or all coins have the same unfair bias.


bill

Being a fuzzy thinker – I would solve this problem using a Monte Carlo (brute force) approach. That is I would assume (estimate/swag ) a probability of the biased coin. Run a sufficient number of trials (iterations) and determine the average number of flips until the coin failed (the plane is shot down). I would repeat this process using various probabilities for the biased coin until the average number of flips (plane missions) approached 18.

I got your answer doing it their way. Their mistake was that there are 5/26 outcomes that terminate after 6 tosses, not 4/26. I agree that you must extend the sample space to 1024 to get equally probable events. I also generalized their method for all n:



In the following table continue means number of outcomes that do not terminate, and is equal to outcomes - terminate. 2*continue becomes outcomes for the next row. heads means number of continuations that end in heads. heads becomes terminate for next row.



Now the big step which they don't explain well:

heads = (continue-terminate)/2. This accounts for how many continuing sequences end in heads after the terminating sequences are removed. This was arrived at by noting that heads is the lesser of two numbers which add to continue and differ by terminate. Look at the first couple cases to see this. This can be rewritten as (outcomes-2*terminate)/2.

<PRE>

tosses outcomes terminate continue heads

2 4 1 3 1

3 6 1 5 2

4 10 2 8 3

5 16 3 13 5

6 26 5 21 8

7 42 8 34 13

8 68 13 55 21

9 110 21 89 34

10 178 <FONT COLOR="ff0000">34</FONT>



</PRE>

34/1024 = 3.3%



To genralize, if o(n) is outcomes after n tosses and t(n) is terminations after n tosses, we have:



o(2) = 4

t(2)= 1

o(n) = 2[o(n-1)-t(n-1)]

t(n) = [o(n-1)-2*t(n-1)]/2



probability = t(N)/2^N



So you really only need two columns.

Here is why I think each of these problems is interesting, perhaps more interesting than you even realized:


1. (fair coin) This is interesting because it's much much harder than it looks.


2. (biased coin) This is interesting because you might think that the coin that threw 2 out of 3 heads would be more likely to be biased than the one that threw 1 head. The opposite is the case.


3. (names in hat) This is interesting because you must use inclusion-exclusion to get the right answer.


4. (pentagon) This is interesting just because it's geometrical and has a logical solution.


5. (movie theatre) This is interesting because you have to think about it the right way, and then you have to notice that adding the probabilities for each person gives you the average. This is kind of like inclusion-inclusion where we always add and never subtract.


6. (proofreaders) This is interesting because it seems odd that you can know how many errors there are without actually finding them. For example, why couldn't there be 80 errors, with both readers finding 1-50, reader 1 finding 51-60, and reader 2 finding 61-80? Why couldn't there be a million errors that neither one found? Well there could be. There is an underlying assumption here that the fraction of errors a reader finds is constant no matter which set of errors you consider. This is not necessarily the case except on average as a probability. So what does this number we calculated really mean? Perhaps the expected value of the number of unfound errors.

1,1,2,3,5,8,13,21,34......sounds familiar :P

Very Nice BruceZ.


o(2) = 4

t(2)= 1

o(n) = 2[o(n-1)-t(n-1)]

t(n) = [o(n-1)-2*t(n-1)]/2


If we use standard techniques for recurrence relations, then we can solve those equations.

(I will use the Mathematica algebra package because I am lazy.) The result is


t(n) = (5 - Sqrt[5])/10* ((1 + Sqrt[5])/2)^n + (5 + Sqrt[5])/10* ((1 - Sqrt[5])/2)^n


which is Fibonacci as pointed out by lorinda.


Two questions for bruceZ:


1) How did you figure out t(n) = [o(n-1)-2*t(n-1)]/2?

2) How did you format the table? The last time that I posted actively in this forum, I used to be able to include html key words in these posts. Now those key words don't seem to have an effect.