hard question(no clue how to answer)

[vkaul]

let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. Calculate P{X>Y}


I found it to be the hardest question ever.

 

[dstefan]

The problem can be broken down by the outcome of the first toss of the two coins.

Bearing arithmetic typos, the answer should be (\frac{43}{58}).

 

[JoonHui]

Intuitively, the problem asks whether the pattern A (two heads in a row) can occur after the pattern B (three heads in a row). As you see it, the pattern B contains pattern A, so the probability is zero.

A little more rigorously, I need a little cheating Sheldon Ross' Stochastic Process. First, you need to find E(X)=6 and E(Y)=14 (nice exercises).

Define M=min(X,Y), then

E(Y) = E(M) + E(Y-M|Y>=X)P(Y>=X) + E(Y-M|Y<X)P(Y<X)

Obviously the third term in RHS is zero. Also,

E(X) = E(M) + E(X-M|Y<X)P(Y<X)

We can interpret E(Y-M|Y>=X) as a expected value of additional flips to get a pattern B after we have pattern A. Hence,

E(Y-M|Y>=X) = (1/2)(head appear at the next flip) + (1/2)(tail appear and start over)
= (1/2)(1) + (1/2)(1+E(Y)) = 8

Also,

E(X-M|Y<X) = 0 because we already have pattern A.

So we solve a system of equation and

E(Y) = E(X) + E(Y-M|Y>=X)(1-P(Y<X))
14 = 6 + 8(1-P(Y<X))

hence

P(Y<X) = P(X>Y) = 0.

I feel a little uncomfortable when I am asked this kind of questions because it is prone to misunderstanding. I hope that recuiters give clear questions as much as possible.

I don't think my solution is bullet-proof perfect, so if you have another, please share with me.

 

[Adam]

Intuitively, the problem asks whether the pattern A (two heads in a row) can occur after the pattern B (three heads in a row). As you see it, the pattern B contains pattern A, so the probability is zero.

I think you're making an incorrect assumption here. X and Y are two events based on two separate, independent series of coin tosses, from coins A and B, respectively. Here's an example:

Coin one:
T-T-T-T-H-H

Coin two:
H-H-H-T-T-T

Event X (two heads in a row from coin A) occurred after event Y (three heads in a row from coin B). In the language of the question, X=6 and Y = 3. Since X>Y is a possible event in the space, P{X>Y} must be greater than zero.

 

[Mr Doe]

Omitting the techincal stuff;

(\mathbb{P}(X=n)=\frac{1}{2}\mathbb{P}(X=n-1)+\frac{1}{4}\mathbb{P}(X=n-2), \mathbb{P}(X=2)=\frac{1}{4}, \mathbb{P}(X=3)=\frac{1}{8}), similarly we have
(\mathbb{P}(Y=n)=\frac{1}{2}\mathbb{P}(Y=n-1)+\frac{1}{4}\mathbb{P}(Y=n-2)+\frac{1}{8}\mathbb{P}(Y=n-3), \mathbb{P}(Y=3)=\frac{1}{8}, \mathbb{P}(Y=4)=\frac{1}{16}, \mathbb{P}(Y=5)=\frac{1}{16}).

Now, we have (\mathbb{P}(X>Y)=\sum_{n=4}^{\infty}\sum_{k=3}^{n-1}\mathbb{P}(X=n,Y=k)), but we assumed that tosses are independent, we have (\mathbb{P}(X=n,Y=k)=\mathbb{P}(X=n)\mathbb{P}(Y=k)). I leave to "experts" to finish this off.

 

[vkaul]

Omitting the techincal stuff;

(\mathbb{P}(X=n)=\frac{1}{2}\mathbb{P}(X=n-1)+\frac{1}{4}\mathbb{P}(X=n-2), \mathbb{P}(X=2)=\frac{1}{4}, \mathbb{P}(X=3)=\frac{1}{8}), similarly we have
(\mathbb{P}(Y=n)=\frac{1}{2}\mathbb{P}(Y=n-1)+\frac{1}{4}\mathbb{P}(Y=n-2)+\frac{1}{8}\mathbb{P}(Y=n-3), \mathbb{P}(Y=3)=\frac{1}{8}, \mathbb{P}(Y=4)=\frac{1}{16}, \mathbb{P}(Y=5)=\frac{1}{16}).

