1) Since pi is an irrational number, and moreover a transcendental number, then its decimal expansion is pretty much "random", so in principle any finite series of digits ought to appear somewhere in it.
There are transcendental numbers that do not even have some digit appearing at all. There exists decimal (base-10) transcendental number consisting entirely of zeros and ones.
There also are transcendental numbers that have all the base-10 digits in decimal, but don't even have all 100 pairs of consecutive digits appear.
It is not known if different digits in decimal expansion of pi all have probability of 10%, or not.
A similar question is 'Is pi a Normal number ?'
Here is an interesting quote:
"Determining if numbers are normal is an unresolved problem. It is not even known if fundamental mathematical constants such as pi (Wagon 1985, Bailey and Crandall 2003), the natural logarithm of 2 ln2 (Bailey and Crandall 2003), Apéry's constant zeta(3) (Bailey and Crandall 2003), Pythagoras's constant sqrt(2) (Bailey and Crandall 2003), and e are normal, although the first 30 million digits of pi are very uniformly distributed (Bailey 1988)."
Though one could imagine a non-normal number that does have every possible series of digits within it. For example, concatenating the digits of every number one after the other, and doing it twice if it contains only 1s, is a non-normal number containing every possible series of digits.
However, I would expect every 'non-constructed, transcendental' normal number to also contain all subsequences in it.
For example, concatenating the digits of every number one after the other
This is known as the Champernowne constant. It is one of the few numbers known to be normal (it's practically defined to be so). It is also, in a sense, extremely unrandom (although even that is debatable).
Patashu wrote:
and doing it twice if it contains only 1s
I'm confused about this condition. What does it mean, and does it serve some purpose? Is there some exception that needs to be taken into account?
* * *
If you're bored, use a program that can perform long division to arbitrary precision (200+ digits; I recommend Mathematica, although I also wrote a Matlab program to do the same. Or just use this website.) and enter the following:
60499999499/490050000000
What is the result? Why can it be expressed so accurately in such a short and alluringly elegant rational quotient? (Honestly, I don't entirely know, but I studied it enough to get a few hints.)
To get back to Warp's original question: if Pi is indeed a Normal Number (which is yet unproven), then yes, it will contain every finite sequence you can think of.
Granted, for any sequence of a million digits, the chance for them to be all zeros is 1 / ( 10 ^ 1.000.000 ), a very very small number.
For example, if you were to pick a random spot (of planck length) in the observable universe, at a random moment (of planck time) since the big bang, then your chance of picking exactly the time and place of the first neuron firing inside baby Einstein's brain[1] is merely around 1 / ( 10 ^ 250).
So if you pick a truly random sequence of a million digits, it's very likely that there has never been, and will never be, a physical representation of said sequence in our universe.[2]
But Pi is different. Its decimal expansion is infinite. So we need to take a look at an estimated 10 ^ 1.000.000 subsequences of Pi until we find one that matches? How many subsequences are there in Pi? Infinitely many, which is not only enough to find one match with probability 1, but an infinite amount of matches.
[1] or baby hitler's brain, if you prefer. Or any other point in our spacetime.
[2] well, unless you pick a sequence by writing it down or storing it in your computer's memory. Sampling bias, hu?
A few hours ago, TASeditor uploaded the following video demonstrating an example of a linear-feedback shift register (LFSR): https://en.wikipedia.org/wiki/Linear_feedback_shift_registerLink to video
As the Wikipedia article shows for the 4-bit (nibble) case of this register (which actually can make sense for as few as two bits), the two cycles are the fixed point (0000:0) and a cycle of length 15 containing all of the other nibbles; after watching that video, I decided to figure out what the cycles were for the 8-bit (byte) case. I went ahead and did it manually and the results are below:
The six cycles are indexed by the smallest possible seeds, although it might not be the most illuminating way to look at the bit-patterns; I've also considered coloring a 16x16 grid to show how these five cycles are related, possibly to see what special properties the members of the last cycle (109, 182, and 219) share.
Here are the cycles for some cases below 8 bits...
2-bit: 00:0, 01:1 - 10:2 - 11:3
3-bit: 000:0, 001:1 - 100:4 - 010:2 - 101:5 - 110:6 - 111:7 - 011:3
4-bit: 0000:0:0, 0001:1:1 - 1000:8:8 - 0100:4:4 - 0010:2:2 - 1001:9:9 - 1100:C:12 - 0110:6:6 - 1011:B:11 - 0101:5:5 - 1010:A:10 - 1101:D:13 - 1110:E:14 - 1111:F:15 - 0111:7:7 - 0011:3:3
5-bit...
In the first three cases, the partitioning into cycles is trivial: "Cycle 0" of length 1, and "Cycle 1" of length 2n-1-1 for n-bit words.
It turns out the 6- and 7-bit cases also follow this pattern, but I won't type them all out here.
The challenge is to describe the set of cycles of this LFSR as the number of bits increases; based on reading that Wikipedia article, I suspect it has to do with the factorization of xn+xn-1+1, and I've seen from Wolfram Alpha that this polynomial is reducible over the Reals (and therefore over GF(2)) when n is 5, 8, 11, or 14, and additionally is reducible over GF(2) (but not the Reals) when n is 10, 12, 13 or 16.
As a side-note, this means that the LFSR demonstrated in the video is a poor one for retro games; the ideal case would have the trivial cycle and a cycle of length 25, based on the polynomial x8+x6+x5+x4+1 (that is, by using XOR on the least significant bit, the third least significant, and the two to the left of that).
I'm surprised this thread has been going as long as it has. Also Pi being a normal number would be interesting... If I recall Numberphile had a video on it a while back.
Projects:
Interested in TASing N64 Mario Golf.
GBA Mario Tennis: Power Tour is on hold.
I started thinking: A 4x4x4 rubik's cube can be used to "emulate" both a 2x2x2 cube and a 3x3x3 cube. (If, from the solved state, you only rotate halves of the cube, it will effectively work as a 2x2x2, and if you only rotate the outer slices, it will effectively work as a 3x3x3.)
On the other hand, a 3x3x3 cannot be used to emulate a 2x2x2 (unless you completely ignore the center slices, ie. don't care that they may end up scrambled, and only care about the corner pieces, but I'm not counting that as valid). Also, you can use a 5x5x5 to emulate a 3x3x3 but not a 4x4x4 nor a 2x2x2.
This got me thinking: What's the general formula for which smaller-sized cubes can be emulated using an nxnxn-sized cube?
At first one would think that this might have something to do with divisors, but it's not that simple. One of the major and most obvious reasons for this is that any cube larger than 3x3x3 can be used to emulate a 3x3x3 (when you rotate only the outer slices.) Thus the answer is not that trivial.
So we have a cube with N columns, trying to simulate one with n columns. For N=4, we use grouping G={2,2} to simulate n=2, and G={1,2,1} to simulate n=3, with obviously G={1,1,1,1} being the default N=n=4; Where |G|=n. Clearly this is just ways to split up our integer N into different sized sets, subject to certain conditions we hope to derive along the way.
For example, we cannot use 4={1,1,2} as an emulator for n=3, because on the left side we have a face by itself, but we on the right we have the face paired off with an edge section. This means that when solving it, it'll eventually be split up. EG the two (Face, Direction) rotations: (Bottom, Left), (Left Up) would separate part of the 2x2 simulated cube initially in the bottom right corner. This is because of the lack of symmetry in the {1,1,2} expression. IE if we have tiles 'a' and 'b' in the 3rd emulated set (--,--,ab), after a rotation we have (a,b,--), which will then be separated upon moving either column. So we need each tile to be paired with just as many pieces on one side as the other, thus our given emulator distribution MUST be symmetrical.
For all N>3, we we have N={1,(n-2),1}, which is of course symmetrical and has magnitude 3, thus an n=3 cube can always be emulated for any N. For N=5, we also have G={1,3,1}={2,1,2} for n=3 emulation. We cannot have n=2, because we have 5 columns to pair off to our 2 emulated sides. Since we cannot split this evenly, it is not possible. Now in terms of symmetry, it depends on if we have an odd or even number of columns, thus if we have a central column or not.
IE for n odd, we need its central column to be emulated, done differently depending on if N is odd or even. If N is even, we can do this by having equal amounts of columns adjacent to the central divide as being treated as a single block. EG {1,2,1} gives us an emulated central column, so n=3 can be done inside N=4. Note here that the size of that central column (2) is even, but if we have N odd, then the central column in N does not get split up, but instead needs to be bunched with equal amounts of columns on both sides, thus we would have the size of the middle string being odd. EG for n=3 inside N=5, gives G={1,3,1}={2,1,2}, where both middle columns have odd numbers. Hence we have a solution for N odd. Either way, n odd can be emulated in both N even and N odd.
But for n even, we need to split the columns of N into an even amount, one which is clearly impossible if N is odd, thus N also needs to be even. Thus N odd can emulate only n odd, N even can emulate n both odd or even. This is true for All N>n, for example:
N=4. {1,1,1,1}, {1,2,1}, {2,2}.
N=5. {1,1,1,1,1}, {1,3,1}={2,1,2}.
N=6. {1,1,1,1,1,1}, {1,1,2,1,1}, {1,2,2,1}={2,1,1,2}, {1,4,1}={2,2,2}. {3,3}.
N=7. {1,1,1,1,1,1,1}, {1,1,3,1,1}, {1,5,1}={2,3,2}={3,1,3}.
N=8. {1,1,1,1,1,1,1,1}, {1,1,1,2,1,1,1}, {1,1,2,2,1,1}={1,2,1,1,2,1}={2,1,1,1,1,2}, {1,1,4,1,1}={1,2,2,2,1}={2,1,2,1,2}, {1,3,3,1}={3,1,1,3}={2,2,2,2}, {1,6,1}={2,4,2}={3,2,3}, {4,4}.
So Odd cubes can only emulate smaller odd cubes. Even cubes can emulate all smaller cubes. Basically because the emulation will take the symmetric form of either G={---k---,---k'---} or G={--k--,m,--k'--}; thus giving total group size=emulator size of the form a+a=2a=even, or a+b+a=2a+b which can be made even or odd.
The challenge is to describe the set of cycles of this LFSR as the number of bits increases; based on reading that Wikipedia article, I suspect it has to do with the factorization of xn+xn-1+1, and I've seen from Wolfram Alpha that this polynomial is reducible over the Reals (and therefore over GF(2)) when n is 5, 8, 11, or 14, and additionally is reducible over GF(2) (but not the Reals) when n is 10, 12, 13 or 16.
It has to do partially with the factorization of xn+xn-1+1 (mod 2) (or equivalently, factorization of the reverse xn+x+1 (mod 2)), but it is more complex than just factorization. I can't explain everything in complete detail, but this is how it goes (everything below is in mod 2 land):
- Every LFSR is equivalent to a Galois LFSR. Example for x16+x14+x13+x11+1 (credit Wikipedia):
- The internal state of the Galois LFSR above (lower image) can be represented by the polynomial given by sum(ith bit is 1) xi, where the leftmost bit is bit 0 and bit position counts left to right. Example above: 1+x2+x4+x5+x8+x9+x10+x15.
- Cycling the Galois LFSR is as simple as multiplying the polynomial internal state by x and taking the remainder upon division by the reverse of the LFSR's polynomial 1+x2+x3+x5+x16.
- Let f(x) be the reverse of the LFSR's polynomial and p(x) be the initial Galois LFSR state. Then the question is: what is the smallest positive n such that f(x) divides p(x)(xn-1)?
- Factor f(x) into irreducible factors f1(x)f2(x)...fk(x). Then for each irreducible factor that does not divide p(x), the question is: what is the smallest positive ni such that fi(x) divides xni-1?. If f(x) itself is irreducible, then it cannot divide p(x) (since deg f > deg p) unless p(x) is the zero polynomial.
- Even if f(x) is irreducible, that doesn't necessarily mean that the LFSR has period 2deg f-1 (the maximum) for nonzero initial values. In order for that to happen, the smallest positive n for which f(x) divides xn-1 must be 2deg f-1. In this case, f(x) is a primitive polynomial (field theory definition of primitive, not gcd definition).
- Note that every polynomial with nonzero constant term is a divisor of xn-1 for some n. In particular, an irreducible polynomial g(x), other than x, is a divisor of x^(2deg g-1)-1. This follows from field theory but I won't go into it here.
At this point, it is easier just to do small examples. The polynomials of interest are the reversals of xn+xn-1+1, that is, xn+x+1.
n=5:
x5+x+1=(x2+x+1)(x3+x2+1).
Note that both x2+x+1 and x3+x2+1 are primitive polynomials.
Let p(x) be the polynomial for the initial Galois LFSR state. Let g(p(x))=(u(x),v(x)) where u(x) is remainder of p(x) divided by x2+x+1 and v(x) is remainder of p(x) divided by x3+x2+1 (this is unique by the Chinese Remainder Theorem).
If g(p(x))=(0,0) (p(x) is the zero polynomial), then the cycle has length 1.
If g(p(x))=(u(x),0) for nonzero u(x), then the cycle has length 22-1=3 (since x3+x2+1 divides p(x), its only contribution is from x2+x+1)
If g(p(x))=(0,v(x)) for nonzero v(x), then the cycle has length 23-1=7.
If g(p(x))=(u(x),v(x)) for nonzero u(x) and v(x), then the cycle has length gcd(3,7)=21; this covers all possible values as well.
n=8:
x8+x+1=(x2+x+1)(x6+x5+x3+x2+1).
Note that both x2+x+1 and x6+x5+x3+x2+1 are primitive polynomials.
Let p(x) be the polynomial for the initial Galois LFSR state. Let g(p(x))=(u(x),v(x)) where u(x) is remainder of p(x) divided by x2+x+1 and v(x) is remainder of p(x) divided by x6+x5+x3+x2+1.
If g(p(x))=(0,0) (p(x) is the zero polynomial), then the cycle has length 1.
If g(p(x))=(u(x),0) for nonzero u(x), then the cycle has length 22-1=3.
If g(p(x))=(0,v(x)) for nonzero v(x), then the cycle has length 26-1=63.
If g(p(x))=(u(x),v(x)) for nonzero u(x) and v(x), then the cycle has length gcd(3,63)=63. For a given v(x), there are 3 possible values for u(x) in order to cover all possible values; thus, this gives 3 classes of length 63, for a total of 4.
n=9:
x9+x+1 is irreducible.
Now since the smallest positive n such that x9+x+1 divides xn-1 is n=73 (instead of n=29-1=511), x9+x+1 is not primitive. In fact, if p(x) is the initial Galois LFSR state, and p(x) is not the zero polynomial, then the cycle has length 73. There are 7 such cycles. Of course, if p(x)=0, then the cycle has length 1.
Now, it's pretty hard to characterize the factorizations of xn+x+1, even if polynomial factorization can be done quickly (faster than integer factorization for sure). The only other thing I can say is that x2+x+1 is always a divisor of xn+x+1 when n=2 (mod 3), and xn+x+1 is always square-free, since the gcd of xn+x+1 and its derivative is always 1. That's about it.
Here are full factorizations of xn+x+1 (mod 2) from n=2 to 20. The symbol * after a factor means that it is not a primitive polynomial; in this case the smallest m for which it divides xm-1 is given.
x2+x+1
x3+x+1
x4+x+1
x5+x+1=(x2+x+1)(x3+x2+1)
x6+x+1
x7+x+1
x8+x+1=(x2+x+1)(x6+x5+x3+x2+1)
x9+x+1*
x10+x+1=(x3+x+1)(x7+x5+x4+x3+1)
x11+x+1=(x2+x+1)(x9+x8+x6+x5+x3+x2+1)
x12+x+1=(x3+x2+1)(x4+x3+1)(x5+x3+x2+x+1)
x13+x+1=(x5+x4+x3+x+1)(x8+x7+x5+x3+1)
x14+x+1=(x2+x+1)(x5+x3+1)(x7+x6+x5+x2+1)
x15+x+1
x16+x+1=(x8+x6+x5+x3+1)(x8+x6+x5+x4+x3+x+1)*
x17+x+1=(x2+x+1)(x3+x+1)(x12+x11+x10+x9+x8+x6+x4+x+1)*
x18+x+1=(x5+x2+1)(x13+x10+x8+x7+x4+x3+x2+x+1)
x19+x+1=(x3+x2+1)(x4+x+1)(x5+x4+x2+x+1)(x7+x5+x4+x3+x2+x+1)
x20+x+1=(x2+x+1)(x5+x4+x3+x2+1)(x13+x11+x10+x9+x7+x4+1)
x9+x+1: 73
x8+x6+x5+x4+x3+x+1: 85
x12+x11+x10+x9+x8+x6+x4+x+1: 273
Joined: 3/2/2010
Posts: 2174
Location: A little to the left of nowhere (Sweden)
I ran into this problem recently, I'm not sure it actually has an answer as I cannot find one, but perhaps my math simply isn't strong enough.
Given a sequence of 19 pre-defined numbers, for simplicity sake, lets say 1-19. Is there a sensible way (like an algorithm) to get all possible re-ordered sequences of the given numbers?
I ran into this problem recently, I'm not sure it actually has an answer as I cannot find one, but perhaps my math simply isn't strong enough.
Given a sequence of 19 pre-defined numbers, for simplicity sake, lets say 1-19. Is there a sensible way (like an algorithm) to get all possible re-ordered sequences of the given numbers?
Joined: 3/2/2010
Posts: 2174
Location: A little to the left of nowhere (Sweden)
Ilari wrote:
Warepire wrote:
I ran into this problem recently, I'm not sure it actually has an answer as I cannot find one, but perhaps my math simply isn't strong enough.
Given a sequence of 19 pre-defined numbers, for simplicity sake, lets say 1-19. Is there a sensible way (like an algorithm) to get all possible re-ordered sequences of the given numbers?
I ran into this problem recently, I'm not sure it actually has an answer as I cannot find one, but perhaps my math simply isn't strong enough.
Given a sequence of 19 pre-defined numbers, for simplicity sake, lets say 1-19. Is there a sensible way (like an algorithm) to get all possible re-ordered sequences of the given numbers?
I know this was already answered, but it's an interesting problem that happens to be simple enough for me to tackle (very rare in this math challenges thread). I also don't know C++ that well, so I'd like to offer my own solution, even though it may match what is in Ilari's link.
Let's work with a smaller set of numbers, just 6 through 10 (I'm using 6 through 10 instead of 1 through 5 because I'd like to use those integers later). First, sort them so our first permutation is 6, 7, 8 , 9, 10. Now, produce five bins whose minimal values are
1, 1, 1, 1, 1
and whose maximal values are
5, 4, 3, 2, 1
The bin values of 1, 1, 1, 1, 1 correspond to the first permutation, 6, 7, 8, 9, 10. To produce the next permutation, increment the leftmost bin until it "carries over" and increments the bin to its immediate right. So to produce the first eleven bin values, we would take...
And so on.
How do we obtain a permutation from the bins? If n is the number in the bin, simply take the nth entry in our first permutation that remains in the list. After it has been added, remove it from the list. (Note this means our first permutation didn't have to be in order, we just need to preserve the list's ordering as we progress.) As an example, suppose our bins contain the values 4, 2, 2, 1, 1. The algorithm would look like this (written lazily in Lua-esque pseudocode):
List = {6, 7, 8, 9, 10} --This is the original list.
Bins = {4, 2, 2, 1, 1}
Permutation = {} --The final output is just the empty set so far.
--The first element in Bins is 4, so take the 4th element of List and insert it in Permutation:
Permutation = {9}
--Remove the fourth element of List because we can't use 9 in our permutation anymore:
List = {6, 7, 8, 10}
--(This could be done with Lua's table.remove function or some other programming equivalent. Also note that algorithmically, it may be helpful to remove the first element of Bins so this entire process is done using table.remove and table.add.)
--Now repeat the process. The second element of Bins is 2, so insert the second element of List into Permutation:
Permutation = {9, 7}
Don't forget to remove 7 from List:
List = {6, 8, 10}
Finishing the last three steps:
Permutation = {9, 7, 8}
List = {6, 10}
Permutation = {9, 7, 8, 6}
List = {10}
Permutation = {9, 7, 8, 6, 10}
And we're done! Because there are 5! different possible values of the Bins variable and each one corresponds to a unique permutation (this is easy to show), all permutations are accounted for. To produce the next permutation, just follow the process I outlined above, incrementing the leftmost bin until it "carries over" to the one to its immediate right and resets to 1.
Well, after typing all of that out, I've suddenly realized that it does not produce unique permutations if some of the elements are identical. My recollection is that the combinatorics gets pretty difficult once identical elements are included, so I'll give the problem a little more thought and see if I can tweak the algorithm to suit it. Perhaps this is taken into account in the C++ algorithm? If not, then I propose that problem as the next math challenge.
So, Monty Hall once again... is as unintuitive as ever.
So, you are playing a round of Monty Hall. You choose door number 1. The host opens one of the other doors and reveals a goat and gives you the chance to switch your selection. Would it be advantageous for you to switch? Since you are savvy and know the probabilities, you of course switch, in order to get the 2/3 win probability.
However, if before your decision I told you that the host actually opened a door at random, without knowing what would be behind it (and it just happened to have the goat behind it in this particular case), would it still be advantageous to switch?
"Of course", you say. "What goes inside the host's head doesn't change anything. The two other doors still have a 2/3 chance, and now I have information about which door it can't be. So of course it's advantageous to switch."
Seems completely reasonable. If in a particular round the host reveals a goat door, we are within the standard Monty Hall scenario. The reason why that particular door was revealed shouldn't change anything. It's not like the probabilities change depending on what the host was thinking at that moment, or what he knew. This isn't (a pseudoscientific version of) quantum mechanics, after all; this is pure math.
So let's test that scenario with a small computer program. Just to see that it works correctly we first implement the traditional scenario (the host always reveals a goat door, and the contestant always switches). This gives the expected 66% winning rate.
Now we change the program so that the host opens a random door from the two unchosen doors, we discard the rounds where the car door was opened (because we are not interested in those rounds, we are only interested in the rounds where a goat door was opened at random, because our scenario was to see if it's advantageous to switch if you happen to be in a round where a goat door was opened) and then print the result.
And our collective jaws drop to the floor when the program prints a winning rate of "50%" (or something close to it.) We review the program to see where the bug is, and can't find it. It still prints "50%" no matter how many times we run it.
I wrote a small such program that runs a million rounds. With the classic Monty Hall scenario it prints
1000000 rounds, 667169 wins, 66%
With the random-reveal version it prints
666267 rounds, 333630 wins, 50%
Why does this happen? Why does the host knowing or not knowing affect the probabilities of those rounds where the goat was revealed? Why is this so unintuitive?
I'm not sure, but it may not be fair to exclude a third of the results. When you include the 333733 rounds in which the host unwittingly revealed the car, you have a win rate of 33%, the same as only choosing once.
<Zurreco> if so called professional players cant adapt to every playing field, theyre obviously not that great
Including the rounds where the car door is revealed is not relevant to the problem I posed.
The point was this: "if before your decision (to switch) I told you that the host actually opened a door at random, would it still be advantageous to switch?"
All logic and intuition would dictate that it makes absolutely no difference what the host knew or didn't know in his head when he revealed the goat. Heck, you (as the contestant) cannot even know if this was a random or a deliberate reveal if I didn't tell you. Yet somehow it does make a difference...
I think the difference comes from the fact that the host revealing a goat is no longer a necessity, so when a goat IS revealed that gives us extra information about the possibilities of the game, changing the probabilities. It's clear that if the host revealed the car then we would instantly know we had lost, but we didn't know that before he had opened a door. In the original game, no information is conveyed like this because a goat is always revealed.
Let's say there's Goat A, Goat B, and Car, so can use 'ABC' notation conveniently enough. Let the first letter be your choice, the second the revealed door, and thus the third letter what you could choose to switch to. Obviously the basic combinations are:
ABC
ACB
BAC
BCA
CAB
CBA
The problems stem from conditional probability, trying to keep track of which remaining possibilities/combinations we're actually talking about here. There's 1/3 chance of picking A first say, and thus 2 remaining doors to play with. However, this is where the two games diverge, since normally the host never shows you the car. This means that given A, there's a 0% chance of him doing 'ACB', and thus 100% chance of it being 'ABC'. If we choose C first, then he can show us either A or B, with probability of 50% each, thus:
ABC=1/3*1=1/3
ACB=1/3*0=0
BAC=1/3*1=1/3
BCA=1/3*0=0
CAB=1/3*1/2=1/6
CBA=1/3*1/2=1/6
Good: ABC+BAC=1/3+1/3=2/3
Bad: CAB+CBA=1/6+1/6=1/3
Those give the standard figures. For your alternative game, we no longer deliberately discard 'ACB' and 'BCA' from the start, because he could accidentally show you the car now. This means that given A as your first choice, it's no longer 100% that he'll show you B next, but he may also show C, with probability 50% each. This changes it from the standard 100/0 split the game had before, to 50/50. This means the probabilities of each set occurring are no longer biased against one particular set, giving us a normal distribution of
ABC=1/3*1/2=1/6
ACB=1/3*1/2=1/6 -Discarded after
BAC=1/3*1/2=1/6
BCA=1/3*1/2=1/6 -Discarded after
CAB=1/3*1/2=1/6
CBA=1/3*1/2=1/6
Good: ABC+BAC=1/6+1/6=2/6=1/3
Bad: CAB+CBA=1/6+1/6=2/6=1/3
Here we have P(Good)=P(Bad)=1/3, with the remaining 1/3 being discarded, IE restarting the game. So given that we actually had a successful game, we have equal chances of switching being a good or bad thing, thus the 50% figure you got.
Why is that counter intuitive? Well instead of the host choosing to get rid of a bad prize, he just gets rid of a prize at random, then of course that's gonna lower your chance of winning isn't it? Would've thought that's expected.
That explains why the simulation gives 66% in one situation and 50% in the other.
The question remains, though: If you are playing one single round, and the host reveals a goat door, is it advantageous to change?
Let's say you don't know if the host opened the door randomly or knowingly. How would you even know, if nobody tells you? How do you know if you are in the standard Monty Hall setup, or in the randomized version? There's no way of knowing.
More puzzlingly, even if you do know, why would that make any difference?
If you were playing several rounds, then it obviously makes a difference. In the randomized variation you are, effectively, playing with two doors, which is why there's a 50/50 chance. In the normal version no door is discarded, so you have the 66/33 chance.
I think this puts the original question in a new light, given that the original Monty Hall problem (at least implicitly) talks about one single round. Does it really make a difference whether you switch or not?
If you are playing one single round, and the host reveals a goat door, is it advantageous to change?
Let's say you don't know if the host opened the door randomly or knowingly. How would you even know, if nobody tells you? How do you know if you are in the standard Monty Hall setup, or in the randomized version? There's no way of knowing.
Let's also assume that the host is allowed to use any strategy whatsoever, not just the two strategies mentioned (random, and Monty Hall/always open goat door) and the player has no way of knowing. This becomes a game-theoretic question.
The player can never do worse than 50%. Flip a coin. Don't switch if heads, switch if tails. No matter what strategy the host does, given that the opened door is a goat, switching is either right or wrong. Assigning 50% probabilities to switch or not switch gives 50% success rate, no matter what.
On the other hand, the host can set it up so that the player can never do better than 50% (random door strategy).
So the solution based on these assumptions: Flip a coin. Don't switch if heads, switch if tails. 50% success rate always.
On the other hand, if the player knew exactly what the host's strategy was, then the player may gain an advantage. If the host's strategy gives a higher-than-50% success rate for switching (such as Monty Hall), then the player switches. If the host's strategy gives a lower-than-50% success rate for switching (such as, host always opens car door if player initially selected goat door), then the player does not switch.
Warp wrote:
More puzzlingly, even if you do know, why would that make any difference?
It's called strategy. It exists just about everywhere (we're on a gaming site, even).
Whether only one round is performed or not is irrelevant. Every round has a success probability, even when there is only one.
- The internal state of the Galois LFSR above (lower image) can be represented by the polynomial given by sum(ith bit is 1) xi, where the leftmost bit is bit 0 and bit position counts left to right. Example above: 1+x2+x4+x5+x8+x9+x10+x15.
- Cycling the Galois LFSR is as simple as multiplying the polynomial internal state by x and taking the remainder upon division by the reverse of the LFSR's polynomial 1+x2+x3+x5+x16.
- Let f(x) be the reverse of the LFSR's polynomial and p(x) be the initial Galois LFSR state. Then the question is: what is the smallest positive n such that f(x) divides p(x)(xn-1)?
- Factor f(x) into irreducible factors f1(x)f2(x)...fk(x). Then for each irreducible factor that does not divide p(x), the question is: what is the smallest positive ni such that fi(x) divides xni-1?. If f(x) itself is irreducible, then it cannot divide p(x) (since deg f > deg p) unless p(x) is the zero polynomial.
- Even if f(x) is irreducible, that doesn't necessarily mean that the LFSR has period 2deg f-1 (the maximum) for nonzero initial values. In order for that to happen, the smallest positive n for which f(x) divides xn-1 must be 2deg f-1. In this case, f(x) is a primitive polynomial (field theory definition of primitive, not gcd definition).
- Note that every polynomial with nonzero constant term is a divisor of xn-1 for some n. In particular, an irreducible polynomial g(x), other than x, is a divisor of x^(2deg g-1)-1. This follows from field theory but I won't go into it here.
At this point, it is easier just to do small examples. The polynomials of interest are the reversals of xn+xn-1+1, that is, xn+x+1.
n=5:
x5+x+1=(x2+x+1)(x3+x2+1).
Note that both x2+x+1 and x3+x2+1 are primitive polynomials.
Let p(x) be the polynomial for the initial Galois LFSR state. Let g(p(x))=(u(x),v(x)) where u(x) is remainder of p(x) divided by x2+x+1 and v(x) is remainder of p(x) divided by x3+x2+1 (this is unique by the Chinese Remainder Theorem).
If g(p(x))=(0,0) (p(x) is the zero polynomial), then the cycle has length 1.
If g(p(x))=(u(x),0) for nonzero u(x), then the cycle has length 22-1=3 (since x3+x2+1 divides p(x), its only contribution is from x2+x+1)
If g(p(x))=(0,v(x)) for nonzero v(x), then the cycle has length 23-1=7.
If g(p(x))=(u(x),v(x)) for nonzero u(x) and v(x), then the cycle has length gcd(3,7)=21; this covers all possible values as well.
n=8:
x8+x+1=(x2+x+1)(x6+x5+x3+x2+1).
Note that both x2+x+1 and x6+x5+x3+x2+1 are primitive polynomials.
Let p(x) be the polynomial for the initial Galois LFSR state. Let g(p(x))=(u(x),v(x)) where u(x) is remainder of p(x) divided by x2+x+1 and v(x) is remainder of p(x) divided by x6+x5+x3+x2+1.
If g(p(x))=(0,0) (p(x) is the zero polynomial), then the cycle has length 1.
If g(p(x))=(u(x),0) for nonzero u(x), then the cycle has length 22-1=3.
If g(p(x))=(0,v(x)) for nonzero v(x), then the cycle has length 26-1=63.
If g(p(x))=(u(x),v(x)) for nonzero u(x) and v(x), then the cycle has length gcd(3,63)=63. For a given v(x), there are 3 possible values for u(x) in order to cover all possible values; thus, this gives 3 classes of length 63, for a total of 4.
n=9:
x9+x+1 is irreducible.
Now since the smallest positive n such that x9+x+1 divides xn-1 is n=73 (instead of n=29-1=511), x9+x+1 is not primitive. In fact, if p(x) is the initial Galois LFSR state, and p(x) is not the zero polynomial, then the cycle has length 73. There are 7 such cycles. Of course, if p(x)=0, then the cycle has length 1.
Now, it's pretty hard to characterize the factorizations of xn+x+1, even if polynomial factorization can be done quickly (faster than integer factorization for sure). The only other thing I can say is that x2+x+1 is always a divisor of xn+x+1 when n=2 (mod 3), and xn+x+1 is always square-free, since the gcd of xn+x+1 and its derivative is always 1. That's about it.
Here are full factorizations of xn+x+1 (mod 2) from n=2 to 20. The symbol * after a factor means that it is not a primitive polynomial; in this case the smallest m for which it divides xm-1 is given.
x2+x+1
x3+x+1
x4+x+1
x5+x+1=(x2+x+1)(x3+x2+1)
x6+x+1
x7+x+1
x8+x+1=(x2+x+1)(x6+x5+x3+x2+1)
x9+x+1*
x10+x+1=(x3+x+1)(x7+x5+x4+x3+1)
x11+x+1=(x2+x+1)(x9+x8+x6+x5+x3+x2+1)
x12+x+1=(x3+x2+1)(x4+x3+1)(x5+x3+x2+x+1)
x13+x+1=(x5+x4+x3+x+1)(x8+x7+x5+x3+1)
x14+x+1=(x2+x+1)(x5+x3+1)(x7+x6+x5+x2+1)
x15+x+1
x16+x+1=(x8+x6+x5+x3+1)(x8+x6+x5+x4+x3+x+1)*
x17+x+1=(x2+x+1)(x3+x+1)(x12+x11+x10+x9+x8+x6+x4+x+1)*
x18+x+1=(x5+x2+1)(x13+x10+x8+x7+x4+x3+x2+x+1)
x19+x+1=(x3+x2+1)(x4+x+1)(x5+x4+x2+x+1)(x7+x5+x4+x3+x2+x+1)
x20+x+1=(x2+x+1)(x5+x4+x3+x2+1)(x13+x11+x10+x9+x7+x4+1)
x9+x+1: 73
x8+x6+x5+x4+x3+x+1: 85
x12+x11+x10+x9+x8+x6+x4+x+1: 273
