This video looks great and I understand the general function like f(n)=1/2(f(n-1)+1)+1/2(f(n)+f(n-1)+1);but I don't understand the eariler when.Why x=1/2(x+1)+1/4(x+2)+1/8(x+3)+3/8;Thank you so much for your explaination.Wish you everything goes well
Hey, thank you! If you look at the probability tree above, we are just averaging over all the leafs. The +1/+2/+3 come from the extra tosses, the 1/2,1/4,1/8 are the probabilities and the 3/8 comes from the 1/8 probabilities of needing 3 tosses. I would recommend you check out my Tennis Tournament video, in which we use the same 'strategy', but might be easier to understand in that scenario.
This kind of problems are very easily to be solved by recursive equation. A more general question of this is called pattern match (e.g., the expected number of toss needed to see the first pattern HTTH), which can also be solved by solving recursive equations.
I had a question about when you set up the recursive equation. You had f(n) = 1/2(f(n-1) + 1) + 1/2(f(n-1) + 1 + f(n)) So the first part represents throwing the last H and game ends, and the last part represents throwing a T and starting over. So why is it f(n-1) + 1 + f(n) inside the bracket and not just f(n) + 1? Because if you throw a T, you can just increase the overall expectation by 1 right? For e.g expected throws until a 6: E = 1/6(1) + 5/6(E+1), where you can just write E + 1 for the case when you don't throw a 6. Thanks in advance. Love your interview question videos!
You are right, that is what those parts represent. You also need to take into consideration that after you get a T, you start over (since the problem states that you are looking for consecutive heads). This gives you: f(n-1) + 1 up until now (similar to the first term) and f(n) starting from here, to reach the n consecutive heads.
Hey Harry, Happy to know that my content is useful and wishing you the best of luck in the upcoming interview. I do have a video planned for release tomorrow, so make sure you hit the alarm bell to be notified when it's up. While I'd like to be able to do more of them, they do take quite a lot of time (coding the vid, recording the audio, editing the audio, editing the final vid).
I would just throw in tha these kind of stochastic algorithms as presented at the end converge at the rate of sqrt of n. So If you have 1million toss simulations, expect maybe around a .001 accuracy
You are right about the rate of convergence. In this case, the bit with the simulations is not intended as proof and it's not formal in any way. The reason why that is included is more to be able to see some examples and to bring a more "practical" approach to the problem. Also, I hope at least, that including the code in the video is at least somewhat helpful for some people watching that want to check their results in other examples.
Hi and thank you for the comment! In the last steps we do the following: 1) Replace f(1) with 2, thus 2^(n-1)*f(1)=2^(n-1)*2=2^n 2) Compute the bracket, which is the sum of a geometric progression (en.m.wikipedia.org/wiki/Geometric_progression). Using the formula from the page, for a=2, r=2, n=n-1, we get 2*(1-2^(n-1))/(1-2) =(2 - 2^(n))/(-1) = 2^n - 2 3) Summing them up, and taking into account that 2^n+2^n = 2* 2^n = 2^(n+1), we arrive at the final result, 2^(n+1) - 2 Hope this helps, let me know if it doesn't :)
is there any reason we couldn't use the geometric distribution, define the first success as getting '3' heads, and then look at the expected value for a geometric distribution?
For a geometric distribution to work in this case we have to define the trial first, and then when such an experiment is a success or failure. To be able to consider "3 consecutive heads" as a succes means that our trial is tossing 3 times. But, you can get 3 consecutive heads from 2 failures of this trial: (THH)(HTT). So a geometric distribution does not fit this problem. This is the only approach that I could think of that could include a geometric distribution, and it does not seem to work. Do you have another solution that can model the tosses as geometric trials?
Hey, thanks for the video Can you please suggest resources to practice such kind of questions except '50 challenging problems in probability' and xingfengxu's book.
Hello, I think that is no clear how did you derive the first equation of f(n) = 1/2(f(n-1) + 1) + 1/2(f(n-1) + 1 + f(n)) I think that you should replace f(n) by f(n-1) {f(n-1) = 1/2(f(n-1) + 1) + 1/2(f(n-1) + 1 + f(n)) } as you do for the first example with 3 Heads because the second knot is derived from the first one which is f(n-1) and not f(n).
I can see how this can be confusing. The initial point, the one in which you already have n-1 consecutive heads is not split into two cases, but extended with the next toss. Meaning that we are interested in the expected tosses for n. You can see how the equation you propose gets you that f(n)=-2, and that makes no sense in the context of tosses. The differences between the case with 3 and the generalized proof is that for the former you start from the initial toss, but for the latter you start from n-1 tosses. Hope this helps!
Hi. Thanks for the message and for the feedback! It's quite hard to find the line between being too explicit (and thus boring) and being too concise (and sometimes overlooking simple explanations), especially on RUclips when the only thing you know about your audience is their age. What formula are you referring to?
Why did you not use a geometric distribution? A coin toss is a perfect bernoulli trial so it seems like this question is begging for a geometric distribution lol
Hey, as I also answered to a different comment: While a coin toss is a perfect geometric distribution, the "succes" in our case is not getting a head, but getting 3 consecutive ones. So the desired Bernoulli trial is tossing a coin 3 times. But, you can get 3 consecutive heads from 2 failures of this trial: (THH)(HTT). So a geometric distribution does not fit this problem. This is the only approach that I could think of that could include a geometric distribution, and it does not seem to work. Do you have another solution that can model the tosses as geometric trials?
Another neat way of solving this is by considering an absorbing Markov chain with three consecutive heads (HHH) being the absorbing state.
That's right! That would be a really neat solution!
This video looks great and I understand the general function like f(n)=1/2(f(n-1)+1)+1/2(f(n)+f(n-1)+1);but I don't understand the eariler when.Why x=1/2(x+1)+1/4(x+2)+1/8(x+3)+3/8;Thank you so much for your explaination.Wish you everything goes well
Hey, thank you!
If you look at the probability tree above, we are just averaging over all the leafs.
The +1/+2/+3 come from the extra tosses, the 1/2,1/4,1/8 are the probabilities and the 3/8 comes from the 1/8 probabilities of needing 3 tosses.
I would recommend you check out my Tennis Tournament video, in which we use the same 'strategy', but might be easier to understand in that scenario.
This kind of problems are very easily to be solved by recursive equation. A more general question of this is called pattern match (e.g., the expected number of toss needed to see the first pattern HTTH), which can also be solved by solving recursive equations.
You are right, this problem belongs to a bigger class of problems, which can be solved following a similar method :D
this is so great. please make more like these
Glad to know you enjoy them!
Wow! So nice. I understand completely.
I'm really glad! :D
I had a question about when you set up the recursive equation. You had f(n) = 1/2(f(n-1) + 1) + 1/2(f(n-1) + 1 + f(n))
So the first part represents throwing the last H and game ends, and the last part represents throwing a T and starting over. So why is it f(n-1) + 1 + f(n) inside the bracket and not just f(n) + 1?
Because if you throw a T, you can just increase the overall expectation by 1 right? For e.g expected throws until a 6: E = 1/6(1) + 5/6(E+1), where you can just write E + 1 for the case when you don't throw a 6.
Thanks in advance. Love your interview question videos!
You are right, that is what those parts represent.
You also need to take into consideration that after you get a T, you start over (since the problem states that you are looking for consecutive heads). This gives you: f(n-1) + 1 up until now (similar to the first term) and f(n) starting from here, to reach the n consecutive heads.
love the video! subscribed
Thank you!
can we get more vids? i have an interview with two sigma soon lol
Hey Harry,
Happy to know that my content is useful and wishing you the best of luck in the upcoming interview.
I do have a video planned for release tomorrow, so make sure you hit the alarm bell to be notified when it's up.
While I'd like to be able to do more of them, they do take quite a lot of time (coding the vid, recording the audio, editing the audio, editing the final vid).
Great content!
Thank you!
I love your content
Thank you!
this looks like a Marco chain problem. when the equilibrium is reached
I would just throw in tha these kind of stochastic algorithms as presented at the end converge at the rate of sqrt of n. So If you have 1million toss simulations, expect maybe around a .001 accuracy
You are right about the rate of convergence. In this case, the bit with the simulations is not intended as proof and it's not formal in any way. The reason why that is included is more to be able to see some examples and to bring a more "practical" approach to the problem. Also, I hope at least, that including the code in the video is at least somewhat helpful for some people watching that want to check their results in other examples.
@@atypicalquant oops, I guess I mean 1/sqrt(n). Its still nice to see simulations.
Thanks a lot for this great content! I just didn’t get the last steps to get to the general form 2^(n+1)-2..
Hi and thank you for the comment!
In the last steps we do the following:
1) Replace f(1) with 2, thus 2^(n-1)*f(1)=2^(n-1)*2=2^n
2) Compute the bracket, which is the sum of a geometric progression (en.m.wikipedia.org/wiki/Geometric_progression). Using the formula from the page, for a=2, r=2, n=n-1, we get 2*(1-2^(n-1))/(1-2) =(2 - 2^(n))/(-1) = 2^n - 2
3) Summing them up, and taking into account that 2^n+2^n = 2* 2^n = 2^(n+1), we arrive at the final result, 2^(n+1) - 2
Hope this helps, let me know if it doesn't :)
@@atypicalquant all clear now! Many thanks 🙏
For the general case - how do we know that f(n) = w * f(n-1) + 2?
In the game reset branch we have the f(n) as well which here just disappears
my bad, I forgot to multiply with the probabilities of the branches
is there any reason we couldn't use the geometric distribution, define the first success as getting '3' heads, and then look at the expected value for a geometric distribution?
For a geometric distribution to work in this case we have to define the trial first, and then when such an experiment is a success or failure. To be able to consider "3 consecutive heads" as a succes means that our trial is tossing 3 times.
But, you can get 3 consecutive heads from 2 failures of this trial: (THH)(HTT). So a geometric distribution does not fit this problem. This is the only approach that I could think of that could include a geometric distribution, and it does not seem to work. Do you have another solution that can model the tosses as geometric trials?
@@atypicalquant I see, thanks heaps!
Hey, thanks for the video
Can you please suggest resources to practice such kind of questions except '50 challenging problems in probability' and xingfengxu's book.
Hey Aviral, have you checked the books that I recommend under "I." on my website (atypicalquant.net/quant-books/)?
@@atypicalquant thanks a lot
I havent seen them, taking a look now!!
Hello, I think that is no clear how did you derive the first equation of f(n) = 1/2(f(n-1) + 1) + 1/2(f(n-1) + 1 + f(n)) I think that you should replace f(n) by f(n-1) {f(n-1) = 1/2(f(n-1) + 1) + 1/2(f(n-1) + 1 + f(n)) } as you do for the first example with 3 Heads because the second knot is derived from the first one which is f(n-1) and not f(n).
I can see how this can be confusing. The initial point, the one in which you already have n-1 consecutive heads is not split into two cases, but extended with the next toss. Meaning that we are interested in the expected tosses for n. You can see how the equation you propose gets you that f(n)=-2, and that makes no sense in the context of tosses.
The differences between the case with 3 and the generalized proof is that for the former you start from the initial toss, but for the latter you start from n-1 tosses.
Hope this helps!
Nice video!
But you should explain the formula also. Didn't understand how you derived it.
Hi. Thanks for the message and for the feedback! It's quite hard to find the line between being too explicit (and thus boring) and being too concise (and sometimes overlooking simple explanations), especially on RUclips when the only thing you know about your audience is their age. What formula are you referring to?
@@atypicalquant Yes I understand. True, you can't be boring on YT. Formula I was referring was the one you put after the tree diagram.
Why did you not use a geometric distribution? A coin toss is a perfect bernoulli trial so it seems like this question is begging for a geometric distribution lol
Hey, as I also answered to a different comment:
While a coin toss is a perfect geometric distribution, the "succes" in our case is not getting a head, but getting 3 consecutive ones. So the desired Bernoulli trial is tossing a coin 3 times.
But, you can get 3 consecutive heads from 2 failures of this trial: (THH)(HTT). So a geometric distribution does not fit this problem. This is the only approach that I could think of that could include a geometric distribution, and it does not seem to work. Do you have another solution that can model the tosses as geometric trials?