Partial Differential Equations (PDEs)

Partial Differential Equations (PDEs)

• PDEs involve unknown functions of multiple variables and their partial derivatives.
• Example: $\frac{\partial u}{\partial x} + \frac{\partial u}{\partial y} = 0$.

Order of PDE

• The order is determined by the highest derivative in the equation.
• $\frac{\partial u}{\partial x} + \frac{\partial u}{\partial y} = 0$ is a first-order PDE.
• $\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0$ is a second-order PDE.

Linear PDE

• The unknown function and its derivatives appear to the first power only.
• There are no products between the unknown function and/or its derivatives.
• General Form: $a(x, y) \frac{\partial u}{\partial x} + b(x, y) \frac{\partial u}{\partial y} + c(x, y) u = f(x, y)$.

Homogeneous PDE

• All terms contain the unknown function or its derivatives.
• Example: $\frac{\partial u}{\partial x} + \frac{\partial u}{\partial y} + u = 0$.
• The equation is equal to zero.

Linear Homogeneous PDE with Constant Coefficients

• Takes the form: $a \frac{\partial^2 u}{\partial x^2} + b \frac{\partial^2 u}{\partial x \partial y} + c \frac{\partial^2 u}{\partial y^2} = 0$, where a, b, and c are constants.

Important PDEs

• Heat Equation: $\frac{\partial u}{\partial t} = k \frac{\partial^2 u}{\partial x^2}$. Models heat flow or diffusion.
• Wave Equation: $\frac{\partial^2 u}{\partial t^2} = c^2 \frac{\partial^2 u}{\partial x^2}$. Models wave phenomena.
• Laplace's Equation: $\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0$ or $\nabla^2 u = 0$. Describes steady-state phenomena.

Solution Techniques for PDEs

• Separation of Variables: Seeks solutions in the form $u(x, t) = X(x)T(t)$ for linear PDEs.
• Fourier Series: Represents functions as an infinite sum of sines and cosines, useful for solving PDEs with boundary conditions.
• Characteristics: Transforms first-order PDEs into ordinary differential equations along characteristic curves.
• Numerical Methods: Includes techniques like finite difference, finite element, and finite volume methods for approximating solutions.

Light Propagation in Nonlinear Media

Nonlinear Polarization

• In intense light, the polarization P is no longer linear with the electric field E: $\mathbf{P}=\varepsilon_{0}\left(\chi^{(1)} \mathbf{E}+\chi^{(2)} \mathbf{E} \mathbf{E}+\chi^{(3)} \mathbf{E} \mathbf{E} \mathbf{E}+\cdots\right)$
• $\chi^{(1)}$: linear susceptibility
• $\chi^{(2)}$: $2^{\text {nd }}$ order susceptibility, responsible for second harmonic generation (SHG)
• $\chi^{(3)}$: $3^{\text {rd }}$ order susceptibility, responsible for third harmonic generation (THG), self-focusing, etc.

Second Harmonic Generation (SHG)

• Polarization is given by: $\mathbf{P}(t)=\varepsilon_{0}\left[\chi^{(1)} \mathbf{E}(t)+\chi^{(2)} \mathbf{E}^{2}(t)\right]$
• Assuming monochromatic electric field $\mathbf{E}(t)=\mathbf{E}_{0} \cos (\omega t)$, polarization contains term oscillating at $2 \omega$, which generates a new field at $2 \omega$.

Third Harmonic Generation (THG)

• Polarization is given by: $\mathbf{P}(t)=\varepsilon_{0}\left[\chi^{(1)} \mathbf{E}(t)+\chi^{(3)} \mathbf{E}^{3}(t)\right]$
• Assuming monochromatic electric field $\mathbf{E}(t)=\mathbf{E}_{0} \cos (\omega t)$, polarization contains a term oscillating at $3 \omega$, generating a new field at $3 \omega$.

Wave Equation

