Waiting for the First Success

Transcript

0:00Introduction

Hello everyone! Let me start with a small puzzle. You throw a die again and again, until a six appears. On average, how many throws will you need? And a second question. Suppose there has been no six in the first few throws. Is a six now due, more likely on the next throw? Many people say yes. Today we find out the truth. Waiting for the first success comes up in JEE probability questions. So, let's begin.

0:30The set-up: repeat until the first success

First, the set-up. We repeat a trial again and again, like throwing a die or tossing a coin. The trials are independent, and each one is a success with the same probability, small p, okay? Then q equals one minus p, the probability that a trial fails. Simple, right? Now our random variable, capital X, is the number of the trial on which the first success comes. Clear? So let me ask you this. What values can capital X take? And is there a largest value? The answer is one, two, three, and so on, without any end. The three dots mean the list goes on forever, so there is no largest value. Got it? Now, careful, this is not the binomial distribution. There, the number of trials, n, is fixed, and we count the successes. Here there is no fixed n, and we count the trials until the first success. With me?

1:28The first success on trial k

Now the main question. For the first success to come exactly on trial k, what must happen in all the trials before it? Yes, exactly, they must all fail! On screen, capital F is a failure and capital S is a success. The curly brace underneath says there are k minus one failures, and then one success, on trial k. Okay? The trials are independent, so we multiply: q for each of the k minus one failures, then p for the success. So P of X equals k is q to the power k minus one, times p. The capital P means probability, and the k minus one up high is the power. Right? Next, P of X greater than k. That means the first success comes after trial k. So what does that tell you about the first k trials? That is correct, they are all failures. Not even one success in the first k trials. So P of X greater than k is simply q to the power k. One short line, and no long sum to add up. Remember this shortcut. Clear?

2:35The mean waiting time

Now back to our first puzzle. Each throw gives a six with probability one sixth. Just from your feeling, how many throws do you expect to wait, on average? The mean, E of X, is the sum of k times q to the power k minus one, times p. The capital sigma means add, and k greater than or equal to one, under it, means k starts at one and never stops. And this sum works out to exactly one over p. We prove it in Example two. Okay? So for the die, p is one sixth, and one over one sixth is six. Six throws on average. If you guessed six, very good! The rarer the success, the longer the wait. Got it?

3:20The memoryless property

Now the second puzzle. Suppose the first m throws all failed, no six at all. Is a six now due? Is it more likely on the next throw? No, it is not, and many students fall into this trap. This is the memoryless property, and the vertical bar means given. P of X greater than m plus k, given X greater than m, equals q to the power k, for every m and k. With me? Why is this true? Use conditional probability. If X is greater than m plus k, it is surely greater than m, so the top is just P of X greater than m plus k. So we get q to the power, m plus k, over q to the power m, which is q to the power k. The bottom, q to the power m, is not zero as long as p is less than one, so dividing is fine. Okay? And q to the power k is exactly P of X greater than k. So after m failures, the wait starts afresh. The die has no memory, so a six is never due, and the answer to our second puzzle is no. Clear?

4:27Example 1: first head on the fifth toss of a fair coin

Now Example one, an easy one. Here it is: a fair coin is tossed until a head appears. Find the probability that the first head is on the fifth toss. Pause the video and try it first. Done? Okay, let's check. Here a success means a head. The coin is fair, so p is one half, and q is also one half. Okay? The first head on the fifth toss means four tails first, and then a head. On screen, capital T is a tail, and capital H is a head. So, four tails, each with probability one half. One half to the power four is one over sixteen. Is that our answer? No, that is the trap: we forgot the head itself, on toss five. So P of X equals five is q to the power four, times p, which is one half to the power four, times one half. The little dot on screen means times. Right? That is one half to the power five, which is one over thirty two. Small, isn't it? Four tails in a row before the first head does not happen often. Got it?

5:37Example 2: proving the mean wait is 1/p with an AGP sum

Now Example two, a little harder: let us prove the formula for the mean. Show that the sum, for k from one upwards, of k times q to the power k minus one, times p, equals one over p. Take the p outside first, then pause the video and try it. Done? Okay, let's check. With p outside, we need the sum of k times q to the power k minus one. Is this a geometric progression? Can we use the usual formula directly? Not quite, and this is the trap! Write it out. The sum is one, plus two q, plus three q squared, plus four q cubed, and so on. Each power of q has an extra number in front, so this is an arithmetico-geometric series, from sequences and series. We call its sum capital S, okay? The standard trick is to multiply S by q. Every term moves one place to the right, so we get q, plus two q squared, plus three q cubed, and so on. With me? Now subtract the second line from the first. On the left we get one minus q, times S, and on the right every coefficient becomes one, so we get one, plus q, plus q squared, and so on. That is a plain geometric progression, with sum one over one minus q. Okay? Divide by one minus q again, and S is one over one minus q, whole squared. Since one minus q is p, S is one over p squared. The two vertical bars mean mod q, the modulus of q. It must be less than one for these infinite sums, and it is, because p is more than zero. Right? Finally, multiply back by p. p times one over p squared is one over p, and the proof is done. This is exactly the formula that gave six throws for the die. Clear?

7:34Quick revision: first success, mean 1/p, memoryless

So, quick revision. First, P of X equals k is q to the power k minus one, times p: k minus one failures, then a success. Second, P of X greater than k is q to the power k, and the mean wait, E of X, is one over p. Third, the memoryless property: past failures never make a success due. Now try the practice problem on this page. All the best!