Expected stopping time

1. Jul 8, 2010

this is not a homework question, it was a interview question

Question:

suppose we keep flipping an unbiased coin every second, how long do you have to wait on average before you get two heads in a row.

hoping someone could help me out

Last edited by a moderator: May 4, 2017
2. Jul 8, 2010

Rogerio

Let's call P(k) the probability of getting those two heads right after k seconds.
So, the average time is
0*P(0) + 1*P(1) + 2*P(2) + ... + n*P(n) + ...

3. Jul 9, 2010

thanks i understand that suppose the Probabilty of head is 0.5. apparently the answer is 6 secons but how does
0*P(0) + 1*P(1) + 2*P(2) + ... + n*P(n) + .... = 6 ? thats what i dont understand yet

4. Jul 9, 2010

Stellaferox

For an answer see thread "number of rolls of a die to get a particular #"
Marc

5. Jul 9, 2010

SW VandeCarr

The probability of not getting two heads in the first two tosses is 3/4. Consider the average time as the time (or number of tosses) it takes to get a probability of 0.5 or less.

6. Jul 9, 2010

thanks all for you replies, i understand the idea, but still not sure how Average turns out to be 6.i think i am getting it. i need to think it over see what i come up with

7. Jul 9, 2010

SW VandeCarr

P(2 heads in a row)=1 -(.75)^3 = 0.58. That's three possible pairs (1,2; 3,4; 5,6), totaling 6 tosses or six seconds. However, if you consider possible pairs 1,2; 2,3, 3,4 you should be able, on average, to get a two in a row in four tosses. Which do you think is correct?

Last edited: Jul 9, 2010
8. Jul 9, 2010

techmologist

I don't understand that reasoning. Wouldn't that give the median time (approximately), and not the average?

9. Jul 9, 2010

SW VandeCarr

If you ran an experiment, what would the expectation be for the number of tosses before a pair of heads? I called it the "average" and I would expect the median would approach the mean for multiple fair trials. Do you disagree?

10. Jul 9, 2010

techmologist

It might, but it might not. I don't know for this particular problem. Some waiting times have distributions that are so weird that the median isn't any where near the mean. The waiting time until (# of heads - # of tails) = 1 has infinite mean, but I'm pretty sure the median is finite.

EDIT: I guess the median in my example would be 1, since the probability of starting out with a toss of heads is 1/2. Or is it 1.5? I forget exactly how median is defined for discrete random variables.

Last edited: Jul 9, 2010
11. Jul 9, 2010

SW VandeCarr

The parameter is mean number of tosses to obtain the first run of two heads=success.The usual method of calculating the probability of success over successive identical independent binomial trials (S or F) is to multiply the probability of failure and subtract that from one, P(S)=1-P(F)^k where k is the number of trials. I took the expectation to be lowest value of k where P(S) = 0.5 or more. Note the unit trial is two tosses, not one.

Last edited: Jul 9, 2010
12. Jul 9, 2010

techmologist

That's the part I don't get. That isn't the definition of expectation. Why do you take it to be that?

EDIT: Specifically, I think the idea that the expectation and the median will be the same needs justification. It isn't true in general.

13. Jul 10, 2010

SW VandeCarr

The expectation can simply be the ponderated sum of values X can take. The point where the probability of success exceeds that of failure seems reasonable for a binomial process. What would you choose as the expected value, p=1? It's actually not the mean because the actual mean 4,8125 in a fitted model or 6 tosses if we take discrete trials to be non overlapping sets of two coin flips (and that's the real question 1,2; 3,4; 5,6 or 1,2; 2,3, 3,4).

http://www.aiaccess.net/English/Glossaries/GlosMod/e_gm_expecta tion.htm [Broken]

Last edited by a moderator: May 4, 2017
14. Jul 10, 2010

techmologist

The article you link to defines expectation as the "ponderated" or weighted sum (values weighted by their respective probabilities). That is not what you are describing. "Average", "mean", "expectation", and "expected value" are all interchangeable. That's what I assumed the OP meant when he said "on average". In a distribution where the mean is infinite, the median might be a better "typical value" statistic. But here the mean exists. You can find it by conditioning on when the first tail comes up. If the random variable T is the waiting time for k heads in a row, and the random variable U is the waiting time for the first tail to appear, then you can find the expected value of T like this:

