5 ms·

Adventures in Probability

165 points by kiyanwang 2y ago

vdvsvwvwvwvwv 2y ago
This was a lot of fun. By skipping over the formulaic details and proof and explaining the lay of the land, it makes a good starting point to explore further. Either mathematically or just some python dice rolls. Really good. Same ethos as fast.ai courses. Finally that you can add tbe /3 and /5 to get a /8 distribution makes intuitive semsw to me. / means lambda. This is because if you have people arriving to a train station you could split them by eye colour and there is no reason a particular eye colour cause there to be dependencies. (Assuming spherical cows: families arriving excepted. Assume it is downtown rush hour)
asah 2y ago
I can't help but wonder if real systems have additional (perhaps subtle) signals, which can be provided to a neural network, which then outperforms these simple algorithms. For example, customers arrive at the grocery store in clusters due to traffic lights, schools getting out, etc. Even without direct signals, a NN could potentially pickup on these "rules" given other inputs, e.g. time of day, weather, etc. ?
- vdvsvwvwvwvwv 2y ago
  Lgtm; A NN is literally a probability distribution producer.
- tech_ken 2y ago
  > For example, customers arrive at the grocery store in clusters due to traffic lights, schools getting out, etc. You're kind of just describing seasonality components and exogenous regressors; RNNs do actually function quite well for demand forecasting of this type but even simple models (Holt-Winters or a Bayesian state space model or something) can be really effective
shiandow 2y ago
Poisson processes are neat, they always end up working nicely in ways that many other distributions/processes very much don't. Splitting a Poisson process into two lower rate processes is a neat trick. Even better is that you can do the same to convert a Poisson process into one with a variable rate, provided that rate is lower than the original (original may be variable as well). And the fact that the partial sums of a bunch of exponential distributions results in the same distribution of values as picking Poisson(lambda * time) values uniformly at random is pure magic.
- tmoertel 2y ago
  Another neat property of Poisson processes is that when raced against one another, they win in proportion to their underlying rates. This property is the basis of a clever random sampling algorithm that works well in SQL: SELECT * FROM Population WHERE weight > 0 ORDER BY -LN(1.0 - RANDOM()) / weight LIMIT 100 -- Sample size. For an explanation of how it works, see https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
  - foldU 2y ago
    (author of OP) That post of yours was actually what got me tooling around with this stuff again :) it's a really excellent one
    - tmoertel 2y ago
      Thanks! That was very kind of you to say. Whenever I write stuff like that, I wonder, "Does anyone find this useful?" It helps to hear every once in a while that the answer is sometimes yes.
  - gmfawcett 2y ago
    Nice article!
