John von Neumann and stochastic simulations

source: Monte Carlo method (Wikipedia)

John von Neumann was one of the genuine mathematical geniuses of the twentieth century. A particularly interesting window onto von Neumann's scientific work is provided by George Dyson in his  book, Turing's Cathedral: The Origins of the Digital Universe. The book is as much an intellectual history of the mathematics and physics expertise of the Princeton Institute for Advanced Study as it is a study of any one individual, but von Neumann plays a key role in the story. His contribution to the creation of the general-purpose digital computer helped to lay the foundations for the digital world in which we now all live.

There are many interesting threads in von Neumann's intellectual life, but one aspect that is particularly interesting to me is the early application of the new digital computing technology to the problem of simulating large complex physical systems. Modeling weather and climate were topics for which researchers sought solutions using the computational power of first-generation digital computers, and the research needed to understand and design thermonuclear devices had an urgent priority during the war and post-war years. Here is a description of von Neumann's role in the field of weather modeling in designing the early applications of ENIAC  (P. Lynch, "From Richardson to early numerical weather prediction"; link):

John von Neumann recognized weather forecasting, a problem of both great practical significance and intrinsic scientific interest, as ideal for an automatic computer. He was in close contact with Rossby, who was the person best placed to understand the challenges that would have to be addressed to achieve success in this venture. Von Neumann established a Meteorology Project at the Institute for Advanced Study in Princeton and recruited Jule Charney to lead it. Arrangements were made to compute a solution of a simple equation, the barotropic vorticity equation (BVE), on the only computer available, the ENIAC. Barotropic models treat the atmosphere as a single layer, averaging out variations in the vertical. The resulting numerical predictions were truly ground-breaking. Four 24-hour forecasts were made, and the results clearly indicated that the large-scale features of the mid-tropospheric flow could be forecast numerically with a reasonable resemblance to reality. (Lynch, 9)

image: (link, 10)

A key innovation in the 1950s in the field of advanced computing was the invention of Monte Carlo simulation techniques to assist in the invention and development of the hydrogen bomb. Thomas Haigh, Mark Priestley, and Crispin Rope describe the development of the software supporting Monte Carlo simulations in the ENIAC machine in a contribution to the IEEE Annals of the History of Computing (link). Peter Galison offers a detailed treatment of the research communities that grew up around these new computational techniques (link). Developed first as a way of modeling nuclear fission and nuclear explosives, these techniques proved to be remarkably powerful for allowing researchers to simulate and calculate highly complex causal processes. Here is how Galison summarizes the approach:

Christened "Monte Carlo" after the gambling mecca, the method amounted to the use of random, numbers (a la roulette) to simulate the stochastic processes too complex to calculate in full analytic glory. But physicists and engineers soon elevated the Monte Carlo above the lowly status of a mere numerical calculation scheme; it came to constitute an alternative reality--in some cases a preferred one--on which "experimentation" could be conducted. (119) 

At Los Alamos during the war, physicists soon recognized that the central problem was to understand the process by which neutrons fission, scatter, and join uranium nuclei deep in the fissile core of a nuclear weapon. Experiment could not probe the critical mass with sufficient detail; theory led rapidly to unsolvable integro-differential equations. With such problems, the artificial reality of the Monte Carlo was the only solution--the sampling method could "recreate" such processes by modeling a sequence of random scatterings on a computer. (120)

The approach that Ulam, Metropolis, and von Neumann proposed to take for the problem of nuclear fusion involved fundamental physical calculations and statistical estimates of interactions between neutrons and surrounding matter. They proposed to calculate the evolution of the states of a manageable number of neutrons as they traveled from a central plutonium source through spherical layers of other materials. The initial characteristics and subsequent interactions of the sampled neutrons were assigned using pseudo-random numbers. A manageable number of sampled spaces within the unit cube would be "observed" for the transit of a neutron (127) (10^4 observations). If the percentage of fission calculated in the sampled spaces exceeded a certain value, then the reaction would be self-sustaining and explosive. Here is how the simulation would proceed:

Von Neumann went on to specify the way the simulation would run. First, a hundred neutrons would proceed through a short time interval, and the energy and momentum they transferred to ambient matter would be calculated. With this "kick" from the neutrons, the matter would be displaced. Assuming that the matter was in the middle position between the displaced position and the original position, one would then recalculate the history of the hundred original neutrons. This iteration would then repeat until a "self-consistent system" of neutron histories and matter displacement was obtained. The computer would then use this endstate as the basis for the next interval of time, delta t. Photons could be treated in the same way, or if the simplification were not plausible because of photon-matter interactions, light could be handled through standard diffusion methods designed for isotropic, black-body radiation. (129)

