HSC 2016 MX2 Combinatorics Marathon (archive) (2 Viewers)

Status
Not open for further replies.

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Re: HSC 2016 MX2 Combinatorics Marathon

Yep :). Want to justify this for everyone else's sake?

You might also find it fun to think about what happens if the coin is biased and has heads probability p in (0,1).
(Idk if it still works out nicely and won't have time to check until after uni tomorrow but I feel like it should.)
 

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
Re: HSC 2016 MX2 Combinatorics Marathon

Yep :). Want to justify this for everyone else's sake?

You might also find it fun to think about what happens if the coin is biased and has heads probability p in (0,1).
(Idk if it still works out nicely and won't have time to check until after uni tomorrow.)
Eh, it's the sum of a double series, which I could do myself but right now, too many distractions...

As for the generalised weighted probability, I wouldn't bet on a nice form, but I'm feeling hopeful.
 

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

Yep :). Want to justify this for everyone else's sake?

You might also find it fun to think about what happens if the coin is biased and has heads probability p in (0,1).
(Idk if it still works out nicely and won't have time to check until after uni tomorrow but I feel like it should.)
I think it does; I think glittergal96 (lol) asked a similar Q before, about expected no. of tosses required to get k heads in a row for a weighted coin. This Q. is basically same as that because here the profit is just equal to the no. of tosses required.
 

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

A somewhat related Q (which I'm not sure if there is a nice answer to):

Let K be a predetermined positive integer. Let the coin have probability p in (0, 1) of landing heads on a given toss. Let X be the no. of tosses required to first obtain K heads in a row. For each integer jK, find Pr(X = j) (assuming the tosses are independent). (Obviously this probability is 0 whenever j < K, because we need at least K tosses to get a string of K consecutive heads.)
 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Re: HSC 2016 MX2 Combinatorics Marathon

I think it does; I think glittergal96 (lol) asked a similar Q before, about expected no. of tosses required to get k heads in a row for a weighted coin. This Q. is basically same as that because here the profit is just equal to the no. of tosses required.
This question is exactly the same, which is why I re-asked it :p. It had been a while so new people might not have seen it.

Also it was previously phrased in the unweighted case, I still have the solution I tex'd.

The method looks like it will carry over fine unless I am missing something, the series might just be slightly messier. Anyway, I have to finish some marking (a probability course incidentally) and prep some stuff for my supervisor meeing so I won't go through the details of the weighted problem till tomorrow evening.
 

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

This question is exactly the same, which is why I re-asked it :p. It had been a while so new people might not have seen it.

Also it was previously phrased in the unweighted case, I still have the solution I tex'd.

The method looks like it will carry over fine unless I am missing something, the series might just be slightly messier. Anyway, I have to finish some marking (a probability course incidentally) and prep some stuff for my supervisor meeing so I won't go through the details of the weighted problem till tomorrow evening.
The one glittergal96 asked was with probability p for the coin iirc. The one you're referring to is from a few years ago (OK, I think it was from 2 years ago, after checking through some threads) I think, the one by glittergal96 was more recent, I think it's on this very thread. I think it was about finding the expected no. of tosses to get K heads in a row, from memory. (I think it can be done without needing a hard series.)
 
Last edited:

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Re: HSC 2016 MX2 Combinatorics Marathon

Will also have a crack at your related Q (finding the PDF of the sequence lengths, rather than just the expectation of the lengths.)

I remember you asking that before and me being stumped (because my solution to the expectation problem exploited self-similarity to solve for the expectation without having to compute a PDF and sum a presumably gory series.)
 

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

Will also have a crack at your related Q (finding the PDF of the sequence lengths, rather than just the expectation of the lengths.)

I remember you asking that before and me being stumped (because my solution to the expectation problem exploited self-similarity to solve for the expectation without having to compute a PDF and sum a presumably gory series.)
Yes this one looks like it'd probably be much nicer done without having to sum a series. And I haven't thought about the pmf problem since that time lol. Maybe I'll try it again later.
 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Re: HSC 2016 MX2 Combinatorics Marathon

The one glittergal96 asked was with probability p for the coin iirc. The one you're referring to is from a few years ago (OK, I think it was from 2 years ago, after checking through some threads) I think, the one by glittergal96 was more recent, I think it's on this very thread. I think it was about finding the expected no. of tosses to get K heads in a row, from memory. (I think it can be done without needing a hard series.)
Ah nice yeah, I forgot that you posted that solution here :).
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
Re: HSC 2016 MX2 Combinatorics Marathon

Yep :). Want to justify this for everyone else's sake?

You might also find it fun to think about what happens if the coin is biased and has heads probability p in (0,1).
(Idk if it still works out nicely and won't have time to check until after uni tomorrow but I feel like it should.)
I'll do it for the weighted probability since you can just sub in p=1/2.

Let the expected number of tosses before gaining 'n' tails be E(n). Then we can make the following recurrence relation:



Basically we have E(n-1), then we throw either an n'th tail with probability 1-p, or we throw a head which then brings us back to square one.

Solving the recurrence relation we get:



We can solve this to get:



Now letting k=n we arrive at:



But we have that

So:



Now summing this GP will give you the answer (a bit cbf atm to do this lol).
 
Last edited:

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

Ah nice yeah, I forgot that you posted that solution here :).
What was the method you used? The same as the one you posted on the thread where you asked this Q before (in the unweighted case)?
 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Re: HSC 2016 MX2 Combinatorics Marathon

What was the method you used? The same as the one you posted on the thread where you asked this Q before (in the unweighted case)?
Yep. :). The ideas in both proofs are very similar though, even if superficially they look a bit different.
 

braintic

Well-Known Member
Joined
Jan 20, 2011
Messages
2,137
Gender
Undisclosed
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