exmadscientist 2y ago
> I think if I were in charge of presenting this material to students I'd do it by introducing the concept of memorylessness and by showing how good memorylessness is, how many wonderful things you can do with it. And then one day I'd be like, "well, it sure would be nice if we had any distributions like that!" and then whirl around with my piece of chalk to deliver the exciting news that we do. Exactly one, in fact. Incidentally, this also goes for the determinant of a matrix. It's got a lot of neat and desirable properties, and it turns out to be the only thing that does. When it was finally taught to me this way, those weird algorithms we use to compute this seemingly-arbitrary number finally made sense. (And, in fact, this is the easiest way to prove that all those algorithms have to be computing the same seemingly-arbitrary number. Because the algorithms preserve the properties that define The Determinant, and The Determinant is the unique thing that preserves all of those properties, so must those algorithms all be computing The Determinant, no matter how different they might look.) So I can vouch that this style of explanation really does work, at least for people like me.
- AgentMatt 2y ago
  Can you give some examples for algorithms which aren't obviously logically connected but use the determinant for its nice properties?
  - mturmon 2y ago
    Two ways to compute the determinant: 1) product of eigenvalues 2) cofactor expansion (e.g., https://textbooks.math.gatech.edu/ila/determinants-cofactors.html https://textbooks.math.gatech.edu/ila/determinants-cofactors...) The second is the one I was taught first, in the context of linear system solution, but it does not seem obvious that it would be related to the product of eigenvalues. It’s kind of a weird pile of arithmetic manipulations.
- jackthetab 2y ago
  Any sources that discuss this viewpoint wrt the determinant? Seems I'm still at the "seemingly-arbitrary number" stage.
2-3-7-43-1807 2y ago
I doubt that this model of a queue and the processing of its items by overlaying two independent poisson processes is statistically valid (one for items arriving, the other for processing those items). The processing starts only after the respective item arrived in the queue - so it's not independent - and this needs to be modeled accordingly or it requires a proof that this is equivalent to the suggested overlaying approach - that wouldn't be obvious or trivial.
- travisjungroth 2y ago
  It might be trivial if you consider it a window of an infinite process.
  - 2-3-7-43-1807 2y ago
    the infinite process only solves the problem of having a processed event happen before anything to process has entered the queue - as far as I can tell.
- ocular-rockular 2y ago
  As an introduction to the topic it functions very well though. It doesn't matter whether it's valid or not. In fact, I would say that diving immediately into the validity of some bullshit independence assumptions and other nonsense is where you lose most students (it definitely lost me). I think flawed examples lead to a great way of scaffolding towards the "true" nontrivial answer in a teaching setting at least... I am still exceptionally bitter at how I was taught and forced to learn stochastics and it was very much through a purely theoretical, proof driven, abstract lens with very crappy examples that were more of an afterthought... because of course the theory is all you need to make sense of it!
  - 2-3-7-43-1807 2y ago
    This bullshit independence is one of the most fundamental and important concepts of probability theory and that other nonsense is also relevant cause especially with statistics it's easy to concoct a model which only seems to be correct ... but in fact isn't.
alexpotato 2y ago
>my professor projected video of himself writing on a piece of paper before a very large auditorium, and that guy was left-handed, and so his hand would cover his notes for like the entire time and it was impossible to see what he was writing. I only figured out that this was why it was so unpleasant like halfway through the class. So many of my college math classes had some version of this professor who took a fascinating subject like linear algebra, statistics or algorithms and made it into a slog. The fact that most stats is taught by getting students to just memorize random ideas rather than building up a holistic and intuitive view really is a travesty. Also makes sense why so many people, even though they took stats in college, hav e such a poor understanding of probability.
- tiahura 2y ago
  Left-handed I could handle. Opaque accents seem to warrant some sort of consumer protection action by authorities.
- dfxm12 2y ago
  The fact that most stats is taught by getting students to just memorize random ideas rather than building up a holistic and intuitive view really is a travesty. We don't need first principals thinking for every thing. Granted, this comment is a bit vague, so I don't know how exactly you were taught or which type of class we're talking about, but generally, you can accept some axioms in applied mathematics classes. If we're talking the bare minimum classes like in the article (for apparently a business degree), this is likely a general applied prob/stat. Things tend to get more in depth with more advanced pure mathematics courses.
  - bunderbunder 2y ago
    There's a middle path between rote memorization of outcomes, and building everything up from first principles. And I'm guessing it's probably what the parent poster had in mind. A great statistics textbook along these lines is Principles of Statistics by MG Bulmer. It's one of those Dover classic textbooks that you can get for cheap. This book assumes you already know basic calculus and combinatorics. It then goes through a series of practical problems, and shows how you can use calculus or combinatorics to solve them. And, along the way, an intuitive and holistic perspective on statistics begins to form. The overall effect is great. It's a lot like a 3blue1brown video series, only from the 1960s, and with problem sets.
dariosalvi78 2y ago
my Msc thesis in 2004 was about this: a probabilistic model for last-recently used queues, based on poisson processes, for network packets flows. The model worked OK on a couple of datasets I could get at that time. I tried to publish the work but got rejected a couple of times, then I gave up. If anyone wants to read it (even try to publish) I am happy to share it.
sriram_malhar 2y ago
You can't combine rate of arriving with rate of leaving, can you? Leaving is dependent on arriving, so the latter distribution is dependent on the former.
- signa11 2y ago
  little’s law is quite instructive here. assuming that a system is stable, you can.
sidcool 2y ago
How does one know the application of such a Math concept for a particular software problem? I couldn't guess in a million years.
- manvillej 2y ago
  you go to school for it. Stats, applied mathematics, operations research, industrial engineering. I went for industrial engineering. we learned the math as pure math, then the math as free language problems, then how to identify and collect data to identify their attributes, then simulate and verify those processes, then test for variations in the underlying assumptions of those processes. They never really did teach me to code well in a language that was useful, I had to pick that one up myself.
- travisjungroth 2y ago
  Other option as someone who didn’t go to school. Learn a bunch of methods. Learn a bunch of problems. Match them up. “A bunch” is actually a small enough number that brute forcing it works fine. If you have 20 methods in your head, you’re far ahead of most people. You don’t even have to have them in your head. There’s an underutilized technology called a “list” where you just write things down one after another. Go down your list of methods. You’ll be able to throw out 90% of them because of something obvious. You could be up to speed on this in a day of clicking though Wikipedia if you have some stats knowledge. Two days of you don’t. It’s how I did it myself, for whatever that’s worth.
  - vismit2000 2y ago
    Richard Feynman was fond of giving the following advice on how to be a genius. You have to keep a dozen of your favorite problems constantly present in your mind, although by and large they will lay in a dormant state. Every time you hear or read a new trick or a new result, test it against each of your twelve problems to see whether it helps. Every once in a while there will be a hit, and people will say, “How did he do it? He must be a genius!” https://news.ycombinator.com/item?id=40808933 https://news.ycombinator.com/item?id=40808933
manvillej 2y ago
hey this might be a stupid detail in implementation, but if the poisson simulation of arrival and completion are started cold, then random assignment of events could assign a completion before an arrival, or there could be more completions than arrivals? Arrivals should always be greater or equal to completions? Edit: I remembered by stats class. merging poisson distributions requires Independent processes. since start and completion are dependent, its not mathematically valid. but I am an engineer and it works, so whatever

165 points by kiyanwang 2y ago

This was a lot of fun. By skipping over the formulaic details and proof and explaining the lay of the land, it makes a good starting point to explore further. Either mathematically or just some python dice rolls. Really good. Same ethos as fast.ai courses. Finally that you can add tbe /3 and /5 to get a /8 distribution makes intuitive semsw to me. / means lambda. This is because if you have people arriving to a train station you could split them by eye colour and there is no reason a particular eye colour cause there to be dependencies. (Assuming spherical cows: families arriving excepted. Assume it is downtown rush hour)

asah 2y ago

I can't help but wonder if real systems have additional (perhaps subtle) signals, which can be provided to a neural network, which then outperforms these simple algorithms. For example, customers arrive at the grocery store in clusters due to traffic lights, schools getting out, etc. Even without direct signals, a NN could potentially pickup on these "rules" given other inputs, e.g. time of day, weather, etc. ?

vdvsvwvwvwvwv 2y ago
Lgtm; A NN is literally a probability distribution producer.
tech_ken 2y ago
> For example, customers arrive at the grocery store in clusters due to traffic lights, schools getting out, etc. You're kind of just describing seasonality components and exogenous regressors; RNNs do actually function quite well for demand forecasting of this type but even simple models (Holt-Winters or a Bayesian state space model or something) can be really effective

shiandow 2y ago

Poisson processes are neat, they always end up working nicely in ways that many other distributions/processes very much don't. Splitting a Poisson process into two lower rate processes is a neat trick. Even better is that you can do the same to convert a Poisson process into one with a variable rate, provided that rate is lower than the original (original may be variable as well). And the fact that the partial sums of a bunch of exponential distributions results in the same distribution of values as picking Poisson(lambda * time) values uniformly at random is pure magic.

tmoertel 2y ago
Another neat property of Poisson processes is that when raced against one another, they win in proportion to their underlying rates. This property is the basis of a clever random sampling algorithm that works well in SQL: SELECT * FROM Population WHERE weight > 0 ORDER BY -LN(1.0 - RANDOM()) / weight LIMIT 100 -- Sample size. For an explanation of how it works, see https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
- foldU 2y ago
  (author of OP) That post of yours was actually what got me tooling around with this stuff again :) it's a really excellent one
  - tmoertel 2y ago
    Thanks! That was very kind of you to say. Whenever I write stuff like that, I wonder, "Does anyone find this useful?" It helps to hear every once in a while that the answer is sometimes yes.