Galison argues that there were two fairly different views in play of the significance of Monte Carlo methods in the 1950s and 1960s. According to the first view, they were simply a calculating device permitting the "computational physicist" to calculate values for outcomes that could not be observed or theoretically inferred. According to the second view, Monte Carlo methods were interpreted realistically. Their statistical underpinnings were thought to correspond exactly to the probabilistic characteristics of nature; they represented a stochastic view of physics.

King's view--that the Monte Carlo method corresponded to nature (got "back of the physics of the problem") as no deterministic differential equation ever could--I will call stochasticism. It appears in myriad early uses of the Monte Carlo, and clearly contributed to its creation. In 1949, the physicist Robert Wilson took cosmic-ray physics as a perfect instantiation of the method: "The present application has exhibited how easy it is to apply the Monte Carlo method to a stochastic problem and to achieve without excessive labor an accuracy of about ten percent." (146)

This is a very bold interpretation of a simulation technique. Rather than looking at the model as an abstraction from reality, this interpretation looks at the model as a digital reproduction of that reality. "Thus for the stochasticist, the simulation was, in a sense, of apiece with the natural phenomenon" (147).

One thing that is striking in these descriptions of the software developed in the 1950s to implement Monte Carlo methods is the very limited size and computing power of the first-generation general-purpose computing devices. Punch cards represented "the state of a single neutron at a single moment in time" (Haigh et al link 45), and the algorithm used pseudo-random numbers and basic physics to compute the next state of this neutron. The basic computations used third-order polynomial approximations (Haigh et al link 46) to compute future states of the neutron. The simulation described here resulted in the production of one million punched cards. It would seem that today one could use a spreadsheet to reproduce the von Neumann Monte Carlo simulation of fission, with each line being the computed result from the previous line after application of the specified mathematical functions to the data represented in the prior line. So a natural question to ask is -- what could von Neumann have accomplished if he had Excel in his toolkit? Experts -- is this possible?

Computational models for social phenomena

There is a very lively body of work emerging in the intersection between computational mathematics and various fields of the social sciences. This emerging synergy between advanced computational mathematics and the social sciences is possible, in part, because of the way that social phenomena emerge from the actions and thoughts of individual actors in relationship to each other. This is what allows us to join mathematics to methodology and explanation. Essentially we can think of the upward strut of Coleman’s boat — the part of the story that has to do with the “aggregation dynamics” of a set of actors — and can try to create models that can serve to simulate the effects of these actions and interactions.

source: Hedstrom and Ylikoski (2010) "Causal Mechanisms in the Social Sciences" (link)

 

Here is an interesting example in the form of a research paper by Rahul Narain and colleagues on the topic of modeling crowd behavior ("Aggregate Dynamics for Dense Crowd Simulation", link). Here is their abstract:

Large dense crowds show aggregate behavior with reduced individual freedom of movement. We present a novel, scalable approach for simulating such crowds, using a dual representation both as discrete agents and as a single continuous system. In the continuous setting, we introduce a novel variational constraint called unilateral incompressibility, to model the large-scale behavior of the crowd, and accelerate inter-agent collision avoidance in dense scenarios. This approach makes it possible to simulate very large, dense crowds composed of up to a hundred thousand agents at near- interactive rates on desktop computers.

Federico Bianchi takes up this intersection between computational mathematics and social behavior in a useful short paper called "From Micro to Macro and Back Again: Agent-based Models for Sociology" (link). His paper focuses on one class of computational models, the domain of agent-based models. Here is how he describes this group of approaches to social explanation:

An Agent-Based Model (ABM) is a computational method which enables to study a social phenomenon by representing a set of agents acting upon micro-level behavioural rules and interacting within environmental macro-level (spatial, structural, or institutional) constraints. Agent-Based Social Simulation (ABSS) gives social scientists the possibility to test formal models of social phenomena, generating a virtual representation of the model in silico through computer programming, simulating its systemic evolution over time and comparing it with the observed empirical phenomenon. (1) 

 And here is how he characterizes the role of what I called "aggregation dynamics" above:

