7 ms·
Convolutions, Polynomials and Flipped Kernels
- bjt12345 1y agoThis and complex analysis are fascinating topics in Undergraduate studies.
- esafak 1y agoContour integrals still feel cool.
- Sourabhsss1 1y agoThe visualizations make the concept easy to grasp.
- gitroom 1y ago[dead]
- incognito124 1y agoMy 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.
- srean 1y agoOn 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. This expression tree of Max'es and Plus'es can be algebraically processed to obtain bounds on the completion time distribution. One example is the straggler problem in mapreduce/Hadoop. In the naive case, the completion time is the max of each parallel subtask. (*) If the tasks have a heavy tail, which sometimes they do, the straggler's completion time can be really bad. This can be mitigated by k-out-n set up, where you encode the problem in such a way that only k out of n jobs need to finish to obtain the final result. One can play with this trade-off between potentially wasted computation and expected completion time. For heavy tailed distributions another simplification is possible. The tails of Max and + start becoming of the same order, so one can switch between convolutions and products. (*) This shows up in microservices architectures also. The owner/maintainer of a microservice end point might be very happy with its tail latency. However an end user who consumes and composed the results of the endpoints can experience really bad tail latencies for the final output.
- incognito124 1y agoThanks for sharing the name of that problem! I've encountered it before while optimizing batched LLM inference. The whole batch would last until all queries in a batch were done, and by changing the batch size, you'd trade off per-query-speed (better in a larger batch) with overall performance (worse with a larger batch). Nowadays I think this is solved in an entirely different way, though.
- deleted 1y ago[deleted]
- srean 1y agoIt gets more entertaining. It's common to wrap API calls with retry on failure, or spawn an identical request if taking longer than x,or recursively spawn an identical request if taking longer than x,or retry on failure but no more than k times. All of these and similar patterns/decorators can be analysed using the same idea.
- incognito124 1y agoOh wow, pretty cool stuff! If you have more to share, you can always dump it in my mail inbox
- silloncito 1y agoYou should be careful with your estimation. The events should be independent to apply those properties but it is very common that one cause can influence many factors, so they are not independent and all the beauty math does not work as with independence. In the worst day, all fail, because one resource can block others and the system get strangled. There is the black swan book when one rare event make the financial market realize what is risk.
- srean 1y agoA load-balancer transparently sitting in front of the api end-point (not an uncommon scenario) usually decouples things well enough to be practically independent. That said, silloncito's warning does need to be paid heed. While independence is essential for the proof to go through, the relationships need not break catastrophically with break of independence, usually it is graceful degradation with degree of independence. There are however specific, often degenerate, theoretical edge cases where the degradation is rapid.
- jerf 1y ago3blue1brown has a walkthrough of this: https://www.youtube.com/watch?v=IaSGqQa5O-M https://www.youtube.com/watch?v=IaSGqQa5O-M
- stared 1y agoBeware - 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 https://www2.math.upenn.edu/~wilf/gfology2.pdf).
- deleted 1y ago[deleted]
- eliben 1y agoIndeed, generating functions are mentioned in a footnote :) Very interesting topic
- stared 1y agoSaw 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 https://arxiv.org/abs/1009.1031).
- srean 1y agoOoh! Lovely. Thank you. Generating functions, Z-transforms are indispensable in probability theory, Physics, signal processing, and now it seems for a good round of Mafia while camping with friends.
- esafak 1y agoI tip my hat to the person who invented that.
- nayuki 1y agoYou 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 1y ago[deleted]
- kazinator 1y agoNot 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 The remainder is -5, which gives us a -5/(x + 2) term: Thus 5 = 2x + 1 - ----- x + 2 How about something we know divides: x + 1 _______________ x + 1 | x^2 + 2x + 1 x^2 + x -------- x + 1 x + 1 ----- 0