Name: Introduction to stochastic processes
ISBN: 9780134980898

What Hacker News says

graycatApr 2025

Stochastic process with the Markov property: Past and future are conditionally independent given the present. The general version of conditionally independent is from probability theory based on measure theory and the Radon-Nikodym theorem (with von Neumann's novel proof in Rudin, Real and Complex Analysis), but an easier introduction is in Erhan Çınlar, Introduction to Stochastic Processes.

In a Poisson process the time until the next event has the Poisson distribution and, thus, from a simple calculus manipulation, is a Markov process.

E.g., time from now until a molecule of hydrogen peroxide H2O2 decomposes to water and oxygen is independent of when it was made from water and oxygen. That is the basis of half life, the same distribution until decomposition starting now no matter when the chemical or particle was created.

In WWII, searching at sea, e.g., for enemy submarines, was important, and then was Bernard O. Koopman, Search and Screening, 1946 with an argument that time to an encounter between two ships had a Poisson distribution, i.e., was a Markov process.

In grad school, there was a question about how long US submarines would last in war at sea. Well, take n Red ships and m Blue ships with, for each ship, position, speed, and detection radius and, for each Red-Blue pair, given a detection, probabilities of Red dies, Blue dies, both die, neither die (right, these four have to be non-negative and add to 1). Now have specified a Markov process that can evaluate with a relatively simple Monte-Carlo simulation.

Had written a random number generator in assembler using an Oak Ridge formula, typed quickly, and did the simulation. Had a review by a famous probability prof and passed when explained how the law of large numbers applied. So, some pure and applied math and computing worked, but some politics didn't!

thread

empyrrhicistJan 2023

The one I'm enjoying right now is Introduction to Stochastic Processes by Erhan Cinlar.

thread

graycatOct 2022

The quote from the article in Encyclopedia of Biostatistics is awash in undefined terminology sometimes about peripheral issues.

Clean, logical, all terms well defined and explained, with plenty of advanced content, is in (with some markup using TeX)

Erhan \c Cinlar, {\it Introduction to Stochastic Processes,\/} ISBN 0-13-498089-1, Prentice-Hall, Englewood Cliffs, NJ, 1975.\ \

The author was long at Princeton. He is a high quality guy.

As I was working my way through grad school in a company working on US national security, a question came up about the survivability of the US SSBN fleet under a special scenario of global nuclear war but limited to sea. Results were wanted in two weeks. So, I drew from Çinlar's book, postulated a Markov process subordinated to a Poisson process, typed some code into a text editor, called a random number generator I'd written in assembler based on the recurrence

X(n+1) = X(n) 5^15 + 1 mod 2^47

and was done on time.

A famous probabilist was assigned to review my work. His first remark was that there was no way for my software to "fathom" the enormous "state space". I responded, at each time t, the number of SSBNs left is a random variable, finite, with an expectation. So, I generate 500 sample paths, take their average, use the strong law of large numbers, and get an estimate of their expected value within a "gnat's ass" nearly all the time. "The Monte Carlo puts the effort where the action is."

The probabilist's remark was "That is a good way to think of it."

Need to do some work with Markov chains, simulation, etc.? Right, just read some Çinlar, not much in prerequisites (he omitted measure theory), get clear explanations, no undefined terminology, from first principles to some relatively advanced material, and be successful with your project.

thread

graycatApr 2020

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.

thread

graycatApr 2019

E. Cinlar, Introduction to Stochastic Processes

Covers limit theorems and continuous time.

thread

graycatOct 2018

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.

thread