Solving the complexity by dissecting the macro-level facts to its micro-level components and reconstructing the mechanism through which interacting actors produce a macro-level social outcome. In other words, reconstructing the micro-macro link from interacting actors to supervenient macrosociological facts. (2)

Or in other words, the task of analysis is to provide a testable model that can account for the way the behaviors and interactions at the individual level can aggregate to the observed patterns at the macro level.

Another more extensive example of work in this area is Gianluca Manzo, Analytical Sociology: Actions and Networks. Manzo's volume proceeds from the perspective of analytical sociology and agent-based models. Manzo provides a very useful introduction to the approach, and Peter Hedstrom and Petri Ylikoski extend the introduction to the field with a chapter examining the role of rational-choice theory within this approach. The remainder of the volume takes the form of essays by more than a dozen sociologists who have used the approach to probe and explain specific kinds of social phenomena.

Manzo provides an account of explanation that highlights the importance of "generating" the phenomena to be explained. Here are several principles of methodology on this topic:

• P4: in order to formulate the "generative model," provide a realistic description of the relevant micro-level entities (P4a) and activities (P4b) assumed to be at work, as well as of the structural interdependencies (P4c) in which these entities are embedded and their  activities unfold;
• P5: in order rigorously to assess the internal consistency of the "generative model" and to determine its high-level consequences, translate the "generative model" into an agent-based computational model;
• P6: in order to assess the generative sufficiency of the mechanisms postulated, compare the agent-based computational model's high-level consequences with the empirical description of the facts to be explained (9)

So agent-based modeling simulations are a crucial part of Manzo's understanding of the logic of analytical sociology. As agent-based modelers sometimes put the point, "you haven't explained a phenomenon until you've shown how it works on the basis of a detailed ABM." But the ABM is not the sole focus of sociological research, on Manzo's approach. Rather, Manzo points out that there are distinct sets of questions that need to be investigated: how do the actors make their choices? What are the structural constraints within which the actors exist? What kinds of interactions and relations exist among the actors? Answers to all these kinds of question are needed if we are to be able to design realistic and illuminating agent-based models of concrete phenomena.

Here is Manzo's summary table of the research cycle (8). And he suggests that each segment of this representation warrants a specific kind of analysis and simulation.

This elaborate diagram indicates that there are different locations within a complex social phenomenon where different kinds of analysis and models are needed. (In this respect the approach Manzo presents parallels the idea of structuring research methodology around the zones of activity singled out by the idea of methodological localism; link.) This is methodologically useful, because it emphasizes to the researcher that there are quite a few different kinds of questions that need to be addressed in order to successfully explain a give domain of phenomena.

The content-specific essays in the volume focus on one or another of the elements of this description of methodology. For example, Per-Olof Wikstrom offers a "situational action theory" account of criminal behavior; this definition of research focuses on the "Logics of Action" principle 4b.

People commit acts of crime because they perceive and choose (habitually or after some deliberation) a particular kind of act of crime as an action alternative in response to a specific motivation (a temptation or a provocation). People are the source of their actions but the causes of their actions are situational. (75)

SAT proposes that people with a weak law-relevant personal morality and weak ability to exercise self-control are more likely to engage in acts of crime because they are more likely to see and choose crime as an option. (87)

Wikstrom attempts to apply these ideas by using a causal model to reproduce crime hotspots based on situational factors (90).

The contribution of Gonzalez-Bailon et al, "Online networks and the diffusion of protest," focuses on the "Structural Interdependency" principle 4c.

One of the programmatic aims of analytical sociology is to uncover the individual-level mechanisms that generate aggregated patterns of behaviour.... The connection between these two levels of analysis, often referred to as the micro-macro link, is characterised by the complexity and nonlinearity that arises from interdependence; that is, from the influence that actors exert on each other when taking a course of action. (263)

Their contribution attempts to provide a basis for capturing the processes of diffusion that are common to a wide variety of types of social behavior, based on formal analysis of interpersonal networks.

Networks play a key role in diffusion processes because they facilitate threshold activation at the local level. Individual actors are not always able to monitor accurate the behavior of everyone else (as global thresholds assume) or they might be more responsive to a small group of people, represented in their personal networks. (271)

They demonstrate that the structure of the local network matters for the diffusion of an action and the activation of individual actors.

In short, Analytical Sociology: Actions and Networks illustrates a number of points of intersection between computational mathematics, simulation systems, and concrete sociological research. This is a very useful effort as social scientists attempt to bring more complex modeling tools to bear on concrete social phenomena.