Stats for nerds
4recommend
10mentions
4people
2010–2023years
70% recommend30% neutral
Mentions per year
What Hacker News says
- The one I'm enjoying right now is Introduction to Stochastic Processes by Erhan Cinlar.
- Yes, as in the OP, S curves can be challenging to work with, in particular, to use, say, early in the history of smart phones, to make long term projections from the number of smart phones sold each day for each of the last 30 days.
But there is some good news: The data used can vary, and in some cases good projections can be easier to make. Can see, e.g., for COVID-19 the recent
https://news.ycombinator.com/item?id=22898015
https://news.ycombinator.com/item?id=22897967
https://news.ycombinator.com/item?id=22900104
https://news.ycombinator.com/item?id=22902667
In the third one of those we have that the projection from a FedEx case is the solution to the first order ordinary differential equation initial value problem
y'(t) = k y(t) (b - y(t))
There for data we used y(0) and b. Then we guessed at k. Had we used values of y for the past month, we could have picked a better, likely fairly good, value for k.
Lesson: Fitting an S curve does not have to be terribly bad.
The key here is the b: The S curve of the solution is the logistic curve, and it rises to be asymptotic to b from below. Knowing b helps a LOT! When have b, are no longer doing a projection or extrapolation but nearly just an interpolation -- much better.
For FedEx, the b was the capacity of the fleet. For COVID-19 the b would be the population needed for herd immunity (from recovering from the virus, from therapeutics that confer immunity, and a vaccine that confers immunity).
Knowing b makes the fitting much easier/better. To know b, likely need to look at the real situation, e.g., population of candidate smart phone users, candidate TV set owners, market potential of FedEx (as it was planned at the time), or population needed for herd immunity for the people in some relatively isolated geographic area.
Then in TeX source code, the solution is
y(t) = { y(0) b e^{bkt} \over y(0) \big ( e^{bkt} - 1 \big ) + b}
Can also use a continuous time discrete state space Markov process subordinated to a Poisson process. Here's how that works:
Have some states, right, they are discrete. For FedEx, that would be (i) the number of customers talking about the service and (ii) the number of target customers listening. Then the time to the next customer is much like the time to the next click of a Geiger counter, that is, has exponential distribution, that is, is the time of the next arrival in a Poisson arrival process (e.g., the time of the next arrival at the Google Web site). So at this arrival, the process moves to a new state where we have 1 more current customer and 1 less target customer. Then start again to get the next new customer.
The Markov assumption is that the past and future of the process are conditionally independent given the present state; so that justifies our getting to the next state using only the current state -- given the current state, for predicting the future, everything before that is irrelevant.
What is a Markov process, what satisfies that the Markov assumption, can depend on what we select for the state -- roughly the more we have in the state, the closer we are to Markov. In particular, if we take the whole past history of the process as the state, IIRC every process is Markov. But Markov helps in something like the FedEx application since that state is so simple.
We get to use continuous time since the time to the next change of state is from a Poisson process whose arrival times are the continuum -- that is, we don't have to make time discrete although it is true that the history of the process (one sample path) has state changes only at discrete times.
So, for state change, and for some positive integer n we have some n possible states, then for i, j = 1, 2, ..., n, we can have some p(i,j) which is the probability of jumping from state i to state j, that is, we have an n x n matrix of transition probabilities.
[p(i,j) is the conditional probability of entering state j given that the last state was i.]
For two jumps, square that matrix. Now there is a lot of pretty math -- get some limits and eigenvectors of states, etc. Actually fairly generally there is a closed form solution to the process. Alas, often in practice that closed form is useless because the n and the n x n are so large, maybe n^2 in the trillions. E.g., in a problem I solved for war at sea, there were Red weapons, Blue weapons, on each side some number types and some number of weapons of that type. The states were the combinatorial explosion. Then there were the one on one Red-Blue encounters where one died, the other died, both died, or neither died. The time to an encounter was the next arrival of Poisson processes, also Poisson. Well, that was an example where there was a closed form solution but n and n x n were wildly too large for the closed form solution but running off, say, 500 sample paths via Monte-Carlo was easy to program and fast for the computer. So, sure the software reported the average of the 500 sample paths. On a PC today, my software would be done before could get finger off the mouse button or the Enter key.
This approach is fairly general. And since what I did included attack submarines, SSBN submarines, anti-submarine destroyer ships, long range airplanes, etc., there should be no difficulty building such a model for COVID-19 that included babies, grade school kids, ..., nursing home residents, people at home, people working nearly alone on farms, ....
Back to S curves, IIRC dropping out of the math for the n x n matrix and its powers is an S curve. So, in a broad range of cases, always get an S curve although a different curve depending on, yes, the p(i,j) and the initial state. Uh, when no one is left sick, the Markov process handles that as an absorbing state -- once get there, don't leave.
For the n in the billions, the n x n is really a biggie. So, for the submarine problem I did,
J. Keilson, Green's Function Methods in Probability Theory.
asked "How can you possibly fathom that enormous state space?". That is a good question, and my answer was: "After, say, 5 days, the number of SSBNs left is a random variable. It is bounded. So it has finite variance. So, both the strong and weak laws of large numbers apply. So, run off 500 sample paths, average them, and get the expectation within a gnat's ass nearly all the time. Intuitively, Monte Carlo puts the effort where the action is.". Keilson was offended by "gnat's ass" but liked the math and approved my work for the US Navy. That question and answer are good to keep in mind.
There is more in, say,
Erhan Çinlar, Introduction to Stochastic Processes, ISBN 0-13-498089-1, Prentice-Hall, Englewood Cliffs, NJ, 1975.
For why the arrival times have exponential distribution and why we get a Poisson process, Çinlar has a nice simple, intuitive, useful axiomatic derivation. There is more via the renewal theorem in
William Feller, An Introduction to Probability Theory and Its Applications, Second Edition, Volume II, ISBN 0-471-25709-5, John Wiley & Sons, New York, 1971.
- Evar D. Nering, Linear Algebra and Matrix Linear Algebra and Matrix Theory*
Kenneth Hoffmann And Ray Kunze. Linear Algebra, 2nd Edition, Prentice-Hall, Englewood Cliffs, New Jersey, 1971.
https://www.zuj.edu.jo/download/linear-algebra-2nd-edition-k...
Halmos, Finite Dimensional Vector Spaces
George E. Forsythe and Cleve B. Moler, Computer Solution of Linear Algebraic Systems
Paul R. Halmos, Naive Set Theory, Van Nostrand, Princeton, NJ, 1960.
More has been done since this book, but this book is a gorgeous introduction to axiomatic set theory. So, even people who want to dig into the latest work would do well to have this as the first book. And for people wanting to read any of the more advanced material here, knowledge of this book will be from good to have to important.
https://piazza-resources.s3.amazonaws.com/is25bi6c6o1oh/isv1...
Walter Rudin, Principles of Mathematical Analysis
The third edition is a lot better than the first two.
H. L. Royden, Real Analysis: Second Edition
Beautifully written, elegant, but maybe don't work way too hard on the exercises about upper/lower semi-continuity, and there is a better summary than Littlewood's three principles.
Bernard R. Gelbaum and John M. H. Olmsted, Counterexamples in Analysis
John C. Oxtoby, Measure and Category: A Survey of the Analogies between Topological and Measure Spaces
Walter Rudin, Real and Complex Analysis
Walter Rudin, Functional Analysis
Leo Breiman, Probability
Kai Lai Chung, A Course in Probability Theory, Second Edition
Jacques Neveu, Mathematical Foundations of the Calculus of Probability
Erhan Cinlar, Introduction to Stochastic Processes
J. L. Doob, Stochastic Processes
I. I. Gihman and A. V. Skorohod, The Theory of Stochastic Processes I, II
Donald E. Knuth, The TeX book
Donald E. Knuth, The Art of Computer Programming, Second Edition
Leo Breiman, "Statistical Modeling: The Two Cultures," Statistical Science, Vol. 16, No. 3, 199–231, 2001.
Paul R. Halmos, "The Theory of Unbiased Estimation", Annals of Mathematical Statistics, Volume 17, Number 1, pages 34-43, 1946.
Paul R. Halmos and L. J. Savage, "Application of the Radon-Nikodym Theorem to the Theory of Sufficient Statistics", The Annals of Mathematical Statistics, Volume 20, Number 2 (1949), 225-241.
https://projecteuclid.org/download/pdf_1/euclid.aoms/1177730...
- It's all much easier than that:
It's just the Poisson process, e.g., with a nice chapter in E. Cinlar, Introduction to Stochastic Processes.
Buses come as arrivals. So bus arrivals are a stochastic arrival process where stochastic just means varying randomly over time where, really, the randomly doesn't mean anything, includes deterministic arrivals, that is, known exactly in advance, but also admits any case of unpredictability.
Well, in short, if have a stochastic arrival process with stationary, independent increments, then the arrival process is a Poisson process and there is a number, usually denoted by lambda, so that the times between arrivals are independent, identically distributed random variables with exponential distribution with arrival parameter, the arrival rate, lambda. The stationary means that the probability distribution of the times between arrival does not change over time. The independent increments means that the time from one arrival to the next is independent of all the past history of arrivals.
The exponential distribution has the property, easy to verify with simple calculus, that the conditional expectation of the arrival time given that the arrival time is already greater than some number is the same as the expected arrival time.
So, net, if bus arrivals form a Poisson process, then the time until the next bus arrives is the same after waiting five minutes as not having waited at all.
Cinlar's treatment is nice because it is qualitative, that is, has assumptions that can often be confirmed or believed just intuitively. And we might not believe that bus arrivals meed the assumptions.
This subject can continue with, say, hazard curves for equipment failures and a lot more about Poisson processes.
E.g., the sum of two independent Poisson processes, say, Red buses and Blue buses, assuming that they are Poisson processes, is also a Poisson process with arrival rate the sum of the Red and Blue arrival rates. If randomly throw away some arrivals, then what is left is also a Poisson process with arrival rate adjusted in the obvious way.
In Feller's volume II is the renewal theorem that the sum of independent arrival processes, Poisson or not, with mild assumptions, converges to a Poisson process as the number of processes summed grows. So, if the users of a sufficiently busy Web site act independently with mild assumptions, then the Web site will see arrivals accurately as a Poisson process.
The vanilla Poisson process is Geiger counter clicks.
There is much more to the pure and applied math and applications of Poisson processes.
- > I'm sure that @graycat will scoff at those recommendations, but his reading list would be considered excessively hardcore and time consuming even for a graduate student in math, which I'm assuming you're not.
Probability and stochastic processes based on measure theory are not very popular in the US, even in graduate math departments.
Uh, scoff, scoff. Okay?
The full measure theoretic details of stochastic processes in continuous time can be a bit of a challenge. That topic can be important, e.g., for Brownian motion and stochastic differential equations used in mathematical finance. Of course, there is
Karatzas and Shreve, Brownian Motion and Stochastic Calculus and Chung and Williams, Introduction to Stochastic Integration. And there's much more, especially from Russia and France.
But, otherwise, usually in practice, what people are interested in is either (1) second order stationary stochastic processes, e.g., as in electronic or acoustical signals and noise. There are commonly interested in power spectral estimation, digital filtering, maybe Wiener filtering, the fast Fourier transform, etc. or (2) what is in, say, Cinlar, Introduction to Stochastic Processes.
In Cinlar, for the continuous time case, get a good introduction to the Poisson process (the vanilla arrival process, e.g., like clicks at a Geiger counter, new sessions at a Web site, and much more). Also get what else people are mostly interested in in practice, Markov processes in discrete time with a discrete state space (that is, the values are discrete).
The case of Markov processes in continuous time and discrete state space is not so tough if the jumps are driven by just a Poisson process. But there is still more in Cinlar.
And there are other good texts on stochastic processes.
For (1), look at some of the texts used by EEs. The measure theory approach is in Doob, Stochastic Processes, Loeve, Probability Theory, and several more texts by quite good authors. E.g., without measure theory, can just dive in via Blackman and Tukey, The Measurement of Power Spectra ....
With all these sources, are able to get by without measure theory. Yes, without measure theory, at some places will have to not ask to understand too much and just skip over some details to get back to the applied stuff.
But for measure theory, the Durrett text seems to get a student to that unusually quickly.
For more, at the MIT Web site, there is an on-line course in mathematical finance that avoids measure theory. They want to use the Radon-Nikodym theorem and Ito integration but still avoid measure theory. Uh, the Radon-Nikodym theorem is a generalization of the fundamental theorem of calculus. Once see it, it's dirt simple, but a good proof takes a bit or follow von Neumann's proof that knocks it all off in one stroke (it's in Rudin, Real and Complex Analysis).
- I looked through Downey's book.
(A) Definition of Probability.
As far as I could tell, the book defined probability in only one of two ways:
(1) Relative frequency assuming finitely many trials (page 13) and
(2) Bayesian prior intuitive belief (page 52).
No, here the book is doing readers a disservice.
(B) Exponential Distribution
The 'derivation' of the exponential distribution on page 37:
"I’ll start with the exponential distribution because it is easy to work with. In the real world, exponential distributions come up when we look at a series of events and measure the times between events, which are called inter-arrival times. If the events are equally likely to occur at any time, the distribution of inter-arrival times tends to look like an exponential distribution."
is a bit too vague.
(C) Random.
The book also uses 'random' too frequently, loosely, and unnecessarily. Instead, essentially we can just drop the word 'random' and avoid questions about what 'random' means and if some data is 'truly random'.
For (A), essentially universally in advanced work, there is only one approach:
We have a non-empty set of 'trials'. Then an 'event' is a subset of the set of all trials. The set of all trials is an also an event. The set of all events is closed under countable unions and relative complements. In particular, the empty set is an event.
A 'probability' is a function P from the set of all events to the interval [0,1]. For an event A, P(A) is its probability. The probability of the set of all trials is 1.
P is 'countably additive': For countably infinitely many pair-wise disjoint events A_i, for i = 1, 2, ..., the probability of the the union of the A_i is the sum of the P(A_i).
A 'random variable' X is a function from the set of all trials to the real numbers such that for any real number x the set of all trials w such that X(w) <= x is an event. Usually we suppress the notation of the trials and just write the event X <= x. This is our only use of 'random', and we give no more definition of it.
In practice, essentially any number at all that we observe can be regarded as a random variable. In particular, the number might have been something observed about a person. The statement on page (52) that
"Anything involving people is pretty much off the table."
would be a silly foundation for probability.
For Bayesian and prior beliefs, can regard such a belief as an estimate of a conditional probability where we condition on what we know. E.g., we know a lot about people so that given a person, we can guess that with probability over 99% the person is less than 10 feet tall. This point does not mean that we have a 'Bayesian' foundation for probability. It's better just to drop mention of 'Bayesian'.
The 'distribution' of a random variable X is the function F_X(x) = P(X <= x).
Full details are in any of, say,
Jacques Neveu, 'Mathematical Foundations of the Calculus of Probability', Holden-Day.
Leo Breiman, 'Probability', ISBN 0-89871-296-3, SIAM.
M. Loeve, 'Probability Theory, I and II, 4th Edition', Springer-Verlag.
Kai Lai Chung, 'A Course in Probability Theory, Second Edition', ISBN 0-12-174650-X, Academic Press.
Yuan Shih Chow and Henry Teicher, 'Probability Theory: Independence, Interchangeability, Martingales', ISBN 0-387-90331-3, Springer-Verlag.
Essentially what is going on is that we are defining P as a non-negative real 'measure' with 'total mass 1' as in any of:
Paul R. Halmos, 'Measure Theory', D. Van Nostrand Company, Inc.
H. L. Royden, 'Real Analysis: Second Edition', Macmillan.
Walter Rudin, 'Real and Complex Analysis', ISBN 07-054232-5, McGraw-Hill.
This approach to probability is the one used in essentially all advanced work, e.g.,
Ioannis Karatzas and Steven E. Shreve, 'Brownian Motion and Stochastic Calculus, Second Edition', ISBN 0-387-97655-8.
Jean-Rene Barra, 'Mathematical Basis of Statistics', ISBN 0-12-079240-0, Academic Press.
Early in Neveu can see some ways we get essentially pushed into this foundation for probability.
With this approach, for a random variable X, we define its expectation E[X] as just its integral with respect to measure P in the sense of measure theory. Then essentially by a routine 'change of variable' we can get E[X] as an integral in terms of the distribution F_X and the measure it defines on the reals.
With this approach, if, say, for some positive integer n we measure the height of n people, then we say that we have the values of the n random variables
X_1, X_2, ..., X_n
and do not say that we have the values of n trials of one random variable X.
Indeed, with this approach, all our experience, all of the universe, is only one trial.
Given a set of events, we can define what it means for the set to be 'independent'. And we can proceed similarly for random variables.
Then we can give a more careful statement of the central limit theorem and also state the law of large numbers. We can also say why we use an average to estimate an expectation, e.g., as in
Paul R. Halmos, "The Theory of Unbiased Estimation", 'Annals of Mathematical Statistics', Volume 17, Number 1, pages 34-43, 1946.
On page 12 there is:
"The mean of this sample is 100 pounds, but if I told you 'The average pumpkin in my garden is 100 pounds,' that would be wrong, or at least misleading. In this example, there is no meaningful average because there is no typical pumpkin."
No: An 'average' does not have to be 'typical' to be 'meaningful'. The expectation of the weight X of a pumpkin in the garden remains meaningful. And the law of large numbers will still apply.
For the exponential distribution, there is a good 'qualitative' derivation: If we have arrivals where the inter-arrival times are stationary and independent, then the inter-arrival times are independent and have the same exponential distribution. Good details are early in the chapter on Poisson processes in
Erhan Cinlar, 'Introduction to Stochastic Processes', ISBN 0-13-498089-1, Prentice-Hall.
Downey's book places a lot of emphasis on distributions, e.g., Weibull, and descriptions, e.g., skewness. So an implication is, given some data, we should try to find its distribution and various summary properties of it, but usually this is unpromising. It is good to have the concept of a distribution but, given some data, usually not good to try to find its distribution. Instead, we get our results by manipulating the data in ways where we need to know little or nothing about the distribution.
The strong emphasis on hypothesis testing is curious. There is more in:
E. L. Lehmann, 'Testing Statistical Hypotheses', John Wiley and Sons.
E. L. Lehmann, 'Nonparametrics: Statistical Methods Based on Ranks', ISBN 0-8162-4994-6.
Downey's book mentioned the chi-square distribution: The main point is that if X_1, X_2, ..., X_k are random variables with Gaussian distribution with mean 0 and variance 1, then
Y = X_1^2 + X_2^2 + ... + X_k^2
has chi-squared distribution with k degrees of freedom.
Downey's book mentioned the variance of a finite population; while variance is of high interest, the variance of a finite population is not. What is usually wanted is an estimate of variance, and for that the formula in the book should be dividing by n - 1 instead of n; this change yields an 'unbiased' estimate.
It would be good for students to get at least an intuitive understanding of the most powerful hypothesis testing via the Neyman-Pearson result: Using an analogy from real estate investing, regard the false alarm rate as money to be spent and spend the money to get the best return on investment buy buying the property with the highest ROI first, then the one with the second highest, etc. Yes, in principal this process leads to a knapsack problem which is NP-complete. Likely the nicest proof of the Neyman-Pearson result is from the Hahn decomposition; this follows from the Radon-Nikodym result with a famous proof by von Neumann in Rudin.
The mention of 'resampling' is curious: There are cases where we won't have independent random variables but will have 'exchangeable' random variables, and exchangeability can be enough.
One example is extending nonparametric tests to multidimensional data and using it for anomaly detection in server farms and networks where multidimensional data is ubiquitous, e.g.,
N. B. Waite, "A Real-Time System-Adapted Anomaly Detector", 'Information Sciences', volume 115, April, 1999, pages 221-259.
Related
Statistics of random processes
1 recommend · 2
A Course in Probability Theory
3 recommend · 11
Brownian motion and stochastic calculus
3 recommend · 10
Probability
5 recommend · 11
Controlled Markov processes
1 recommend · 10
Linear statistical inference and its applications
1 recommend · 10
