How about a hard math problem for once?
March 22nd, 2022 at 10:15:05 AM
permalink
At the end of the annual MIT Math Contest's "Guts Round" is a set of problems where the participants are not expected to come up with an exact answer, but an estimate, with their score for that problem based on how close they are to the correct answer. (For this problem, an exact answer is worth 20 points, and an incorrect answer less than 40 away scores 20 - 1/2 of the difference between the submitted and correct answers.)
You have a uniformly random permutation of the integers from 1 to 100.
Two of the integers that are not in their correct positions (i.e. integer N is not the Nth number in the permutation) are selected randomly, and their positions swapped.
What is the expected number of swaps needed to get the numbers into increasing order from 1 to 100?
Simulation gets an answer somewhere around 2428
You have a uniformly random permutation of the integers from 1 to 100.
Two of the integers that are not in their correct positions (i.e. integer N is not the Nth number in the permutation) are selected randomly, and their positions swapped.
What is the expected number of swaps needed to get the numbers into increasing order from 1 to 100?
Simulation gets an answer somewhere around 2428
March 22nd, 2022 at 12:15:57 PM
permalink
Why not work on poker math that may help gamblers here? See below link.
https://wizardofvegas.com/forum/questions-and-answers/gambling/36944-math-of-ultimate-texas-holdem/#post843735
https://wizardofvegas.com/forum/questions-and-answers/gambling/36944-math-of-ultimate-texas-holdem/#post843735
March 22nd, 2022 at 3:21:16 PM
permalink
Love it. I can never come up with accurate answers to anything that requires more than basic arithmetic. But I can always reduce them to something where I can use basic arithmetic to make a good estimate.
It should be close to one-half of 1 + 2 + 3 + ... 100
This is because when we are trying to get the first number in place, it is like a 1% chance, which means we would expect 100 random guesses. Then once we found the correct position for one, it's more like a 1 in 99 chance, instead of 1 in 100. But each time we move one number, we are also credited with moving a second number, so cut it in half.
But that estimate is going to be high for a couple reasons I can think of. When the numbers are first placed randomly, we should expect one to be in its right place, so reduce the estimate down to 0.5(1 + 2 + 3 + ... 99) = 2475
(really it should be 1 + 1.5 + 2 + 2.5 + .... 49 + 49.5)
Also, each time we move a number we know it is in the wrong place. So instead of only being a 1 in 99 chance for that first number, it is actually a 1 in 98. Which roughly reduces the swaps for finding the first one by 98/99. It also reduces the amount of swaps to find the other numbers by even more than 98/99. I don't know how to easily change that fraction for the others, so I'll just multiply the 2475 by 98/99 to get 2450, then lower my guess a little bit. Final answer is 2437 because prime.
It should be close to one-half of 1 + 2 + 3 + ... 100
This is because when we are trying to get the first number in place, it is like a 1% chance, which means we would expect 100 random guesses. Then once we found the correct position for one, it's more like a 1 in 99 chance, instead of 1 in 100. But each time we move one number, we are also credited with moving a second number, so cut it in half.
But that estimate is going to be high for a couple reasons I can think of. When the numbers are first placed randomly, we should expect one to be in its right place, so reduce the estimate down to 0.5(1 + 2 + 3 + ... 99) = 2475
(really it should be 1 + 1.5 + 2 + 2.5 + .... 49 + 49.5)
Also, each time we move a number we know it is in the wrong place. So instead of only being a 1 in 99 chance for that first number, it is actually a 1 in 98. Which roughly reduces the swaps for finding the first one by 98/99. It also reduces the amount of swaps to find the other numbers by even more than 98/99. I don't know how to easily change that fraction for the others, so I'll just multiply the 2475 by 98/99 to get 2450, then lower my guess a little bit. Final answer is 2437 because prime.
March 23rd, 2022 at 7:50:34 AM
permalink
I read this math problem three times but still haven’t got the exact meaning of it.
March 23rd, 2022 at 9:28:20 AM
permalink
Quote: acesideI read this math problem three times but still haven’t got the exact meaning of it.
link to original post
I will describe it with 6 numbers instead of 100.
You start with a random permutation of {1, 2, 3, 4, 5, 6} - say, {4, 5, 2, 1, 3, 6}.
Randomly choose two numbers that are not in their correct positions, and swap them.
In the example, all of the numbers except 6 are in the wrong position, so choose two of them - say, 3 and 4 - and swap them.
The permutation is now {3, 5, 2, 1, 4, 6}.
Note that neither 3 nor 4 are in the correct positions; the only condition was that neither of the two numbers chosen were correct before the swap.
You could have chosen 2 and 5, resulting in 2 being moved to its correct spot but not 5; you could have also chosen 4 and 1, resulting in both being moved to their correct spots.
Keep doing this until you get {1, 2, 3, 4, 5, 6}.
What is the expected number of swaps needed, over all 720 possible starting permutations?
March 23rd, 2022 at 9:53:39 AM
permalink
Quote: ThatDonGuyQuote: acesideI read this math problem three times but still haven’t got the exact meaning of it.
link to original post
I will describe it with 6 numbers instead of 100.
You start with a random permutation of {1, 2, 3, 4, 5, 6} - say, {4, 5, 2, 1, 3, 6}.
Randomly choose two numbers that are not in their correct positions, and swap them.
In the example, all of the numbers except 6 are in the wrong position, so choose two of them - say, 3 and 4 - and swap them.
The permutation is now {3, 5, 2, 1, 4, 6}.
Note that neither 3 nor 4 are in the correct positions; the only condition was that neither of the two numbers chosen were correct before the swap.
You could have chosen 2 and 5, resulting in 2 being moved to its correct spot but not 5; you could have also chosen 4 and 1, resulting in both being moved to their correct spots.
Keep doing this until you get {1, 2, 3, 4, 5, 6}.
What is the expected number of swaps needed, over all 720 possible starting permutations?
link to original post
Your explanation is very clear to me. I think we can modify this problem a little to make it practically useful. When we choose a swap, we always choose such a swap that at least one correct position can be reached after the swap.
March 23rd, 2022 at 10:11:46 AM
permalink
Quote: acesideQuote: ThatDonGuyQuote: acesideI read this math problem three times but still haven’t got the exact meaning of it.
link to original post
I will describe it with 6 numbers instead of 100.
You start with a random permutation of {1, 2, 3, 4, 5, 6} - say, {4, 5, 2, 1, 3, 6}.
Randomly choose two numbers that are not in their correct positions, and swap them.
In the example, all of the numbers except 6 are in the wrong position, so choose two of them - say, 3 and 4 - and swap them.
The permutation is now {3, 5, 2, 1, 4, 6}.
Note that neither 3 nor 4 are in the correct positions; the only condition was that neither of the two numbers chosen were correct before the swap.
You could have chosen 2 and 5, resulting in 2 being moved to its correct spot but not 5; you could have also chosen 4 and 1, resulting in both being moved to their correct spots.
Keep doing this until you get {1, 2, 3, 4, 5, 6}.
What is the expected number of swaps needed, over all 720 possible starting permutations?
link to original post
Your explanation is very clear to me. I think we can modify this problem a little to make it practically useful. When we choose a swap, we always choose such a swap that at least one correct position can be reached after the swap.
link to original post
You don't get to choose the swaps; the numbers are selected randomly. The only condition is, neither of the numbers that are selected can be in their correct position.
March 23rd, 2022 at 11:20:23 AM
permalink
I like this problem (expected number of trials is one of my favorite genres) but I haven't come up with a solution or estimate.
One approach is to start from a fully deranged string since we know there is very close to a 1/e =~36.79% chance of starting there. Then there are c(100,2) ways to choose two positions, of which there is only 1 way that two numbers will get to their correct positions, 98*2 ways that one number will get into its proper position, and the remainder of ways will keep the string in a fully deranged state. I believe you could work out the probabilities of starting with 99, 98, 97, 96, 95, etc deranged items starting from fully deranged, and that the vast majority of starting points would be in that very upper range. From there a markov chain could be used to get to an answer. I generally see a markov chain as a last resort before a simulation but so far a formulaic solution eludes me. It could exist though, just like the 1/e estimate exists for a fully deranged string (inclusion-exclusion gets to 1/e)
One approach is to start from a fully deranged string since we know there is very close to a 1/e =~36.79% chance of starting there. Then there are c(100,2) ways to choose two positions, of which there is only 1 way that two numbers will get to their correct positions, 98*2 ways that one number will get into its proper position, and the remainder of ways will keep the string in a fully deranged state. I believe you could work out the probabilities of starting with 99, 98, 97, 96, 95, etc deranged items starting from fully deranged, and that the vast majority of starting points would be in that very upper range. From there a markov chain could be used to get to an answer. I generally see a markov chain as a last resort before a simulation but so far a formulaic solution eludes me. It could exist though, just like the 1/e estimate exists for a fully deranged string (inclusion-exclusion gets to 1/e)
Last edited by: Ace2 on Mar 23, 2022
It’s all about making that GTA
March 23rd, 2022 at 2:38:09 PM
permalink
This is my idea of approaching it using recursion.
With two numbers to go (say AB) then they can only be arranged BA (otherwise there would be no numbers to go. You're bound to swap them correctly. so f(2)=1 turn.
With three number (ABC) they can't be BAC as that would be two correct, so they're something like BCA. Whichever pair you swap one will land up correctly and you'll have two to go (BC=B, BA=A, CA=C). So f(3)=1+f(2).
I think you continue this except with four or more you could get two correct (e.g. BADCFE), the problem is the number of permutations starts to grow and not all of the swaps result in any more correct.
I hazard a guess as N gets larger that f(N) tends to (N-1)/2, e.g. with 100 wrong you pick one at random, then the chances of moving it to the correct position is 1/99. There's a similar chance, even if the first one is being moved incorrectly, the one you swap is being moved to the correct place. So on average there's 2/99 of reducing it by one and a small chance of reducing it by two. The first gives the 2450 estimate and you reduce it a bit to cater for any double hits.
With three number (ABC) they can't be BAC as that would be two correct, so they're something like BCA. Whichever pair you swap one will land up correctly and you'll have two to go (BC=B, BA=A, CA=C). So f(3)=1+f(2).
I think you continue this except with four or more you could get two correct (e.g. BADCFE), the problem is the number of permutations starts to grow and not all of the swaps result in any more correct.
I hazard a guess as N gets larger that f(N) tends to (N-1)/2, e.g. with 100 wrong you pick one at random, then the chances of moving it to the correct position is 1/99. There's a similar chance, even if the first one is being moved incorrectly, the one you swap is being moved to the correct place. So on average there's 2/99 of reducing it by one and a small chance of reducing it by two. The first gives the 2450 estimate and you reduce it a bit to cater for any double hits.
