More Challenging Problems

http://bsuvc.bsu.edu/~d004ucslabs/probability.html


Since the answer to one of the problems is not given, and the answer to another is completely wrong, my answers will appear in a post below.

1. The probability of not getting heads in 2 tosses is 3/4. To get two heads in a row on exactly the 10th toss, we have to NOT get two in a row in 4*2 flips, and then get two heads on throws 9 and 10. The probability of this is

(3/4)^4(1/2)(1/2) = 7.9%.


2. This result is counterintuitive. The posted solution is fine except the line:


Thus, the probability of both coins coming up with the given results is 2/27.


Should read:


Thus, the probability of both coins coming up with the given results is (1/2)(4/9) = 2/9.


3. (My solution) The posted solution would be correct only if the names were replaced in the hat after each draw. That isn't the way this kind of thing works, or some people might not get any presents, and some might get several. The correct solution is to note that if f(n) is the number of ways n people can draw names without drawing their own, then f(n) satisifes:


f(2) = 1

f(n) = (n-1)f(n-1)


Thus, f(n) = (n-1)!


So the probability is 9!/10! = 1/10.


4. The posted solution is clever. Mine is to note that you can only see two sides of something if one side slopes away from you less than 90 degrees. Since the angles of a pentagon are 108 degrees, the sides "stick out" 18%. We can see 3 sides as long as we are not more than 18 degrees off center to any one side in either direction for a total of 36 degrees per side. Since there are 5 sides, the probability is 36*5/360 = .5.


5. (My solution) The tallest person will always be visible. The second tallest person will be visible if and only if he is in front of the tallest person, which has probability 1/2. The third tallest person will be visible if and only if he is ahead of the tallest and second tallest people, which has probability 1/4, etc. Now notice that since one person OR MORE will be visible all the time, two people or more will be visible half the time, and three people or more will be visible 1/8 of the time, that means that exactly 1 person will be visible 1/2 the time, exactly 2 people visible 1/4 of the time, etc. So the expected value of the number of visible people is:


1/2 + 2/4 + 3/8 + ... (10 terms)


We know this sums to approximately 2 people visible on average.


5. Perhaps this is more intuitive. 50 errors were found by both proofreaders, and this was 50/70 of the errors found by the second reader alone. So if P(A) and P(B) are the fractions of the total errors found by readers A and B, then

P(A)P(B) = (50/70)P(B) so P(A) = 50/70. Since A found 50/70 of the errors and he found 60 errors, there must be (70/50)(60) = 84 errors total, so 4 errors were undetected.

Ignore my explanation for 1, and look the one on the other website. You can't just consider the individual pairs since you could get a head at the end of one pair and at the beginning of the next.

Nice Q's !


But you are wrong on #3 ! I guess ...

Great Problems BruceZ. I have some comments below.


Question 1 :

I agree that the posted solution to #1 is correct, but it is not very enlightening. It would be very hard to extend the given solution to n=10000. I will post my solution to problem #1 separately.


Question 3 :

I agree that the posted solution would be correct if the names were replaced in the hat after each draw.


I disagree with your solution to #3. You claim that


f(2) = 1

f(n) = (n-1)f(n-1)


where f(n) is the number of ways n people can draw names without drawing their own. Obviously f(2) = 1. It is easy to write out the 6 permutations to check that f(3) = 2 = 2*1 which agrees with your formula. When I wrote out the 24 permuatations for f(4), I got f(4) = 9, which does not obey your formula.


Question 5 : I like your reasoning on this one. I got slightly different numbers. You state that the 3rd tallest person would be visible 1/4 of the time. I think that he would be visible 1/3 of the time. There seem to be 6 equally likely possibilities to me: 123, 132, 213, 231, 312, 321. In 1/3 of these possibilities the 1 can be seen. Similarly, I think the nth person can be seen with probability 1/n, so then, using your reasoning, the average number of people seen in an N person line would be


1+ 1/2 + 1/3 + 1/4 + ... + 1/N

I think problem #3 is essentially the same as the problem posted by math geek.


math geek -- Saturday, 17 August 2002, at 5:26 a.m


