Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Convolutions, Polynomials and Flipped Kernels

eli.thegreenplace.net

Post reply on HN
Print view View original

11–20 of 49 posts

Re: Convolutions, Polynomials and Flipped Kernels

#11

Post by whatshisface »

srean wrote: post #6
incognito124 wrote: post #5

My favourite use case for this: By the same derivation as this blog, one can prove that, if you have any two probability distributions X and Y (they can be different), the probability distribution of X+Y is a convolution of the PMFs/PDFs of X and Y.

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.…

That doesn't sound right. If P(X) is the vector {0.5,0,0.5} and P(Y) is {0.5,0.5,0}, P(X)P(Y) is {0.25,0,0} and that's both not normalized and clearly not the distribution for max(X,Y). Did you get that from an LLM?

Re: Convolutions, Polynomials and Flipped Kernels

#12

Post by srean »

whatshisface wrote: post #11
srean wrote: post #6

Earlier 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.…

That doesn't sound right. If P(X) is the vector {0.5,0,0.5} and P(Y) is {0.5,0.5,0}, P(X)P(Y) is {0.25,0,0} and that's both not normalized and clearly not the distribution for max(X,Y). Did you get that from an LLM?

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.

Re: Convolutions, Polynomials and Flipped Kernels

#15

Post by eliben »

stared wrote: post #13

Beware - one step more and you get into the region of generating functions. I recommend a book Herbert Wilf with a wonderful name of Generatingfunctionology ( https://www2.math.upenn.edu/~wilf/gfology2.pdf ).

Indeed, generating functions are mentioned in a footnote :) Very interesting topic

Re: Convolutions, Polynomials and Flipped Kernels

#16

Post by [deleted] »

srean wrote: post #12
whatshisface wrote: post #11

Earlier quoted context omitted.

That doesn't sound right. If P(X) is the vector {0.5,0,0.5} and P(Y) is {0.5,0.5,0}, P(X)P(Y) is {0.25,0,0} and that's both not normalized and clearly not the distribution for max(X,Y). Did you get that from an LLM?

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.

[deleted]

Re: Convolutions, Polynomials and Flipped Kernels

#17

Post by whatshisface »

srean wrote: post #12
whatshisface wrote: post #11

Earlier quoted context omitted.

That doesn't sound right. If P(X) is the vector {0.5,0,0.5} and P(Y) is {0.5,0.5,0}, P(X)P(Y) is {0.25,0,0} and that's both not normalized and clearly not the distribution for max(X,Y). Did you get that from an LLM?

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.

Re: Convolutions, Polynomials and Flipped Kernels

#18

Post by srean »

whatshisface wrote: post #17
srean wrote: post #12

Earlier 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.

May I raise you a

https://en.m.wikipedia.org/wiki/Distribution_function

It's right in the title.

In probability theory, integration theory, as well as electrical engineering, "distribution function", unless further clarified, means that cumulative thing.

In math, nomenclature overloading can be a problem. So context matters. In the context of dirac delta, distribution means something else entirely -- generalized functions.

Oh! So sad you deleted your point about densities. One can only laugh at and enjoy these idiosyncrasies of nomenclature.

In Electrical Engineering one uses j for imaginary numbers because i is taken (by current).

Re: Convolutions, Polynomials and Flipped Kernels

#19

Post by [deleted] »

srean wrote: post #18
whatshisface wrote: post #17

Earlier quoted context omitted.

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.

May I raise you a https://en.m.wikipedia.org/wiki/Distribution_function It's right in the title. In probability theory, integration theory, as well as electrical engineering, "distribution function", unless further clarified, means that cumulative thing. In math, nomenclature overloading can be a problem. So context matters. In the context of dirac delta, distribution means something else entirely -- generalized func…

[deleted]

Re: Convolutions, Polynomials and Flipped Kernels

#20

Post by stared »

eliben wrote: post #15
stared wrote: post #13

Beware - one step more and you get into the region of generating functions. I recommend a book Herbert Wilf with a wonderful name of Generatingfunctionology ( https://www2.math.upenn.edu/~wilf/gfology2.pdf ).

Indeed, generating functions are mentioned in a footnote :) Very interesting topic

Saw that!

Sometimes it makes things simpler (quite a a lot of things in combinatorics), other times it is a tools for nice tricks (I have no idea how I would solved these equations if it were not for generating functions, see the appendix from a Mafia game paper, https://arxiv.org/abs/1009.1031).

Post reply on HN