Poisson Process: Definition and Characteristics

The Poisson Process

• A Poisson process, denoted as {N(t): t ≥ 0}, counts the number of arrivals in the time interval (0, t].
• It's characterized by rate λ > 0.
• N(0) = 0, meaning the process starts with no arrivals.
• The number of arrivals during disjoint time intervals are independent, shown through Independent increments.
• The number of arrivals in any interval of length t follows a Poisson distribution with mean λt. For all s, t ≥ 0: P(N(t+s) - N(s) = n) = e^(-λt) * (λt)^n / n!, for n = 0, 1, ...
• Sample paths of the Poisson process are right continuous with left limits.

Poisson Process: Characteristics

• For a Poisson process with rate λ, the expected number of arrivals at time t is E[N(t)] = λt.
• The variance of the number of arrivals at time t is Var[N(t)] = λt.
• Independent increments imply that the process has no memory.
• With a time-varying arrival rate λ(t), the process is called a non-homogeneous Poisson process, and P(N(t+s) - N(s) = n) = e^(-∫s^(t+s) λ(u) du) * (∫s^(t+s) λ(u) du)^n / n!, for n = 0, 1, ...

Interarrival Times & Memory

• Let T₁ be the time of the first arrival, and Ti the elapsed time between the (i-1)th and the ith arrival.
• The sequence {Ti, i = 1, 2, ...} represents the interarrival times.
• The interarrival times Ti, i = 1, 2, ... of a Poisson process with rate λ are i.i.d. exponential random variables with parameter λ.
• P(T₁ > t) = P(N(t) = 0) = e^(-λt), indicating T₁ ~ Exp(λ).
• For i > 1: P(Ti > t | T₁ = t₁, ..., T(i-1) = t(i-1)) = P(N(t+t₁+... +t(i-1)) - N(t₁+... +t(i-1)) = 0) = e^(-λt) means Tᵢ ~ Exp(λ) and the {Ti, i = 1, 2, ...} are independent.

Poisson Process Conditional Arrival Time

• Given that N(t) = 1 for a Poisson process {N(t): t≥0} with rate λ, the arrival time is uniformly distributed on (0, t). That is, P(T₁ ≤ s | N(t) = 1) = s/t, for 0 < s < t.
• Derivation: P(T₁ ≤ s | N(t) = 1) = P(T₁ ≤ s, N(t) = 1) / P(N(t) = 1) = P(N(s) = 1, N(t) - N(s) = 0) / P(N(t) = 1) = P(N(s) = 1) * P(N(t) - N(s) = 0) / P(N(t) = 1) = (λse^(-λs) * e^(-λ(t-s))) / (λte^(-λt)) = s/t.

Chapter 4: Applications of Derivatives

4.1 Related Rates

• Related rates analyze how the rates of change of different variables are related within a given scenario.

Strategy

• Draw a picture and introduce variables, which is the crucial first step.
• Note down any numerical information that's given to you.
• State clearly what you are being asked to find.
• Establish an equation linking the variables involved.
• Differentiate both sides of the equation with respect to t (time), applying chain rule and other diff. techniques correctly.
• Substitute the given information into the differentiated equation to solve for the rate you want to find.

Example 1: Melting Snowball

• Objective: To find out the rate at which the radius is decreasing.
• Volume is decreasing at 1 cm^3/min, so dV/dt = -1 cm^3/min
• Task: what is dr/dt when r = 10 cm
• Volume of a sphere is V = (4/3)πr^3
• Differentiating gives dV/dt = 4πr^2 (dr/dt)
• From that, dr/dt = -1 / (4π(10^2)) = -1/(400π) cm/min

Example 2: Ladder Sliding Down a Wall

• Goal: Determine how fast the ladder's top is sliding down the wall.
• Given: Ladder is 10 ft long, and dx/dt = 1 ft/s.
• Required: Find dy/dt when x = 6 ft.
• Pythagorean theorem: x^2 + y^2 = 10^2.
• Implicit differentiation yields 2x(dx/dt) + 2y(dy/dt) = 0.
• Substituting and simplifying, we obtain dy/dt = -(x/y)(dx/dt).
• When x=6, y = sqrt(100-36) = 8
• So dy/dt = -(6/8)(1) = -3/4 ft/s.

Example 3: Water Tank

• Objective: Find the water level's rate of increase.
• Tank is shaped as an inverted cone with base radius 2 m and height 4 m
• Water pumped in at 2 m^3, so dV/dt = 2 m^3/min.
• Task: what is dh/dt when h = 3 m?

Example 3: Solution

• Need an equation to link V and h
• By similar triangles, r/h = 2/4, so r = h/2.
• Cone volume is V = (1/3) * pi * r^2 * h = (1/3) * pi * (h/2)^2 * h = (pi/12)h^3
• Diff wrt t gives dV/dt = (pi/4)h^2 * dh/dt
• From that, dh/dt = (4/pi) * (1/h^2) * dV/dt = (4/pi) * (1/3^2) * 2 = 8/(9pi) m/min.

Algorithmic Complexity

