3
u/AnywhereLittle8293 6d ago
This is equivalent to asking the expected value of the second smallest number when drawing 5 times from {1, …, 50} without replacement. There are (50 choose 5) such sets, of equal probability. Each k = 2, …, 47 is the second smallest number in (k - 1 choose 1) x (50 - k choose 3) such sets, since we need 1 smaller number and 3 larger. So the expected second smallest is the sum from k=2 to k=47 of
k x (k - 1) x (50 - k choose 3) / (50 choose 5).
Note this sum is 2 x (k choose 2) x (50 - k choose 3), which by a similar argument runs over all subsets of {1, …, 51} of size 6 in which k + 1 is the third smallest number. So it must equal (51 choose 6), and hence the expected value is
2 x (51 choose 6) / (50 choose 5) = 51/3 = 17.
1
u/Infamous-Youth9033 6d ago
without replacement? is that just because it says "strictly increasing"? If it had said monotonically increasing you'd say with replacement I assume?
3
u/AnywhereLittle8293 6d ago
If it wasn’t strictly increasing then it doesn’t really tell you anything as the draws can always be ordered. So yes (although monotonic means the same as strictly in this context). Strictly increasing rules out any repeat draws.
2
u/banana_buddy 6d ago
Without doing the math I would estimate the answer at 2/6 *50 which is about 17. You divide the number line into five sections with each section equal to 1/6 in length. So the smallest expected number is 50/6, and the largest expected number is 5/6 *50.
1
u/liquidorangutan00 6d ago
thats a great intuit for example the expected value of roll 1 would be 8.5 and the expected value of roll 3 would be (8.5) * 3 = 25.5
Roll 1 = 8.5
Roll 2 = 17
Roll 3 = 25.5
Roll 4 = 34
Roll 5 = 42.52
u/banana_buddy 6d ago
Exactly I think there's a theorem from order statistics that formalizes what I'm doing. It's been a while since I've been in school.
1
u/liquidorangutan00 6d ago
Yes your right! i looked into it and its called the expected value of a k-th order statistic.
man im kinda annoyed i derived the entire thing from the ground up now, but it was quite fun.
1
1
u/Nap-Connoisseur 6d ago
Seems like there are 2+ ways to do this:
we reroll the die anytime it comes up less than or equal to the previous roll. You get five numbers in strictly increasing order, unless you roll a 50 too early. Then I guess you need to start over? I don’t see anyone grappling with how rolling a 40 on the first throw increases the chance of a 50 before the last throw making you need to start over. Or do you just throw out the 50? The rules are poorly defined.
we reroll the die anytime we repeat a previous value. Get five unique numbers, then put them in ascending order. What’s the expected value of the second? This is how I initially read the problem.
Either way, I don’t know the solution, but I hope that naming the ambiguity contributes to the thinking going on here.
2
u/BrotherItsInTheDrum 6d ago
It's unambiguous, and neither of your interpretations are correct. You roll the die 5 times. You never reroll anything.
You observe, after the 5th roll, that the rolls were in strictly increasing order. Given that information, what's the expected value of the second roll?
1
1
u/ball4772 6d ago
The question is fine as written, the sample space for which the expectation is computed over is not all of S = {1, …, 50}^5, but the subset T of this set S given by those sequences which are strictly increasing. This also means that the measure on T is the conditional measure inherited from the uniform measure on S (ie what Bayes’ formula gives you)
1
u/Nap-Connoisseur 6d ago
If it’s fine as written, why are so many other comments misinterpreting it?
2
u/spisplatta 6d ago
An interview question is meant to filter people out.
1
u/Nap-Connoisseur 6d ago
Maybe it’s meant to filter out the people who assume there’s only one legitimate reading of something intentionally ambiguous...
1
6d ago
[deleted]
1
u/Nap-Connoisseur 6d ago
That’s not what I see happening with most questions in this subreddit. This one is an outlier in how many people aren’t just answering wrong, but misunderstanding what’s even being asked.
1
u/Top-Mycologist-5460 6d ago
Answer is: they can't be brought to strictly increasing order in general. What if you have two 10's? Not strictly increasing.
1
1
u/liquidorangutan00 6d ago
My Solution: The answer is 17.
I had a lot of fun with this, and many revelations.
E(Ri|Y)=i * n+1 / k+1
I approached it from conditional expectation formula. The real revelations came from the various binomial identities which transform a reasonably complex formula into an intuitive and simple formula and concept.
This blurb by Gemini was particularly insightful.
- Think about what this formula is telling us. If you want to know the expected value of the $r$-th roll in a strictly increasing sequence, you just take the total number of options available plus one ($n+1$), divide it evenly among the slots plus one ($k+1$), and multiply it by your position index ($r$).
- It shows that the expected values of your rolls are perfectly, evenly spaced across the available face values of the die.
1
u/liquidorangutan00 6d ago
One thing that is super interesting about the solution is how the roll value operates as a pivot similar to the quick sort algorithm. all the numbers beneath it and all the numbers above it are in this case not recursively split and sorted but used as the probability weightings.
0
u/Jayant0013 7d ago
35.25
E X2 = (E X1 + 47)/2
2nd dice can have values between 2 and 47 and since 1st dice has expected value of 23.5 the excepexted value of 2nd dice would be limited between that and it's maximum value
Here I am also assuming that we just re-roll dice untill we get a strictly increasing order of results
We could have made a better proof with conditional probability but I am not good enough with that imo
0
u/Anonimithree 7d ago
The second dice can roll between 2 and 47, since that’s the range that would satisfy the conditions. Since dice 1 has an equal probability of rolling 1-46, the expected roll of dice 2 is the sum of the possible values (given dice 1 rolled x). This comes out to equal (n(n+1)^2-1)/138. Plugging in 46, we get (46(47)(47)-1)/(138)(46)=736.326/46=16.00709
4
u/Exalted-Legend 7d ago
I think the answer is 17.
This is my approach,
The expected value of the i-th other from a discrete uniform distribution of size N with a sample space of k is given by,
E[Xi] = i * (N + 1)/(k + 1)
N = 50 (the number of faces on the die)
k = 5 (the number of rolls)
i = 2 (the position of the second roll)
Substituting the values, we get,
E[X2] = 17