Now, we have (\mathbb{P}(X>Y)=\sum_{n=4}^{\infty}\sum_{k=3}^{n-1}\mathbb{P}(X=n,Y=k)), but we assumed that tosses are independent, we have (\mathbb{P}(X=n,Y=k)=\mathbb{P}(X=n)\mathbb{P}(Y=k)). I leave to "experts" to finish this off.

Finishing this off is not trivial at all.

 

[JoonHui]

I don't agree that

(
P(X=x) = {1\over 2}\mathbb{P}(X=x-1) + {1\over 4}\mathbb{P}(X=x-2)
)
(x>2) nor
(
P(Y=y) = {1\over 2}\mathbb{P}(Y=y-1) + {1\over 4}\mathbb{P}(Y=y-2) + {1\over 8}\mathbb{P}(Y=y-3)
)
(y>3). By definition P(X=x-k) is the probability that A get 2 heads in a row at x-k flips. A nor B does not flip after they get 2 or 3 heads respectively, so we cannot construct recursive equations in this way.

 

[vkaul]

The problem can be broken down by the outcome of the first toss of the two coins.

Bearing arithmetic typos, the answer should be (\frac{43}{58}).

How can the outcome of the first toss completely decide the matter. We are not calculating expectation here. We are calculating probability.

 

[JoonHui]

So what was the answer the recruiter told you? vkaul?

 

[vkaul]

So what was the answer the recruiter told you? vkaul?

He did not tell me the answer. I don't know. I felt so dumb not being able to do this question.

 

[dstefan]

How can the outcome of the first toss completely decide the matter. We are not calculating expectation here. We are calculating probability.

The equally probable outcomes of a first toss are (H,H), (H,T), (T,H), and (T,T).

Then,

(P(X>Y) = \frac{1}{4} P(X>Y | X(1)=H \& Y(1) = H) + \frac{1}{4} P(X>Y | X(1)=H \& Y(1) = T) + \frac{1}{4} P(X>Y | X(1)=T \& Y(1) = H) + \frac{1}{4} P(X>Y | X(1)=T \& Y(1) = T) )

Note that
(P(X>Y | X(1)=T \& Y(1) = T) = P(X>Y))
(P(X>Y | X(1)=T \& Y(1) = H) = \frac{1}{2})

Think in similar terms of the other two probabilities.

 

[vkaul]

The equally probable outcomes of a first toss are (H,H), (H,T), (T,H), and (T,T).

Then,

(P(X>Y) = \frac{1}{4} P(X>Y | X(1)=H \& Y(1) = H) + \frac{1}{4} P(X>Y | X(1)=H \& Y(1) = T) + \frac{1}{4} P(X>Y | X(1)=T \& Y(1) = H) + \frac{1}{4} P(X>Y | X(1)=T \& Y(1) = T) )

Note that
(P(X>Y | X(1)=T \& Y(1) = T) = P(X>Y))
(P(X>Y | X(1)=T \& Y(1) = H) = \frac{1}{2})

Think in similar terms of the other two probabilities.

I agree to the first probability.
The second probability above does not seem to be 1/2. They are not symmetric events. Secondly, you also did not even include the possibily of tie by just seeing the cases X>Y and Y>X what about the case X=Y.
Maybe I am incorrect, but I need to understand the logic behind this number 1/2

 

[Mr Doe]

I don't agree that

(
P(X=x) = {1\over 2}\mathbb{P}(X=x-1) + {1\over 4}\mathbb{P}(X=x-2)
)
(x>2) nor
(
P(Y=y) = {1\over 2}\mathbb{P}(Y=y-1) + {1\over 4}\mathbb{P}(Y=y-2) + {1\over 8}\mathbb{P}(Y=y-3)
)
(y>3). By definition P(X=x-k) is the probability that A get 2 heads in a row at x-k flips. A nor B does not flip after they get 2 or 3 heads respectively, so we cannot construct recursive equations in this way.