• Derived from Maxwell's equations: $\nabla^{2} \mathbf{E}-\mu \varepsilon \frac{\partial^{2} \mathbf{E}}{\partial t^{2}}=\mu \frac{\partial^{2} \mathbf{P}_{N L}}{\partial t^{2}}$
• $\mathbf{P}_{N L}$ represents the nonlinear polarization.
• Assuming a monochromatic field $\mathbf{E}(\mathbf{r}, t)=\mathbf{E}(\mathbf{r}) e^{-i \omega t}$ and $\mathbf{P}{N L}(\mathbf{r}, t)=\mathbf{P}{N L}(\mathbf{r}) e^{-i 2 \omega t}$ (for SHG), the wave equation is: $\nabla^{2} \mathbf{E}(\mathbf{r})+\frac{(2 \omega)^{2}}{c^{2}} n^{2}(2 \omega) \mathbf{E}(\mathbf{r})=-\frac{(2 \omega)^{2}}{\varepsilon_{0} c^{2}} \mathbf{P}_{N L}(\mathbf{r})$

Slowly Varying Envelope Approximation

• Assuming a slowly varying electric field $\mathbf{E}(\mathbf{r})=\mathbf{A}(z) e^{i k z}$, where $\mathbf{A}(z)$ is slowly varying and $k=\frac{2 \omega}{c} n(2 \omega)$, the wave equation becomes $\frac{d \mathbf{A}(z)}{d z}=i \frac{\omega}{\varepsilon_{0} n c} \mathbf{P}_{N L}(z) e^{-i k z}$.

Phase Matching

• The intensity of second harmonic field $I_{2 \omega} \propto \frac{\sin ^{2}(\Delta k \cdot L / 2)}{(\Delta k \cdot L / 2)^{2}}$
• $\Delta k=k_{2 \omega}-2 k_{\omega}$ is phase mismatch
• $L$ is length of nonlinear medium
• Phase matching condition needed to maximize the intensity: $\Delta k=k_{2 \omega}-2 k_{\omega}=0$ or $n(2 \omega)=n(\omega)$ (can be achieved using birefringent materials).

Optical Parametric Amplifier (OPA)

• A nonlinear optical process with labels: pump $\omega_{p}$, signal $\omega_{s}$, idler $\omega_{i}$, and nonlinear medium $\chi^{(2)}$.
• Energy conservation: $\omega_{p}=\omega_{s}+\omega_{i}$.
• Momentum conservation (Phase matching): $\mathbf{k}{p}=\mathbf{k}{s}+\mathbf{k}_{i}$.

Algorithmic Trading and Order Book Events

High-Frequency Data

• Granular data view of trading activity.
• Records every message to the exchange.
• Time resolution down to nanoseconds
• Requires specialized tools.

Examples of Order Book Events

• Limit Order: Adds liquidity.
• Market Order: Removes liquidity.
• Cancel Order: Removes liquidity.
• Execute Order: Order is filled.

Order Book

• A list of buy and sell orders for a specific security.
• Orders listed with prices and quantities.
• Constantly updated as orders are placed, canceled, and executed.
• Example:

• The best ask price is 1500.01, and the best bid price is 1499.99. The difference between the best ask and bid prices referred to as the spread.

Order Book Event Information

• Time stamp
• Order ID
• Price
• Size
• Side (buy or sell)
• Type (limit, market, cancel)

Example:

• Example of Limit order to sell 100 shares at a price of 1500.01.
• Example of Market order to buy 200 shares at the best available price
• Example of Cancellation of an order to sell 50 shares at a price of 1500.01.

Algorithmic Trading

• Computer programs to automate trading.
• Used to execute trades at high speeds.
• Used to take advantage of small price discrepancies.

Two Main Categories:

• Execution Algorithms: Execute large orders without affecting price.
• Trading Strategies: Identify and exploit trading opportunities.

Order Book Events and Algorithmic Trading

• Can be used to create algorithmic strategies.
• Simple strategy: buy when bid increases, sell when ask decreases.

