Prerequisites

Prerequisites#

This subject will build on a wide range of topics. It will require very little detailed knowledge of any one particular subject. We will draw most heavily on some fundamental concepts of probability and on Taylor Series (at \(x=0\)).

The sort of calculations we do with PGFs are very different from calculations that traditionally occur in mathematics. For that reason, some people say that they seem like magic. We do a few simple manipulations of a function, and suddenly we claim to have a deep conclusion about some seemingly completely unrelated concept. Because we do fundamentally different types of calculations, we are typically not building on deep results of any particular field of mathematics, rather we will use relatively `shallow’ results across a wide range of fields.

Essential#

The ideas below are essential in that we will assume you know these and will not review them in any detail. It is fine if they are not immediately fresh in your mind as long as you can refresh it before you start.

  • Basic Probability: We will use some introductory concepts from probability. If \(\mathbb{P}(X)\) is the probability that event \(X\) happens:

    • You should understand what we mean by:

      • mutually exclusive events. What are \(\mathbb{P}(A \text{ and } B)\) and \(\mathbb{P}(A \text{ or } B)\) in terms of \(\mathbb{P}(A)\) and \(\mathbb{P}(B)\) if \(A\) and \(B\) are mutually exclusive? (intuitively, think about rolling a single die, what is the probability of rolling 1 and 2 in a single roll? what is the probability of rolling 1 or 2?, how would this change if the die were weighted?)

      • independent events: What is \(\mathbb{P}(A \text{ and } B)\) if \(A\) and \(B\) are independent? What is the probability of at least one of \(A\) and \(B\) happening? (again with a die analogy, rolling two dice of different colors, what is the probaiblity the blue one has \(3\) and the orange one has \(4\)? What is the probability that the blue one has \(3\) and/or the orange one has \(4\)?)

    • You should recognize that your friend has made a calculation error if he says:

      • \(\mathbb{P}(A) = -0.5\).

      • \(\mathbb{P}(A) = 1.5\).

      • The total probability of all possible mutually exclusive events is \(0.5\).

    • You should be able to calculate the average of many rolls of a weighted die based on knowing the probability of each outcome.

  • Polynomial manipulations:

    • You should be able to identify the coefficient of \(x^k\) in the product or sum of two polynomials without having to do the entire sum or product.

  • Taylor Series:

    • You should be able to find the Taylor Series of a function \(f(x)\) given the values of \(f(0)\), \(f'(0)\), \ldots.

    • The Taylor series of \(1/(1-x)\) is the geometric series

    \[ \frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots \]

  • Complex Analysis or Fourier Series:

    • \(e^{i\theta} = \cos(\theta) + i \sin(\theta)\)

    • \(e^{ni\theta} = \cos(n\theta) + i \sin(n\theta)\)

  • Differential equations:

    • If the probability of some event \(A\) is \(p_A(t)\) and the probability is being increased at rate \(\alpha(t)\) and reduced at rate \(\beta(t)\) then

    \[ \frac{d}{dt} p_A(t) = \alpha(t) - \beta(t) \]

    • Given a proposed function \(p_A(t)=f(t)\), you should be able to check if \(f(t)\) satisfies the differential equation.

  • Graph Theory:

    • A directed graph is a collection of nodes connected by directed edges.

    • A tree is a graph with no cycles/loops

    • A rooted, directed tree is a tree formed by having a “root” node, and all edges in the tree are directed away from the root node.

  • Some basic biological concepts:

    • Cancer is a result of a cell that begins to divide in a way it shouldn’t.

    • An infectious disease spreads by a pathogen produced in one individual entering another and beginning to reproduce within the new individual.

    • For a species to invade a region, one or more must be introduced to the region and it must begin to reproduce.

Less Essential#

These topics will be reviewed when they come up, but you have likely seen them before.

  • Binomial Theorem for positive integer exponents:

    \[ (x+y)^n = x^n + \binom{n}{1} x^{n-1}y + \binom{n}{2} x^{n-2}y^2 + \cdots + \binom{n}{n-1} x y^{n-1} + y^n \]
Contents