You can also multiply polynomials by way of analogy with integer multiplication: 3 1 2 1 × 2 0 6 ------------ 18 6 12 6 0 0 0 0 6 2 4 2 ----------------- 6 2 22 8 12 6 = 6x^5 + 2x^4 + 22x^3 + 8x^2 + 12x^1 + 6x^0.
[deleted]
Convolutions, Polynomials and Flipped Kernels
41–49 of 49 posts
Re: Convolutions, Polynomials and Flipped Kernels
#42Earlier quoted context omitted.
On similar lines the MAX operator on the random variables become PRODUCT operator on its distribution. It's fun to play with the (Max, +)algebra of random variables and infer it's distribution. This turns out to be quite useful in estimating completion time of dependant parallel jobs. Spawning multiple parallel jobs becomes a Max operation and chaining sequential jobs becomes a '+' operation on the completion times.…
Almost every probability theorem starts with "let's take independent random variables". But in reality almost nothing is independent. Superdeterminism even claims that exactly nothing is independent.
Almost every elementary probability theorem. There are plenty of theorems conditional on bounds on how weak the dependency should be (or how fast correlations decrease with order, etc.), including CLT-like theorems, it’s just that they are difficult to state, very difficult to prove, and almost impossible to verify the applicability of. In practice you are anyway going to instead use the simpler version and check if the results make sense after the fact.
Re: Convolutions, Polynomials and Flipped Kernels
#43Earlier quoted context omitted.
You are using PMFs. I meant and wrote distribution function aka cumulative distribution function. They are closed under products. > Did you get it from LLM LOL. There must be a fun and guilty story lurking inside the accusation. On a more serious note, I would love it if LLMs could do such simplifications and estimations on their own.
Distributions can be either PDFs or CDFs. To be honest I'd never heard of assuming that a distribution was a CDF unless otherwise specified.
This is a natural point of confusion. The true (IMO) primitive concept here is the probability measure. Probability measures on the real line are in canonical bijection with CDFs, the latter being axiomatizable as càdlàg functions (see https://en.wikipedia.org/wiki/Càdlàg) asymptotic to 0 (resp. 1) at minus infinity (resp. infinity). On the other hand, not every probability measure has a density function. (If you want the formalism of densities to capture all probability measures, you need to admit more exotic generalized functions à la Dirac.)
Re: Convolutions, Polynomials and Flipped Kernels
#44Earlier quoted context omitted.
What ? I've never heard of this math. Do you mean literally those are the resulting operations in the general case or are those approximate explanation and we need to find more specific cases to make this true ?
Check out tropical algebras
Fascinating thank you for reminding me about that
Re: Convolutions, Polynomials and Flipped Kernels
#45Earlier quoted context omitted.
Surely this isn't quite right. Max of variables = product of cumulative distribution functions . Sum of variables = convolution of probability density functions . So both of the equations you write down are correct, but only if you interpret "Distr" as meaning different things in the two cases. [EDITED to add:] Provided the random variables in question are independent, as mentioned elsewhere in the discussion; if the…
The original post, to which I replied, is about the correspondence between summation of random variables and convolution of their distribution. Independence is sufficient for that. I just carried through that assumption of independence in my own comment, thinking it was obvious to do that (carry over the assumptions).
But is he right about the different meanings of Distr in your equations ?
Re: Convolutions, Polynomials and Flipped Kernels
#46You can also multiply polynomials by way of analogy with integer multiplication: 3 1 2 1 × 2 0 6 ------------ 18 6 12 6 0 0 0 0 6 2 4 2 ----------------- 6 2 22 8 12 6 = 6x^5 + 2x^4 + 22x^3 + 8x^2 + 12x^1 + 6x^0.
Not to mention divide:
2x^2 + 5x - 3
-------------
x + 2
2x + 1
______________
x + 2 | 2x^2 + 5x - 3
2x^2 + 4x
-------------
x - 3
x + 2
-----
- 5
5
= 2x + 1 - -----
x + 2
x + 1
_______________
x + 1 | x^2 + 2x + 1
x^2 + x
--------
x + 1
x + 1
-----
0Re: Convolutions, Polynomials and Flipped Kernels
#47Earlier quoted context omitted.
The original post, to which I replied, is about the correspondence between summation of random variables and convolution of their distribution. Independence is sufficient for that. I just carried through that assumption of independence in my own comment, thinking it was obvious to do that (carry over the assumptions).
But is he right about the different meanings of Distr in your equations ?
No he is not.
Both the ideas work for the cumulative distribution function that is called just distribution function in math. I think he got confused by the fact that convolution relation works also with densities (so he might have assumed that it works with densities only and not distributions)
Re: Convolutions, Polynomials and Flipped Kernels
#48Earlier quoted context omitted.
But is he right about the different meanings of Distr in your equations ?
No he is not. Both the ideas work for the cumulative distribution function that is called just distribution function in math. I think he got confused by the fact that convolution relation works also with densities (so he might have assumed that it works with densities only and not distributions)
I'm sorry, but I think you are just wrong about convolutions and cumulative distribution functions.
Let's take the simplest possible case: a "random" variable that's always equal to 0. Its cdf is a step function: 0 for negative values, 1 for positive values. (Use whatever convention you prefer for the value at 0.)
The sum of two such random variables is another with the same distribution, of course. So, what's the convolution of the cdfs?
Answer: it's not even well defined.
The convolution of functions f and g is a function such that h(x) = integral over t of f(t) g(x-t) dt. The integral is over the whole of (in this case) the real numbers.
In this case f and g are both step functions as described above, so (using the convenient Iverson bracket notation for indicator functions) this is the integral over t of [t>0] [x-t>0] dt, i.e., of [0This is not the cdf of any probability distribution since it doesn't -> 1 as x -> oo. In particular, it isn't the cdf of the right probability distribution which, as mentioned above, would be the same step function as f and g.
If X,Y are independent with pdfs f,g and cdfs F,G then the cdf of X+Y is (not F conv G but) f conv G = F conv g.
Re: Convolutions, Polynomials and Flipped Kernels
#49Earlier quoted context omitted.
No he is not. Both the ideas work for the cumulative distribution function that is called just distribution function in math. I think he got confused by the fact that convolution relation works also with densities (so he might have assumed that it works with densities only and not distributions)
I'm sorry, but I think you are just wrong about convolutions and cumulative distribution functions. Let's take the simplest possible case: a "random" variable that's always equal to 0. Its cdf is a step function: 0 for negative values, 1 for positive values. (Use whatever convention you prefer for the value at 0.) The sum of two such random variables is another with the same distribution, of course. So, what's the co…
Oops, one thing in the above is completely wrong (I wrote it before thinking things through carefully, and then forgot to delete it).
It is not at all true that "it's not even well defined", and indeed the following couple of paragraphs determine exactly what the thing in question is. It's not an actual cdf, but the problem isn't that it's ill-defined but that it's well-defined but has the wrong shape to be a cdf.