Algorithmic Game Theory

Mechanism Design without Money

Social choice setting

• Set of possible outcomes $\Omega$
• Set of $n$ agents
• Each agent $i$ has valuation $v_i : \Omega \rightarrow \mathbb{R}$: valuation function
• $v_i(\omega)$: Value of outcome $\omega$ to agent $i$
• Social choice function $f : V_1 \times V_2 \times... \times V_n \rightarrow \Omega$
• $V_i$: set of possible valuation functions for agent $i$

Definition

A social choice function $f$ is strategyproof if for every agent $i$, every $v_i \in V_i$, and every $v'_i \in V_i$,

$v_i(f(v_i, v_{-i})) \ge v_i(f(v'i, v{-i}))$

• $v_{-i}$: the vector of valuation functions of all agents except $i$

Setting

• $n$ agents (or voters)
• Set $A$ of $m$ alternatives
• Each agent $i$ has a ranking (or preference order) $\succ_i$ over the alternatives
• $\succ_i$: complete, transitive, antisymmetric
• Social choice function $f : (\text{set of all possible rankings})^n \rightarrow A$
• Also called a voting rule

Example: Plurality Rule

Each agent reports his top choice. The alternative that is the top choice of the most agents is selected.

• Not strategyproof

Example: Borda Count

Each agent reports a ranking. If an agent ranks an alternative in $j$-th position, then the alternative gets $m-j$ points. The alternative with the most points in total is selected.

• Not strategyproof

Terminology

• A social choice function is strategyproof (or truthful) if no agent can ever benefit from misreporting his preferences, regardless of what the other agents do.
• A social choice function is onto if for every alternative $a \in A$, there exist rankings of the agents such that $a$ is selected.
• Also called unanimous or citizen sovereign
• A social choice function is a dictatorship if there exists an agent $i$ such that the selected alternative is always the top choice of agent $i$, regardless of the rankings of the other agents.

Gibbard-Satterthwaite Impossibility Theorem

Suppose that there are at least 3 alternatives. Then, every social choice function that is strategyproof and onto is a dictatorship.

Pumping Lemma and Non-Context-Free Languages

• To prove a language is non-regular, the Pumping Lemma is used for regular languages.
• Similarly, a Pumping Lemma can be used for context-free languages (CFLs).

Pumping Lemma for CFLs

• If $A$ is a CFL, then $\exists p \in \mathbb{N}$ such that $\forall s \in A$ with $|s| \geq p$, $s$ can be divided into 5 pieces $s = uvxyz$ such that:
  • For all $i \geq 0$, $uv^ixy^iz \in A$.
  • $|vy| > 0$.
  • $|vxy| \leq p$.
• p is the pumping length.

Using the Pumping Lemma

• Steps to prove that language L is not context-free:
  • Assume L is context-free for contradiction.
  • Let p be the pumping length.
  • Find a string s in L where $|s| \geq p$.
  • Consider all possible ways to divide s into s=uvxyz such that $|vy| > 0$ and $|vxy| \leq p$.
  • Show that for each division, there exists $i \geq 0$ such that $uv^ixy^iz \notin L$.
  • Conclude that L is not context-free.

Example 1

• Proof that $B = {w \in {a, b, c}^* \mid |a|_w = |b|_w = |c|_w }$ is not a CFL. -Assume for contradiction that B is a CFL, and let p be length

  • Choose $s = a^pb^pc^p$; $s \in B$ and $|s| = 3p \geq p$.

• Cases cover division of s=uvxyz

  • Then uv^2xy^2z = a^{p+k}b^pc^p ∉ B because |a| > |b| = |c|.

• Contradiction. Hence B is not a CFL

Example 2

• Proof that $C = {ww \mid w \in {0, 1}^* }$ is not a CFL.
  • Choose $s = 0^p1^p0^p1^p$.
  • Note $s\in C, |s| = 4p \ge p$.
• After several division cases that contradict C, the conclusion is that C is not a CFL