Please note that the recursion isn't correct "by accident". I'll comment just the first equation (the logic behind the second is the same). The mentioned event is equivalent to the event that first two tosses are heads, and that there aren't consecutive heads between the 2 and the n toss. From that you will get the recursion.
"Omitting the technical stuff" was the cruical statement in my post .

But I will agree with VKaul, the calculation of the sum is a technical obstacle.

I also agree on VKaul's comment on Dan's post, (\mathbb{P}(X=Y|X_1=T,Y_1=H)) is greater than zero.

 

[igram]

He did not tell me the answer. I don't know. I felt so dumb not being able to do this question.

Hey vkaul, was it the GS interview? what other questions did they ask? It would be helpful if you can share them, I have some interviews coming up.

 

[vkaul]

you will agree now; typo corrected

No I do not agree yet. I am not convinced about how you arrived at 1/2 for the second probability. If I am correct, your intuition is to say that once the second person gets head and the first person gets tails, both have equal chance of winning. I do not agree for two reasons:
1) no consideration of the event X=Y
2) Anyway X>Y and X<Y are not symmetric events with your conditioning. If I am correct, your intuition is to say that once the second person gets head and the first person gets tails, both have equal chance of getting 2 heads from there on. I do not think so. The one head for the second guy will be useful only if he gets two more heads consecutively after that and that probability will be similar to the first person getting two heads consecutively once he got the tail already. If the second guy does not get heads in the second or third tosses he again has to get three heads in a row and first guy has to get two heads in row. So P(X>Y)<P(X<Y) even with the conditioning. This is apart from problem 1 mentioned above.

Then rest of the terms in your expression are as complicated to compute.

 

[dstefan]

Actually, you are right, this requires more thought than what I initially thought.

 

[mhan]

Hi, I think you guys are right about needing to condition on the first couple tosses then applying recursion. I looked at a simpler case, let X be the number of flips for 1 head and Y be the number of flips for 2 heads. (I'll apologize for not knowing how to use TeX.)

We condition the results of the first toss of each sequence, so we have four cases for the set of first tosses: {H,H}, {H,T}, {T,H}, {T,T}.

Note: {T,H} means the sequence where we try to get 1 head got a tails, and the sequence where we try to get 2 heads got a head).

P(X > Y) = P(X > Y | {H, H}) P({H, H}) + P(X > Y | {H, T}) P({H, T}) + P(X > Y | {T, H}) P{T, H}) + P(X > Y | {T, T}) P({T, T})

P(X > Y) = 0 * P({H, H}) + 0 * P ({H, T}) + P (X > Y | {T, H}) P({T, H}) + P(X > Y) P({T, T})

P(X > Y) = P (X > Y) | {T, H})(1/4) + P(X > Y)(1/4)

Now the next step is to get another equation relating P(X > Y) and P (X > Y) | {T, H}), then we can solve them in a system of equations. Let's now condition on the 2nd toss.

Note: P (X > Y) | {T, H}) != 1/2

P (X > Y) | {T, H}) = P (X > Y) | {TH, HH}) (1/4) + P (X > Y) | {TH, HT}) (1/4) + P (X > Y) | {TT, HH}) (1/4) + P (X > Y) | {TT, HT}) (1/4)

P (X > Y) | {T, H}) = 0 * (1/4) + 0 * (1/4) + 1 * (1/4) + P(X>Y) (1/4)

P (X > Y) | {T, H}) = 1/4 + P(X>Y) (1/4)

Now we have two equations and two unknowns, and if we solve for P (X > Y) we get .0909.

 

[vkaul]

I must say it is a good start. But the number of cases to keep track increases almost exponentially going from this simple case to the harder problem.

 

[IlyaKEightSix]

This may sound really dumb, but from the get go:

P(2H)=1/4.
P(3H)=1/8.

So considering that these are independent events, the probability of the two heads should always be twice the probability of three heads, no matter where they are in the sequence.

Therefore, denote the event of three heads as P.

2P+P=1.
3P=1.
P=.33.

2P=.66667.

Probably there's a hole in this reasoning, but I'm thinking that if you're asked to compute this problem on an interview that the solution might be something clever like this.

That, or "The most clever solutions are usually the most beautiful. They're also usually wrong."

 

[vkaul]

Unfortunately the holes in this reasoning are so big, I will be more comfortable not giving an answer at all.