If they are the same problem, then the answer would be the same as the posted solution : 0.36787946428572.

Seeing the 3rd tallest person doesn't mean you can see 3 people or more. You might only see the 3rd tallest and the tallest, with the rest obscured behind the tallest. Also, the probability of the 3rd tallest being visible is 1/3 not 1/4. The probability of the nth tallest person being visible is (n-1)!/n! = 1/n.


With these corrections the problem is actually eaiser. Notice that if we just add the probabilities for seeing the tallest, 2nd tallest, etc. people, we will get the desired average since we will be counting all the times we see 2 people exactly twice, all the times we see 3 people 3 exactly 3 times, etc. So the series is:


1 + 1/2 + 1/3 + ....+ 1/10 = 2.93


So almost 3 people would be visible on average.

I don't know what the hell I was thinking. My recursion doesn't work because after the first person chooses a name, although there are n-1 names left, it is not the same as n-1 people choosing n-1 names because one of their names may already be taken.


This is a little better than the math geek problem because since there are only 10 names, you have to use inclusion-exclusion or your answer will be off. If you assume indpendence or you will be off by 2%.

I fixed #5 above before I saw you answer. This is correct.

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 /images/smile.gif )

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.

If you assume that that H=plane lost, T=plane completes mission, then a probability of H=1/18 gives an average number of missions of 18 (17 good missions, and one bad.) To compute the probability of surviving n missions, just do


(17/18)^n.


For 25 missions we get 0.2396 probability of survival.

"During one period of the war, the average combat life of the B17 was 18 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?"


Bill, to answer your question about a closed solution...


The probability P of being shot down on the nth mission is:


P(n) = p (1-p)^(n-1)


where p is the chance of being shot down on any one mission.


This is the geometric distribution. The geometric distrubution has a mean of:


mu = 1 / p


Since you're given that mu = 18 ... well, it follows that p = 1/18, and so your probability for success on a particular mission is 17/18.


It's not that tough if you remember what the moments of the geometric distribution are.


PP


BTW, if you're curious about how to find the mean, variance, etc. of the geometric distribution from scratch, try this website:


http://mathworld.wolfram.com/GeometricDistribution.html

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


We start by determining how many of the outcomes that continue at each stage end in heads, because that is how many will terminate at the next stage. Since the ones that terminate all end in heads, these are removed from the pool of total outcomes. So of the ones that continue, there will be more that end in tails than heads. The difference between the number of continuations that end in tails and the number that end in heads is equal to the number that terminate. The sum of the number that end in tails and the number that end in heads is equal to the number that continue. So if h is the number of continuations that end in heads, and k is the number that end in tails, c is the number that continue, and t is the number that terminate, we have


k+h=c

k-h=t


subtracting gives 2h=c-t so h =(c-t)/2


If o is the number of outcomes, c = o-t, so

h = (o-2t)/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.


All you have to do is put (code) before the table and (/code) after the table (except use [] instead of () since I can't do it here) and the table will appear as you type it. To make a number red, use (red) and (/red). These are in posting hints.


I suspected Fibonacci was involved in here somewhere. By the way, did you know that


[1+sqrt(5)]/2 = 1 + 1/(1+1/(1+1/(1+1/(1+....


it is also equal to sqrt(1+sqrt(1+sqrt(1+...


To see this, solve x = 1 + 1/x and

x = sqrt(1+x)


The resulting quadratic gives the z-tranform for the difference equation that yields the Fibonacci series.

hello irchans & PseudoSerious,


Thanks for the feed pack for the B17-Germany problem. Say 24% survival -- boy that sure seems like those B17 guys had it rough. I once worked for an ex-B17 pilot back in Ohio in 1955. He mentioned that while flying over Germany many of the B17's beside him would turn into a ball of fire. Later on things got better when the P51 fighters were helping out as escorts.


Thanks


Bill

Bill,


I remember reading a spy novel where the spies had to impersonate veteran fighter pilots that had faced a lot of combat with poor odds of survival. None of the spies succeeded because there was something hard to imitate in the attitude of those veterans that had faced death so many time. Did your ex-B17 pilot boss have a unique attitude?