- gmfawcett 2y ago
  Nice article!

exmadscientist 2y ago

> I think if I were in charge of presenting this material to students I'd do it by introducing the concept of memorylessness and by showing how good memorylessness is, how many wonderful things you can do with it. And then one day I'd be like, "well, it sure would be nice if we had any distributions like that!" and then whirl around with my piece of chalk to deliver the exciting news that we do. Exactly one, in fact. Incidentally, this also goes for the determinant of a matrix. It's got a lot of neat and desirable properties, and it turns out to be the only thing that does. When it was finally taught to me this way, those weird algorithms we use to compute this seemingly-arbitrary number finally made sense. (And, in fact, this is the easiest way to prove that all those algorithms have to be computing the same seemingly-arbitrary number. Because the algorithms preserve the properties that define The Determinant, and The Determinant is the unique thing that preserves all of those properties, so must those algorithms all be computing The Determinant, no matter how different they might look.) So I can vouch that this style of explanation really does work, at least for people like me.

AgentMatt 2y ago
Can you give some examples for algorithms which aren't obviously logically connected but use the determinant for its nice properties?
- mturmon 2y ago
  Two ways to compute the determinant: 1) product of eigenvalues 2) cofactor expansion (e.g., https://textbooks.math.gatech.edu/ila/determinants-cofactors.html https://textbooks.math.gatech.edu/ila/determinants-cofactors...) The second is the one I was taught first, in the context of linear system solution, but it does not seem obvious that it would be related to the product of eigenvalues. It’s kind of a weird pile of arithmetic manipulations.
jackthetab 2y ago
Any sources that discuss this viewpoint wrt the determinant? Seems I'm still at the "seemingly-arbitrary number" stage.

2-3-7-43-1807 2y ago

I doubt that this model of a queue and the processing of its items by overlaying two independent poisson processes is statistically valid (one for items arriving, the other for processing those items). The processing starts only after the respective item arrived in the queue - so it's not independent - and this needs to be modeled accordingly or it requires a proof that this is equivalent to the suggested overlaying approach - that wouldn't be obvious or trivial.

travisjungroth 2y ago
It might be trivial if you consider it a window of an infinite process.
- 2-3-7-43-1807 2y ago
  the infinite process only solves the problem of having a processed event happen before anything to process has entered the queue - as far as I can tell.
ocular-rockular 2y ago
As an introduction to the topic it functions very well though. It doesn't matter whether it's valid or not. In fact, I would say that diving immediately into the validity of some bullshit independence assumptions and other nonsense is where you lose most students (it definitely lost me). I think flawed examples lead to a great way of scaffolding towards the "true" nontrivial answer in a teaching setting at least... I am still exceptionally bitter at how I was taught and forced to learn stochastics and it was very much through a purely theoretical, proof driven, abstract lens with very crappy examples that were more of an afterthought... because of course the theory is all you need to make sense of it!
- 2-3-7-43-1807 2y ago
  This bullshit independence is one of the most fundamental and important concepts of probability theory and that other nonsense is also relevant cause especially with statistics it's easy to concoct a model which only seems to be correct ... but in fact isn't.

alexpotato 2y ago

>my professor projected video of himself writing on a piece of paper before a very large auditorium, and that guy was left-handed, and so his hand would cover his notes for like the entire time and it was impossible to see what he was writing. I only figured out that this was why it was so unpleasant like halfway through the class. So many of my college math classes had some version of this professor who took a fascinating subject like linear algebra, statistics or algorithms and made it into a slog. The fact that most stats is taught by getting students to just memorize random ideas rather than building up a holistic and intuitive view really is a travesty. Also makes sense why so many people, even though they took stats in college, hav e such a poor understanding of probability.

tiahura 2y ago
Left-handed I could handle. Opaque accents seem to warrant some sort of consumer protection action by authorities.
dfxm12 2y ago
The fact that most stats is taught by getting students to just memorize random ideas rather than building up a holistic and intuitive view really is a travesty. We don't need first principals thinking for every thing. Granted, this comment is a bit vague, so I don't know how exactly you were taught or which type of class we're talking about, but generally, you can accept some axioms in applied mathematics classes. If we're talking the bare minimum classes like in the article (for apparently a business degree), this is likely a general applied prob/stat. Things tend to get more in depth with more advanced pure mathematics courses.
- bunderbunder 2y ago
  There's a middle path between rote memorization of outcomes, and building everything up from first principles. And I'm guessing it's probably what the parent poster had in mind. A great statistics textbook along these lines is Principles of Statistics by MG Bulmer. It's one of those Dover classic textbooks that you can get for cheap. This book assumes you already know basic calculus and combinatorics. It then goes through a series of practical problems, and shows how you can use calculus or combinatorics to solve them. And, along the way, an intuitive and holistic perspective on statistics begins to form. The overall effect is great. It's a lot like a 3blue1brown video series, only from the 1960s, and with problem sets.

dariosalvi78 2y ago

my Msc thesis in 2004 was about this: a probabilistic model for last-recently used queues, based on poisson processes, for network packets flows. The model worked OK on a couple of datasets I could get at that time. I tried to publish the work but got rejected a couple of times, then I gave up. If anyone wants to read it (even try to publish) I am happy to share it.

sriram_malhar 2y ago

You can't combine rate of arriving with rate of leaving, can you? Leaving is dependent on arriving, so the latter distribution is dependent on the former.

signa11 2y ago
little’s law is quite instructive here. assuming that a system is stable, you can.

sidcool 2y ago

How does one know the application of such a Math concept for a particular software problem? I couldn't guess in a million years.

manvillej 2y ago
you go to school for it. Stats, applied mathematics, operations research, industrial engineering. I went for industrial engineering. we learned the math as pure math, then the math as free language problems, then how to identify and collect data to identify their attributes, then simulate and verify those processes, then test for variations in the underlying assumptions of those processes. They never really did teach me to code well in a language that was useful, I had to pick that one up myself.
travisjungroth 2y ago
Other option as someone who didn’t go to school. Learn a bunch of methods. Learn a bunch of problems. Match them up. “A bunch” is actually a small enough number that brute forcing it works fine. If you have 20 methods in your head, you’re far ahead of most people. You don’t even have to have them in your head. There’s an underutilized technology called a “list” where you just write things down one after another. Go down your list of methods. You’ll be able to throw out 90% of them because of something obvious. You could be up to speed on this in a day of clicking though Wikipedia if you have some stats knowledge. Two days of you don’t. It’s how I did it myself, for whatever that’s worth.
- vismit2000 2y ago
  Richard Feynman was fond of giving the following advice on how to be a genius. You have to keep a dozen of your favorite problems constantly present in your mind, although by and large they will lay in a dormant state. Every time you hear or read a new trick or a new result, test it against each of your twelve problems to see whether it helps. Every once in a while there will be a hit, and people will say, “How did he do it? He must be a genius!” https://news.ycombinator.com/item?id=40808933 https://news.ycombinator.com/item?id=40808933

manvillej 2y ago

hey this might be a stupid detail in implementation, but if the poisson simulation of arrival and completion are started cold, then random assignment of events could assign a completion before an arrival, or there could be more completions than arrivals? Arrivals should always be greater or equal to completions? Edit: I remembered by stats class. merging poisson distributions requires Independent processes. since start and completion are dependent, its not mathematically valid. but I am an engineer and it works, so whatever