I think the reason this works is that multiplying polynomials does convolution on the coefficients, and that adding discrete probabilities is a convolution of their histograms. Neat video!
Right? I had been under the impression that generating functions only became useful when the power series has infinitely many terms and a positive radius of convergence, so that one can use tools from analysis to prove things that translate back to statements about the coefficients. But even finite-degree generating functions can be a powerful tool!
@@BenZinbergTutor Generating functions can also be used to solve recurrences! To delve deeper I recommend reading generating functionology by S.Wilf (it can easily be found on google). There he explores all kinds of applications, its a great read on a fun tool.
@@jurel-enlatado1 Oh wow, all sorts of cool stuff in there! I had heard of the book but hadn't looked through it. I suspect the sections on linear recurrences are just a different outfit for finding the eigenvalues of the associated matrix, but even there, the extension to boundary value problems is impressive. And many more cool applications later on. Thanks for the rec!
Multiplying two polynomials is the same thing as taking the discrete convolution of their coefficients. The convolution theorem for probability says that if you have two random variables X and Y with probability distributions Px and Py then the probability distribution for X+Y will be Px convolved with Py. It’s interesting to see how you can just steal one factor from one of the dice to get a new set of dice with this property. And that this is the ONLY other set of dice with the same probability distribution.
This is really elegant! (My first thought was to label the dice 012345 and 234567, but that obviously fails the "positive integers" restriction.) I worked it out on paper as follows: we're convolving one die with the other and producing a symmetric pyramid, so let's try a die whose distribution is a symmetric pyramid (specifically: the distribution rises then falls again, symmetrically). The standard die is a degenerate case of this. Both dice must have exactly one 1, and the pyramid die can't have more than two 2s. So use 122334 for the first die in order to produce a die with a non-flat symmetric pyramidal distribution. And that easily results in 134568 for the second die, which works. (The only other symmetric pyramid options would be 123345 or 122223, which don't work.)
Nice work! Your intuition here was better than mine. I'd be very interested to see if there is a simple argument to rule out solutions where neither of the dice has a pyramid-shaped PMF -- seems like there could be! And yeah, sounds like you saw right away that the positive restriction doesn't really exclude anything. If we drop that restriction, we can still assume without loss of generality that the smallest label on each die is 1, by adding a constant to each face of one die and subtracting that constant from each face of the other die.
lovely proof and demonstration, thank you! also (sorry) wanted to mention that on a standard die opposite faces add up to 7 so your nets for the regular dice are not quite right but it doesnt change the maths :) great video otherwise though, subbed!
@@danjwheatley No worries, I appreciate you mentioning it! Incidentally, each of the Sicherman dice can also be laid out so that all pairs of opposite faces have the same sum.
Not much changes if we drop the requirement of positive face labels. Given a solution, one can add a constant to each face of the first die and subtract that constant from the second die to obtain a new solution, and we could say that those two solutions are "equivalent," in the same way that in Scrabble one might say a word is "equivalent" to its plural. Then, a solution that has nonpositive face labels is always equivalent to a solution that has positive face labels: one can show that it's always possible to choose the additive constant above so that the smallest label on each die is 1.
Nice! The shift from faces to polynomials is similar, I think, to how exponentiation turns multiplications into addition (a thing called omomorphism, I think
Yes, that's right! Just as exponentiation is a structure-preserving map (aka homomorphism) from "addition of real numbers" to "multiplication of positive real numbers," the conversion of dice to polynomials is essentially (up to scaling) a homomorphism from "addition of independent discrete random variables" to "multiplication of polynomials."
Ooh! This made me have an idea in my head... Can we think of a binomial approximation as an infinite sided die when expanded with each coefficient of x representing the number of faces with y dots and the power of x representing the number of dots (y) on a face
I wonder if there is an interpretation to negative (and complex) coefficient polynomial factor. If so, you might have to expand the notion of probability to negative (and complex) values. Great video!
You will have to recast this into a problem where negative numbers have a specific interpretation. You can start with a simple intuitive example by polynomial multiplication: a(x) = x + x^2 b(x) = -x - x^2 = - (x + x^2) The first is a coin with 1 and 2 dots on its faces, the second is also technically a coin with 1 and 2 dots in this faces, but there's a mysterious "negative sign" on the coin. Their product will yield: -x^2 -2x^3 -x^4 This is essentially still summing up the values of the faces but with now the coefficients being somehow negative. This means that there's some extra trickery happening where the (-1) is "negating" a property of the basic coin that we have. This indicates that we need to add a new "rule" (or expanding the algebra) for the game but we still need to "count" the values in a certain way. For example, you can create custom dice with different colored faces and now the dice game has a new set of rules: 1. Roll the dice together 2. Track the following as the outcome of the roll - (1) whether both dice have the same color, (2) the sum of the dots on the faces of the dice. Dice 1 is black 2, dice 2 is white 4. The outcome is (DIFFERENT, 6) 3. Now you instead track the distribution of #(SAME COLOR) - #(DIFFERENT COLOR) for a given sum This will allow you to add an interpretation for negative coefficients. As an example, let's take a(x) = x + x^2 b(x) = x - x^2 a(x)b(x) = x^2 - x^4 This is equivalent to playing with a coin with 2 white faces (1 dot and 2 dot) and a coin with a white face with a single dot and a black face with 2 dots. Outcomes are: white 1 and white 1 => (SAME, 2) white 2 and black 2 => (DIFFERENT, 4) white 2 and white 1 => (SAME, 3) white 1 and black 2 => (DIFFERENT, 3) 2 => 1 (SAME) - 0 (DIFFERENT) => 1 3 => 1 (SAME) - 1 (DIFFERENT) => 0 4 => 0 (SAME) - 1 (DIFFERENT) => -1 This now allows us to now make a more "general" dice game which is consistent with the rules of the original dice game we created.
The idea I shared for negative numbers is an idea from a more general framework from measure theory called "signed measures" where you assign an integer value to a specific outcome 1. mu(1 white, 1 black) => -1 2. mu(1 white, 1 white) => +1 Define rules of "combining" different outcomes into a single value e.g. a measure for "numbers that add up to 2" is a sum of all "mu" values of the different outcomes where the dots add up to 2. As for whether these constitute meaningful probabilities, these concepts are used for calculations in fields such as physics and finance: en.wikipedia.org/wiki/Negative_probability A real physical interpretation for it could be - if you play a betting game where you gain 1$ if the colors are same for a given sum and lose 1$ if the colors are different for a given sum. The distribution will be that of the expected loss/profit from a given sum of numbers.
If we allowed a 12 and 3 sided die we could then have 1,2,2,3,3,4,4,5,5,6,6,7 and 1,3,5 and two other options I haven't worked out. I just have to move the factors of 1-x+x^2 around to find them though. Edit: at most one other option.
This is really cool. If you allow 0 on a face, it looks throwing a single sided dice is also equivalent to throwing a 2 sided and a 3 sided dice together, with [1,2] and [0,2,4] on their faces. x(x+1)= x+x^2 = [1,2] (1-x+x^2)(1+x+x^2) = 1+x^2+x^4= [0,2,4] Hard to have a 3 sided dice but one way to cheat is to have a six sided dice with [0,0,2,2,4,4] and a coin with [1,2]. I wonder can a dice with an arbitrary number of faces be decomposed into a collection of dice with prime factor number of faces?
Somewhat off topic, but I think my guess about prime factorizations of dice may be correct. For example with the standard D&D dice: Tetrahedral Dice: 4= 2x2 [1,2,3,4] = [1,2] + [0,2] Octahedral Dice: 8= 2x2x2 [1,2,3,4,5,6,7,8] = [1,2] + [0,2] + [0,4]
Spidey-senses tingled in a "generating function" kinda way. But I'm not Spiderman, so I just continued watching this great explainer!
I think the reason this works is that multiplying polynomials does convolution on the coefficients, and that adding discrete probabilities is a convolution of their histograms. Neat video!
"on the face of it"
I see what you did there.
Very cool. Even when knowing about generating functions, this is still a fun and interesting video because of the unique problem.
Right? I had been under the impression that generating functions only became useful when the power series has infinitely many terms and a positive radius of convergence, so that one can use tools from analysis to prove things that translate back to statements about the coefficients. But even finite-degree generating functions can be a powerful tool!
@@BenZinbergTutor Generating functions can also be used to solve recurrences! To delve deeper I recommend reading generating functionology by S.Wilf (it can easily be found on google). There he explores all kinds of applications, its a great read on a fun tool.
@@jurel-enlatado1 Oh wow, all sorts of cool stuff in there! I had heard of the book but hadn't looked through it. I suspect the sections on linear recurrences are just a different outfit for finding the eigenvalues of the associated matrix, but even there, the extension to boundary value problems is impressive. And many more cool applications later on. Thanks for the rec!
Multiplying two polynomials is the same thing as taking the discrete convolution of their coefficients. The convolution theorem for probability says that if you have two random variables X and Y with probability distributions Px and Py then the probability distribution for X+Y will be Px convolved with Py.
It’s interesting to see how you can just steal one factor from one of the dice to get a new set of dice with this property. And that this is the ONLY other set of dice with the same probability distribution.
This is really elegant!
(My first thought was to label the dice 012345 and 234567, but that obviously fails the "positive integers" restriction.)
I worked it out on paper as follows: we're convolving one die with the other and producing a symmetric pyramid, so let's try a die whose distribution is a symmetric pyramid (specifically: the distribution rises then falls again, symmetrically). The standard die is a degenerate case of this.
Both dice must have exactly one 1, and the pyramid die can't have more than two 2s. So use 122334 for the first die in order to produce a die with a non-flat symmetric pyramidal distribution. And that easily results in 134568 for the second die, which works.
(The only other symmetric pyramid options would be 123345 or 122223, which don't work.)
Nice work! Your intuition here was better than mine. I'd be very interested to see if there is a simple argument to rule out solutions where neither of the dice has a pyramid-shaped PMF -- seems like there could be!
And yeah, sounds like you saw right away that the positive restriction doesn't really exclude anything. If we drop that restriction, we can still assume without loss of generality that the smallest label on each die is 1, by adding a constant to each face of one die and subtracting that constant from each face of the other die.
Amazing video ❤🔥
Thanking algo for recommending this. Cool problem with satisfying solution
lovely proof and demonstration, thank you!
also (sorry) wanted to mention that on a standard die opposite faces add up to 7 so your nets for the regular dice are not quite right but it doesnt change the maths :)
great video otherwise though, subbed!
Yeah, I realized this after I posted the video. At that point it was too late 🙂
@@BenZinbergTutor completely understandable! feel silly having mentioned it now :S
@@danjwheatley No worries, I appreciate you mentioning it! Incidentally, each of the Sicherman dice can also be laid out so that all pairs of opposite faces have the same sum.
@@BenZinbergTutor oh nice!
beautiful video, love it
Very cool and well explained!
I don't see why no face can be 0, but anyway it is still a beautiful demonstration.
Not much changes if we drop the requirement of positive face labels. Given a solution, one can add a constant to each face of the first die and subtract that constant from the second die to obtain a new solution, and we could say that those two solutions are "equivalent," in the same way that in Scrabble one might say a word is "equivalent" to its plural. Then, a solution that has nonpositive face labels is always equivalent to a solution that has positive face labels: one can show that it's always possible to choose the additive constant above so that the smallest label on each die is 1.
Given it was in the problem statement, I'd say you'd be solving a different problem 😁
wow this is beautiful and quite easy to understand!
This video is super underrated!
What an amazing content
Nice! The shift from faces to polynomials is similar, I think, to how exponentiation turns multiplications into addition (a thing called omomorphism, I think
Yes, that's right! Just as exponentiation is a structure-preserving map (aka homomorphism) from "addition of real numbers" to "multiplication of positive real numbers," the conversion of dice to polynomials is essentially (up to scaling) a homomorphism from "addition of independent discrete random variables" to "multiplication of polynomials."
now let's factorize over the complex numbers and get some ugly dice
You playing D&D and some mad person bring the dice with 14 + 7i faces
That's really cool! And nice explanation of it all
Ooh! This made me have an idea in my head... Can we think of a binomial approximation as an infinite sided die when expanded with each coefficient of x representing the number of faces with y dots and the power of x representing the number of dots (y) on a face
Awesome!!
I wonder if there is an interpretation to negative (and complex) coefficient polynomial factor. If so, you might have to expand the notion of probability to negative (and complex) values. Great video!
You will have to recast this into a problem where negative numbers have a specific interpretation.
You can start with a simple intuitive example by polynomial multiplication:
a(x) = x + x^2
b(x) = -x - x^2 = - (x + x^2)
The first is a coin with 1 and 2 dots on its faces, the second is also technically a coin with 1 and 2 dots in this faces, but there's a mysterious "negative sign" on the coin.
Their product will yield:
-x^2 -2x^3 -x^4
This is essentially still summing up the values of the faces but with now the coefficients being somehow negative.
This means that there's some extra trickery happening where the (-1) is "negating" a property of the basic coin that we have. This indicates that we need to add a new "rule" (or expanding the algebra) for the game but we still need to "count" the values in a certain way.
For example, you can create custom dice with different colored faces and now the dice game has a new set of rules:
1. Roll the dice together
2. Track the following as the outcome of the roll - (1) whether both dice have the same color, (2) the sum of the dots on the faces of the dice. Dice 1 is black 2, dice 2 is white 4. The outcome is (DIFFERENT, 6)
3. Now you instead track the distribution of #(SAME COLOR) - #(DIFFERENT COLOR) for a given sum
This will allow you to add an interpretation for negative coefficients.
As an example, let's take
a(x) = x + x^2
b(x) = x - x^2
a(x)b(x) = x^2 - x^4
This is equivalent to playing with a coin with 2 white faces (1 dot and 2 dot) and a coin with a white face with a single dot and a black face with 2 dots.
Outcomes are:
white 1 and white 1 => (SAME, 2)
white 2 and black 2 => (DIFFERENT, 4)
white 2 and white 1 => (SAME, 3)
white 1 and black 2 => (DIFFERENT, 3)
2 => 1 (SAME) - 0 (DIFFERENT) => 1
3 => 1 (SAME) - 1 (DIFFERENT) => 0
4 => 0 (SAME) - 1 (DIFFERENT) => -1
This now allows us to now make a more "general" dice game which is consistent with the rules of the original dice game we created.
The idea I shared for negative numbers is an idea from a more general framework from measure theory called "signed measures" where you assign an integer value to a specific outcome
1. mu(1 white, 1 black) => -1
2. mu(1 white, 1 white) => +1
Define rules of "combining" different outcomes into a single value e.g. a measure for "numbers that add up to 2" is a sum of all "mu" values of the different outcomes where the dots add up to 2.
As for whether these constitute meaningful probabilities, these concepts are used for calculations in fields such as physics and finance: en.wikipedia.org/wiki/Negative_probability
A real physical interpretation for it could be - if you play a betting game where you gain 1$ if the colors are same for a given sum and lose 1$ if the colors are different for a given sum. The distribution will be that of the expected loss/profit from a given sum of numbers.
If we allowed a 12 and 3 sided die we could then have 1,2,2,3,3,4,4,5,5,6,6,7 and 1,3,5 and two other options I haven't worked out. I just have to move the factors of 1-x+x^2 around to find them though. Edit: at most one other option.
This is really cool. If you allow 0 on a face, it looks throwing a single sided dice is also equivalent to throwing a 2 sided and a 3 sided dice together, with [1,2] and [0,2,4] on their faces.
x(x+1)= x+x^2 = [1,2] (1-x+x^2)(1+x+x^2) = 1+x^2+x^4= [0,2,4]
Hard to have a 3 sided dice but one way to cheat is to have a six sided dice with [0,0,2,2,4,4] and a coin with [1,2].
I wonder can a dice with an arbitrary number of faces be decomposed into a collection of dice with prime factor number of faces?
Somewhat off topic, but I think my guess about prime factorizations of dice may be correct. For example with the standard D&D dice:
Tetrahedral Dice: 4= 2x2
[1,2,3,4] = [1,2] + [0,2]
Octahedral Dice: 8= 2x2x2
[1,2,3,4,5,6,7,8] = [1,2] + [0,2] + [0,4]
Dodecahedral Dice: 12= 2x2x3
[1,2,3,4,5,6,7,8,9,10,11,12] = [1,2] + [0,2] + [0,4,8]
Icosahedral Dice: 20= 2x2x5
[1,2, ... 19,20] = [1,2] + [0,2] + [0,4,8,12,16]
How did you generate the QR code for your content?
Given a polynomial p representing a particular n-sided die setup, what is the meaning or interpretation of evaluating p? eg: p(42) ?
It wouldn't have a useful interpretation.
Nice video :)
nice video
Why
Multiplicative principle on steroids
Bro made one magnificent video and youtube suggested to me right away. God bless reco algo 🙏