Stochastic Processes

Stochastic Processes

Stochasitc processes certainly sound like mysterious and abstract things that no one in the real world could possibly care about. In fact, they're neither mysterious nor are they mere abstract jibber jabber. In fact, they are critical to our understanding of how many everyday things work.

First, how do you pronounce stochastic, anyway? Well, it's sto-KAS-tik. It comes from the Greek word stokhastikos, meaning "able to guess." In Greek stokhos refers to a stick meant for archers to shoot at. So, stochastic processes are those whose outcomes we can't know but can guess at. It turns out we can often make pretty good guesses.

More formally, stochastic processes are systems that change over time and that include random components.

Okay, that's more jibber jabber. At the most basic level, though, these kinds of systems are something anyone can understand. In fact, we experience at least one stochastic process every time we go shopping and make a purchase.

Examples

When you shop and want to make a purchase, you need to check out. This is true whether it's online at Amazon or in the grocery store. From a systems perspective, both are pretty much the same, but it's easier to visualize the grocery store so that's where we'll start, with check-out queues.

Anytime there's a queue, there's a stochastic process. Checking out at a grocery store involves a queue, or a line, at the check-out lane. There are a limited number of "servers"--check-out lanes. Customers arrive to be "served" (check out) at random times. They have random amounts of stuff in their carts. The "service time" (the time it takes any customer to check out) is random, partly due to the random stuff in their carts, but maybe due to other factors like price checks. The average waiting-time (time spent in line waiting to check out) can be a big factor in cusotmer satisfaction, but having too many servers (check-out lanes) can be cost-prohibitive.

The process of checking out is a stochastic process. It involves waiting in line, getting served, waiting while getting served, and other factors. The process takes place over time. The number of people waiting in line, and the average time they wait, can change over time. Stochastic processes is the study of how such systems evolve over time.

Check-out lanes in a grocery store are a simple, everyday example of a stochastic process, but there are dozens of queues we use every day. Calls arriving at a phone switch are another example. The switch can only handle so many calls at a time (equivalent to the number of check-out lanes at the store), calls arrive randomly, and calls last random amounts of time. On holidays (Thanksgiving, for example), incoming calls can exceed the capacity of the switch and no calls get through.

Remember last fall there was a "supply" problem at the ports? Ships were waiting offshore for a dock where they could unload their cargoes. This is just like the check-out lanes at the grocery store, with ships replacing shoppers, their cargoes replacing the carts, and the docks replacing the check-out lanes. Add to this process the decision of how to schedule the ships--is first-come-first-served like at the grocery store the best, or some other means? This problem got resolved fairly quickly, but it involved understanding how the various more-or-less random components interacted, including scheduling priorities, and where and how to tweak them to break up the bottleneck.

A similar problem arose in the build-up to Desert Storm. We suddenly had a massive influx of supplies and personnel to Saudi Arabia that overwhelmed the ports and airports. Again, this is more or less like the grocery store example. One of my former students applied stochastic processes to speed up the process and help eliminate the bottlenecks.

Airplanes circling an airport waiting for a landing slot are another example. Same issues, same general kind of analysis, except that the average waiting time is critical. You don't want airplanes running out of fuel while they wait!

Traffic patterns on freeways are another problem, this one is similar to the packet-switched networks that the internet uses. Each vehicle is like a "packet." It arrives and departs at limited "servers" (interchanges) while it travels (on the freeway for vehicles, on backbone fiber for the internet). One characteristic of these kinds of networks is that the packets (vehicles or the bits of your Netflix video) tend to bunch up, which slows them down. This is due in part to limitations imposed by the bandwidth (for example, the number of lanes on the turnpike). Balancing traffic and bandwidth becomes an important issue, and one that has implications beyond just the efficiency of the network.

The "bunching up" I mentioned is even evident on every-day turnpikes. An example I'm personally familiar with is the ninety-mile stretch of turnpike joining Tulsa and Oklahoma City. There are a limited number of interchanges on this turnpike, and almost all of the traffic arrives and departs at the two metropolitan areas. The "bunching up" is most evident as the traffic approaches either end. That's not because there's more traffic entering the turnpike at these ends--there's not. It's because it takes about that long for the traffic entering at the opposite end to bunch up. If the cities were twice as far apart, we'd still see the traffic bunching up at about the seventy-mile point. Recently the state expanded the last twenty miles of the turnpike at the Tulsa end to six lanes, three in each direction. This transition from four to six lanes has alleviated the bunching up as traffic approaches Tulsa from OKC. I don't know if this is serendipidous or by design, but it's an observable effect.

Elevators in a high-rise hotel are another, more complex example You may have noticed that the elevators seem to be synchronized, arriving at closely similar times on the same floor and moving in the same direction. That's a long-term consequence of how this kind of queue generally operates. No matter where the elevators start in the morning, they wind up more or less synchronized by early evening.

What stochastic processes studies

In all of the above examples, several things interact. At the most basic level, there's the infrastructure. That's the number of check-out lanes, the capacity of the switch, the number of docks at the port, and so on. Then there's the rules about how the infrastructure and the customers interact (customers being the shoppers in a grocery store, cars on a turnpike, airplanes in holding patterns, etc.). In the case of a grocery store, the manager might open a new check-out lane whenever there's a certain number of customers backed up at existing lanes, for example. The turnpike might change speed limits (minimumm and maximum) to tweak clustering patterns. Airport controllers might have priority rules on which planes get served as opposed to first-come-first-served. The same is true in the logistical problems at a port, whether it's in Saudi Arabia or Long Beach. Understanding how these interactions work gives engineers an opportunity to find cost-effective ways to improve the efficiency of the operation, i.e., reduce the average waiting time.

The study of stochastic processes includes the theoretical examination of this kind of interaction over time. How the process evolves over time is one of the main things that stochastic processes study, including the long-term or asymptotic behavior of random systems.

These examples are things we experience, directly or indirectly, every day. By tweaking various components of the system, engineers can reduce or eliminate bottlenecks while at the same time maintaining affordable and effective systems. Understanding stochastic processes and, in particular, how they evolve over time, is a critical part of this design process. Often it's not the infrastructure (number of check out lanes, number turnpike lanes, number of docks, bandwidth) but rather how the traffic gets scheduled that is the critical factor. The scheduling rules often determine the long-term behavior of the system, which is why the abstract study of stochastic processes is important.

The devil is in the details. Or God. Take your pick.

For more jibber jabber, see