Back to an Ext 2 level question:



 
Last edited:

braintic

Well-Known Member
Joined
Jan 20, 2011
Messages
2,137
Gender
Undisclosed
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

Since nobody seems to want to answer my previous question, a spin on the Monty Hall problem:

This game is played with 5 doors.
After you make your initial choice the host opens a door that doesn't have the car, then gives you the option to switch to one of the other unopened doors.
After you make your decision he opens another door that doesn't have the car (possibly your initial choice of door if you made the switch), then gives you the same choice of stay or switch.
This process is repeated once more so that your final choice is between two doors.

As you made three binary choices, there are 2^3 = 8 combinations of stay/switch.
Which of those 8 options maximises your chance of winning the car?

Note: The explanation might include a comment such as "if the host opens this door", but the final answer should not depend on the host's choices. In other words, the best option is predetermined.
 

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

Since nobody seems to want to answer my previous question, a spin on the Monty Hall problem:

This game is played with 5 doors.
After you make your initial choice the host opens a door that doesn't have the car, then gives you the option to switch to one of the other unopened doors.
After you make your decision he opens another door that doesn't have the car (possibly your initial choice of door if you made the switch), then gives you the same choice of stay or switch.
This process is repeated once more so that your final choice is between two doors.

As you made three binary choices, there are 2^3 = 8 combinations of stay/switch.
Which of those 8 options maximises your chance of winning the car?

Note: The explanation might include a comment such as "if the host opens this door", but the final answer should not depend on the host's choices. In other words, the best option is predetermined.
Monty knows what is behind each door, right?
 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Re: HSC 2016 MX2 Combinatorics Marathon

Cool question! Did you think of it yourself braintic?

Let's play this game with n doors.

I believe the optimal strategy is to refuse to switch until the final offer, and switch then. This guarantees you a (n-1)/n chance of success. (It fails if and only if your original choice was the correct door).

Sketch of proof of optimality:

We can consider the "value of a door" to be the expectation of the random variable that is 1 if this door is correct and 0 if it isn't. (Well, the conditional expectation, given the information that Monty successively gives us).

Each time Monty opens a door, he increases the value of all remaining unopened doors (excluding your current choice, because him opening a door gives you no information about your door!) And he also gives the now-open door a value of zero.

The way the value of these unopened doors increases is they scale by the same factor. (I.e they remain in the same proportion, they just "fill up" the value that that the removal of a door vacates).

This can be used to show that at every step, each unopened door has value >= 1/n, regardless of our choices. (Value of an unopened door never decreases).

This means on the last step, when we decide whether to reject a door or not, the minimum value we will be throwing away must be at least 1/n.

As we have shown we can indeed arrange this, (by never changing door beforehand), we are done.

Intuition behind this: Each time Monty opens a door he is telling us more about the unopened doors and making them more valuable. By never changing beforehand, there is the greatest differential in value between doors at the end.
 
Last edited:

braintic

Well-Known Member
Joined
Jan 20, 2011
Messages
2,137
Gender
Undisclosed
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

Alas I did not. I found the 4 door version in a book, but decided to make it one step larger.

Yes you are correct. This example appears early in the book, and they say that it will be solved later using the law of total probability. I am not sure how to apply that here.
It would be good to see a generalized numerical analysis.

To answer Integrand's question, yes that's what I intended when I said that the host opens a door without a car - though I realise that can be interpreted as just a fluke.


Another version of the problem ... which I got from the Harvard lectures that Integrand linked me to :

Three door problem - but this time when the host has two doors to choose from, he is biased towards one selection. Let's say he picks the leftmost of the two remaining doors with probability p. Furthermore, you know which door he favours.

This time your probabilities of winning by switching are affected by which door the host opens.
Find formulae in terms of p for the probability he wins based on which door the host opens.
Explain what happens in the case when p = 0 or 1.
And find the expected number of wins per game by switching (in the variable p case).


BTW Integrand, that Harvard lecturer is really good - once you get over his non-stop stammering. I occasionally think I am listening to an 80s rap group - and oh how I hate (c)rap.
 
Last edited:

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
Re: HSC 2016 MX2 Combinatorics Marathon

Alas I did not. I found the 4 door version in a book, but decided to make it one step larger.

Yes you are correct. This example appears early in the book, and they say that it will be solved later using the law of total probability. I am not sure how to apply that here.
It would be good to see a generalized numerical analysis.

To answer Integrand's question, yes that's what I intended when I said that the host opens a door without a car - though I realise that can be interpreted as just a fluke.


Another version of the problem ... which I got from the Harvard lectures that Integrand linked me to :

Three door problem - but this time when the host has two doors to choose from, he is biased towards one selection. Let's say he picks the leftmost of the two remaining doors with probability p. Furthermore, you know which door he favours.

This time your probabilities of winning by switching are affected by which door the host opens.
Find formulae in terms of p for the probability he wins based on which door the host opens.
Explain what happens in the case when p = 0 or 1.
And find the expected number of wins per game by switching (in the variable p case).


BTW Integrand, that Harvard lecturer is really good - once you get over his non-stop stammering. I occasionally think I am listening to an 80s rap group - and oh how I hate (c)rap.
Hmm... I'd like to see an analysis of the general case with n doors and every door with a unique weighted probability...
 

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

BTW Integrand, that Harvard lecturer is really good - once you get over his non-stop stammering. I occasionally think I am listening to an 80s rap group - and oh how I hate (c)rap.
Yeah, and (unrelated) he also happens to be a really good chess player I think. Also there's a lot of Monty Hall variants out there, with amusing names like 'Monty Fall' and 'Monty Crawl'.
 

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
Status
Not open for further replies.

Users Who Are Viewing This Thread (Users: 0, Guests: 2)

Top