• Algorithmic complexity measures the resources (time and memory) an algorithm requires to solve a problem.
• It facilitates comparison and forecasts scalability with larger inputs.
• It enables optimization by identifying performance bottlenecks and better use of resources.

Time & Space Complexity

• Time complexity refers to the computation time taken by algorithm, as a function of the input size. Evaluated on Best/Average/Worst cases.
• Space complexity refers to the amount of memory, both auxiliary & total, required by algorithm
• In practice, time complexity is measured far more often

Big O Notation

• Big O notation describes a function's limiting behavior as its argument approaches a specific value or infinity.
• Used to classify algorithms based on how runtime or space needs grow relative to input size.
• O(1) Constant
• O(log n) Logarithmic
• O(n) Linear
• O(n log n) Log-linear
• O(n^2) Quadratic
• O(n^3) Cubic
• O(2^n) Exponential
• O(n!) Factorial
• The dominant term determines the complexity. Constant factors and lower-order components are ignored.

Big O Example

• Example code snippet:

    def find_max(arr):
    max_value = arr # O(1)
    for i in range(1, len(arr)): # O(n)
        if arr[i] > max_value: # O(1)
            max_value = arr[i] # O(1)
    return max_value # O(1)

• Time complexity is O(n) because it involves single loop through the N items in the array.
• Space complexity is O(1) because it only uses fixed amount of extra memory regardless of N.

Sequence Alignment

• Core task in bioinformatics, supporting homology inference, structure prediction, and motif finding.
• Aligning two sequences involves inserting spaces in each to achieve equal length without aligning two spaces.
• Uses a scoring function to rate alignment quality based on matches, mismatches, and gaps with assigned scores (+1, -1, -2 respectively). Score(X', Y') = Sum ( s('xi, 'yi))
• Two main types of sequence alignment are global and local.

Needleman-Wunsch Algorithm

• Needleman-Wunsch: A dynamic programming method for optimal global alignment.
• Initialization: Create an (n+1) x (m+1) matrix and initialize the first row/column with gap penalties: F(i, 0) = id and F(0, j) = jd.
• Iteration: fill the matrix using recursive relation F(i, j) = max { F(i-1, j-1) + s(xi, yj), F(i-1, j) + d, F(i, j-1) + d } where s() returns score and d is gap penalty.
• Traceback: trace from F(n, m) to F(0, 0) to find optimal alignment.

Needleman-Wunsch: Details

• It can be computationally expensive for large sequences, requiring O(nm) space.
• Linear-space algorithms like Hirschberg's exist.

Smith Waterman Algorithm

• Algorithm: Dynamic programming, find optimal local alignment between teo sequences
• Initialization
  • F(i, 0) = 0 for all i
  • F(0, j) = 0 for all j
• Fill the matrix F with the following recursive relation
  • F(i, j) = max { F(i-1, j-1) + s(x_i, y_j), F(i-1, j) + d, F(i, j-1) + d, 0}
• Traceback starts from highest score in F, trace back to reach cell w/ score of 0

Global v Local Alignment

Gap Penalties

• Linear gap penalty assigns a constant penalty for each gap. G(r) = const
• Affine Gap Penalty applies a larger penalty for opening a gap and a smaller one for extending it. g(r) = u+v(r-1) , where u is gap opening & v is gap extending penalty.
• Affine penalties are biologically more realistic but increase complexity.

Static Equilibrium - Torque

• Definition of Torque: Torque is the tendency of a force to rotate an object about an axis. It is a vector quantity.
• Magnitude of Torque: Magnitude of Torque = rFsin(theta)
• Direction of Torque: Use the right-hand rule to determine the direction of the torque vector.

Static Equilibrium - Torque

• Net Torque: The net torque on an object is the sum of all the torques acting on it.
• Equilibrium is achieved when an object is not accelerating linearly or rotationally, requiring net force and torque to be zero.
• sum(F) = 0, sum(tau) = 0

Steps to Solve Static Equilibrium Problems

1. Draw a free body diagram (FBD) of the object.
2. Choose a coordinate system and resolve all forces into components.
3. Apply the first condition of equilibrium: $\sum F_x = 0$ and $\sum F_y = 0$.
4. Choose a rotational axis and calculate the torque due to each force.
5. Apply the second condition of equilibrium: $\sum \tau = 0$.
6. Solve the resulting system of equations.

Example (cont)

• Example uses uniform beam w/ length L mass m supported by cable at angle theta. Block of mass M at beam end. Solve for tension in cable and reaction forces at hinge
• Solving involved setting forces at equilibirum, and torques at equilibrium to find variable values.
• Notes:
  • Axis for rotational calculations is arbitary & can be picked to simplified mathematics.
  • Can exert horizontal & vertical forces on the beam
  • Assure consitent units

Python Workbook

• Python3 Intro with Excerises and Solution. Presented in sections: introduction, then howto w/ commands.
• Getting started comes in 2 major ways. Either program file execution, or interactive mode.
• Commands such as arithmetic operations, and variables & naming are provided
• Libaries including math libraries are used
• Provides simple programming exercises with solutions such as helloworld. </h