This employer has taken extra steps to respond to reviews and provide job seekers with accurate company information, photos, and reviews. Interested for your company? Learn More.

Part of a `Trading Assistant Intern` Interview Review - one of `51` `TransMarket Group LLC` Interview Reviews

Answers & Comments

▲

4

▼

of 4votes

I think the answer should be this:

Since the probability of getting two heads in a row and getting two tails in a row is the same, we only need to figure out the probability of the total. The remaining event is:

1 head 1 tail......due to different order, events should be 2

Therefore the probability=0.5(1-2(1/2)^N)=0.5(1-(1/2)^(N-1))

Since the probability of getting two heads in a row and getting two tails in a row is the same, we only need to figure out the probability of the total. The remaining event is:

1 head 1 tail......due to different order, events should be 2

Therefore the probability=0.5(1-2(1/2)^N)=0.5(1-(1/2)^(N-1))

▲

0

▼

of 0votes

Only solution I could think of, which took quite some time, was to actually start by drawing a tree of possible outcomes. From there, I could see only three different states at each node. Either I am in a state similar to my initial state (when I toss a tail), I can also be in tilt state (I have just flipped heads after flipping a tail) or I am in the done state (I have just flipped heads after having flipped heads before).

I consider that someone would only continue flipping if he/she has not flipped two heads in a row. That is, is not in the done state.

That is, for any toss level N, it wrong to assume that number of nodes is equal to 2^N. It will be strictly smaller as of level N = 3.

Anyway, after 3-4 levels drawn, one should see a pattern, that is, the number of tails, or initial state nodes (is), at a level N is equal to the number of is's I had at level N-1 + the number of is's I had at level N-2. We can thus write:

is(N) = is(N-1) + is(N-2).

we then realize that at every level N, the number of tilt nodes (t) is equal to the number of initial states from the previous level. That is:

t(N) = is(N-1)

That makes sense, because on the level N-1, all initial states output one tail (becoming a new initial state at level N) and a heads (becoming a tilt state at level N). the other states of level N-1 are either done (so no continuation) or tilt. The possible outcomes of a tilt state are either done or initial state (if I flip heads again, I am done, so I can't go from tilt to tilt.)

One then realize that following the same logic, the number of done (d) nodes for a level N is given by:

d(N) = t(N-1) = is(N-2)

that is, at every level (as of the second level, or two tosses), I will have a number of done outcomes equal to the number of initial states to levels (or tosses) ago. So the general recursive formula to get the number of done nodes for a certain level really is:

d(N) = is(N-2) = is(N-3) + is(N-4)

We note, by definition:

is(N) = 0, is N<0

is(N) = 1, if N = 0, or 1

is(N) = is(N-1) + is(N-2) otherwise.

Furthermore, the probability of being at any node of a level N is simply (1/2)^N. So if I want to find the probability that I observed at least one occurrence of 2 heads in a row. I simply add the number of done nodes from level 1 to N multiplying them by the probability of them occurring at each level. That is:

P(hh after N tosses) = sum(from i = 1 to N) (d(i).(1/2)^i).

E.g. for N = 2, I get:

d(1).1/2 + d(2).(1/4) = s(-1).1/2 + s(0).(1/4) = 0 + 1/4.

We know that this is true. you can test it for a larger number of tosses and see it is true. as N goes to infinity, the sum will converge to 1, as I have theoretically no chance of never tossing 2 heads in a row if I throw a coin an infinity number of times.

I haven't found a solution that didn't use recursions. There probably is one, I'd be interested in seeing one.

I consider that someone would only continue flipping if he/she has not flipped two heads in a row. That is, is not in the done state.

That is, for any toss level N, it wrong to assume that number of nodes is equal to 2^N. It will be strictly smaller as of level N = 3.

Anyway, after 3-4 levels drawn, one should see a pattern, that is, the number of tails, or initial state nodes (is), at a level N is equal to the number of is's I had at level N-1 + the number of is's I had at level N-2. We can thus write:

is(N) = is(N-1) + is(N-2).

we then realize that at every level N, the number of tilt nodes (t) is equal to the number of initial states from the previous level. That is:

t(N) = is(N-1)

That makes sense, because on the level N-1, all initial states output one tail (becoming a new initial state at level N) and a heads (becoming a tilt state at level N). the other states of level N-1 are either done (so no continuation) or tilt. The possible outcomes of a tilt state are either done or initial state (if I flip heads again, I am done, so I can't go from tilt to tilt.)

One then realize that following the same logic, the number of done (d) nodes for a level N is given by:

d(N) = t(N-1) = is(N-2)

that is, at every level (as of the second level, or two tosses), I will have a number of done outcomes equal to the number of initial states to levels (or tosses) ago. So the general recursive formula to get the number of done nodes for a certain level really is:

d(N) = is(N-2) = is(N-3) + is(N-4)

We note, by definition:

is(N) = 0, is N<0

is(N) = 1, if N = 0, or 1

is(N) = is(N-1) + is(N-2) otherwise.

Furthermore, the probability of being at any node of a level N is simply (1/2)^N. So if I want to find the probability that I observed at least one occurrence of 2 heads in a row. I simply add the number of done nodes from level 1 to N multiplying them by the probability of them occurring at each level. That is:

P(hh after N tosses) = sum(from i = 1 to N) (d(i).(1/2)^i).

E.g. for N = 2, I get:

d(1).1/2 + d(2).(1/4) = s(-1).1/2 + s(0).(1/4) = 0 + 1/4.

We know that this is true. you can test it for a larger number of tosses and see it is true. as N goes to infinity, the sum will converge to 1, as I have theoretically no chance of never tossing 2 heads in a row if I throw a coin an infinity number of times.

I haven't found a solution that didn't use recursions. There probably is one, I'd be interested in seeing one.

▲

0

▼

of 0votes

sorry for all the typos, the solution should be understandable in spite of that.

** To comment on this question, Sign In with Facebook or Sign Up **

Tags are like keywords that help categorize interview questions that have something in common.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

We're sorry but your feedback didn't make it to the team. Your input is valuable to us – would you mind trying again?

Browse:

Copyright © 2008–2014, Glassdoor. All Rights Reserved. Your use of this service is subject to our Terms of Use and Privacy & Cookies Policy. Glassdoor ® is a registered trademark of Glassdoor, Inc.

Sign In with Facebook

We do not post on Facebook

Sign In with Facebook

We do not post on Facebook

votes

Then since the subsets can be:

1. all tails

2. 1 head 1 tail 1 head 1 tail ....

3. at least 2 heads consecutively appear once

So Pr(3) = 1- Pr(1) - Pr(2) = 1- (1/2)^N - (1/2)^N

= 1 - power(1/2,N-1)

DelusiononOct 6, 2012Flag Response