Birth and Assassination Stochastic Process

Type of Activity

This is a multi-week project that could be used as an extended homework assignment.

Outline of Scientific Context

The birth-and-assassination process is a variation of a birth and death process in which the clock which counts down the time until a particles death does not start ticking until the particle's parent dies. This process was proposed by Aldous and Krebs. The idea goes as follows:

We consider the special case where the killing distribution is an exponential distribution with intensity kappa.

The birth and assassination process is motivated by two applications:

  1. Database queuing system: This process is used to study the behavior of queuing system for a data base that blocks multiple queries from modifying the same entry simultaneously. In this system, the arrival times of jobs follow a Poisson process, the service times are independent and identically distributed, and there are infinitely many servers. A job is a descendant of another job is it is blocked by it (or is a descendant of a job blocked by it).
  2. Scotching a rumor in a network: This process represents the dynamics of a rumor spreading on the vertices of a graph along its edges. A vertex may be unaware of the rumor, aware of the rumor and spreading it as true, or aware of the rumor and trying to stop it. (Charles Bordenave has shown it is equivalent to the birth and death process in an asymptotic sense.)

Computational Topics Covered

This assignment is a simulation study. It covers, random number generation, computer experiments, response surface exploration, function writing, profiling code, data structures.

Computational Learning Objectives

Prerequisite Computational Topics

Target Audience

Undergraduates who have had some probability. The project can be extended for graduate students.

Breakdown of Computational Tasks


Some information that you may find useful about the Poisson process:

One approach

Cautionary Notes

The following are questions that students posted on the class discussion board.

Question: Can someone clarify what the "parentID" and "childID" refer to? Does "parentID" refer to that person's parents? Or a number that refers to him/herself? If the latter, then should every parent have a different number?
Response: All people in the same generation should have a unique id - an integer from 1 to the number of people in that generation is fine.
The row/record for a person should have a parent ID, the identifier for their parent, and a personID. So childID is a bit of a misnomer. It should be parentID and personID. Thes IDs need to be unique within a generation, but do not need to be unique across generations.

Question: Do I use rpois one time to determine the number of children, and a second time to determine the birthdays of each child?
I'm also not sure what I am supposed to use runif for.

Response: rpois should give the number of kids and hence the number of birthdays you need to generate
I believe runif is used for the birthdays-

runif (number of birthdays you're generating, birth of parent, death of parent)

Question: Is it possible to coerce a list of numbers with varying row lengths into a numeric vector? I've managed to do this only by catenating each row of the list together (eg. if g is a list of 3 items -> x=c(g[[1]],g[[2]],g[[3]]) ) but I haven't figured out how to write that into a function.
Any tips?

Response: Here are a couple of approaches:

unlist(g) - will turn a list into a vector

for (i in 1:length(g)) {

  code to successively catenate each element of g into a new vector

Question: I am stuck as to how we are supposed to run various simulations for kappa and lambda. Are we supposed to use some sort of r random generator function to obtain values.
Response: kappa and lambda should be arguments in your overall function. you can provide different values and see what happens to the birth and assassination process.

Question: So I've created the head of the family and I made another dataframe that generates his children and all their information (birthtime, death time, number, parent). Everything follows the right distributions (hopefully). The problem is that I have no idea how to create further generations, since I can't figure out a way to only index certain parent IDs and have them create offspring who create offspring.
Response: What I did was I started with the first parent in generation 3 (assuming there is at least one parent). I found the number of kids the first parent had, each childs' parentID (which is one), their birth date, their assassination date, and their childID. Then, I used a for loop to do the same for any other parents in this generation and their kids (if they had any).

Plus lots of questions about control flow.

Ways to Extend the Topic

Other Directions

Similar Exercises/Projects

  • Ad hoc networks
  • BML car model and phase transition.
  • "Beat the CLT".
  • Random Number Generation
  • Grading Suggestions

    We have specified the function name, arguments, and output format in order to test the code programmatically. In addition, we require students to writeup their findings from the response surface exploration.