E[T] = E[E[T|U]] = k*Pr(U>k) + Pr(U=1)*(E[T]+1) + Pr(U=2)*(E[T]+2) + ... + Pr(U=k)(E[T]+k)

since E[T|U=j] = E[T]+j for j < k+1. If you do this for k=2, two heads in a row, you get E[T] = 6.

Last edited: Jul 10, 2010
15. Jul 10, 2010

SW VandeCarr

And that's exactly what I got in terms of tosses.(see post 7)

16. Jul 10, 2010

techmologist

Yes, but how could you know beforehand that the median and mean, two different statistics, would be the same? Consider the problem of how many rolls it takes to roll a five, say, on a single die. The break-even point is between 3 and 4 rolls. 3 rolls gives you P<0.5 for success, while 4 rolls gives you P>0.5 for success. But the mean number of rolls is 6.

17. Jul 10, 2010

SW VandeCarr

I got a calculated break even point from ln(0.75)x=ln(0.5); x=-0.693/-0.288=2.40625 trials=4.8125 rolls. This is the mean of a fitted pdf, but the discrete distribution mean is 6 rolls with the trials consisting of two roll non overlapping sets.

Why is the mean number of rolls (to get a given face) for a die 6?

Last edited: Jul 10, 2010
18. Jul 10, 2010

techmologist

I don't think your method of using non-overlapping sets of two rolls is valid for this problem. You have to allow for the possibility that the first run of two heads occurs on tosses 2 and 3, for instance, and not one of {1,2}, {3,4}, or {5,6}. I think it is an accident your method gives 6 as the median, while the correct answer for the mean is also 6. You might try your method for three heads in a row and see what answer it gives. The correct mean for that is 14 tosses.

Also, consider the simpler problem of how many tosses it takes to get one head in a row. Obviously one toss of the coin gives a chance of 1/2 of getting a head immediately, so the median is 1. But the mean number of tosses to get one head is 2 (see below).

When you have a Bernoulli process in which the probability of success on each trial is p, the expected waiting time T until the first success is 1/p. The random variable T has a geometric distribution. For a coin, p = 1/2 and the mean waiting time is 2. For a die, p = 1/6, so the mean waiting time is 6. To show this, let q = 1-p be the probability of failure on each trial:

E[T] = p(1 + 2q + 3q2 + ... + nqn-1 + ...) = p/(1-q)2 = p/p2

If we go back to your method of considering non-overlapping pairs of coin tosses, the probability of success there is p = 1/4, as you have pointed out. So the mean number of trials needed to get a success is 4 trials, for a total of 8 tosses. The answer of the OP's problem is smaller because your method leaves out possible ways of getting success.

Last edited: Jul 10, 2010
19. Jul 10, 2010

SW VandeCarr

That doesn't make sense. If my method leaves out ways of getting success, it should get a result larger than 8, not smaller than 8.

I do think that overlapping sets should be considered. So consider 12, 23, 34. That's three sets, the same number of tosses and sets as before. .

I don't understand your method of calculation. You're thinking in terms of waiting times and I'm thinking in terms of a series of random trials. You don't add probabilities in this situation. You subtract the product of the probabilities of failure from one to get the probability of success. P(S)=1-P(F)^k where k is the number of trials with a constant probability of failure.

Last edited: Jul 10, 2010
20. Jul 10, 2010

SW VandeCarr

If you use the mean r (p/1-p) where r=1st success in this context (r=1), the break even point and the mean number of trials is the same for two heads in a row (3). For three consecutive heads in the mean number of trials is 0.875/0.125=7 trials. However the break even point p>0,5 is 6 trials. That's the point where half the players will succeed. This is more to intuitive to me and I think post people. The negative binomial distribution has an infinite tail and the mean will be affected by outliers to the point where its less meaningful.

BTW when a trial consists of three tosses the number of tosses to break even is 18 and to the mean is 21.

Last edited: Jul 11, 2010