Channel Capacity and Discrete Memoryless Channels

Lecture 19: Channel Capacity

• Channel capacity is the maximum amount of information that can be reliably transmitted over a channel, with arbitrarily small error probability.
• Memoryless channels are considered.

Discrete Memoryless Channel (DMC)

• Defined by conditional probabilities $p(y|x)$, where $x \in \chi$, $y \in \gamma$.
• $\chi$ is the input alphabet, $\gamma$ is the output alphabet.
• Memoryless: $p(y_1, y_2, \dots y_n|x_1, x_2, \dots x_n) = \prod_{i=1}^{n} p(y_i|x_i)$.

Channel Capacity Formula

• $C = \max_{p(x)} I(X;Y)$ bits per transmission.
• The maximum is taken over all possible input distributions $p(x)$.
• C is a fixed property of the channel.

Binary Symmetric Channel (BSC)

• Binary input and output.
• Probability of error: p.
• $p(y=0|x=0) = p(y=1|x=1) = 1-p$
• $p(y=0|x=1) = p(y=1|x=0) = p$
• $I(X;Y) = H(Y) - H(Y|X) = H(Y) - H(p)$
• $H(Y) \le 1$, $H(p)$ is fixed.
• $H(Y)$ is maximized when $Y$ is uniform, i.e., $p(y=0) = p(y=1) = 1/2$
• $p(y=0) = (1-p)\alpha + p(1-\alpha)$ where $\alpha = p(x=0)$.
• Achieved $p(y=0) = 1/2$ by setting $\alpha = 1/2$.
• For $p(x=0) = p(x=1) = 1/2$, $I(X;Y) = 1 - H(p)$.
• $C = 1 - H(p)$ bits.

Lecture 15: October 24, 2023 - Geometry of Linear Programs

Introduction

• Review of the geometry of linear programs.

Reading

• Section 4.7

Example 1

• Maximizing $x_1 + x_2$ subject to constraints.
• Constraints include $4x_1 - x_2 \le 8$, $2x_1 + x_2 \le 10$, $-5x_1 + 6x_2 \le 30$, $x_1, x_2 \ge 0$
• Feasible region is a five-sided polygon.
• Vertices are $(0, 0), (2, 0), (3, 4), (0, 5), (60/34, 30/34)$.
• Optimal solution is found with the vertex $(3, 4)$ as objective value $3 + 4 = 7$.

Vertices

• Standard form LP: maximize $c^T x$, subject to $Ax = b$, $x \ge 0$.
• $A \in \mathbb{R}^{m \times n}$ has rank $m$.
• A vector $x \in \mathbb{R}^n$ is a basic solution if $Ax = b$, and $m$ indices $B(1), ..., B(m)$ which includes:
  • The columns $A_{B(1)},..., A_{B(m)}$ are linearly independent.
  • If $i \notin {B(1),..., B(m)}$, then $x_i = 0$.
• The columns $A_{B(1)},..., A_{B(m)}$ are called the basis.
• Let $B = (A_{B(1)},..., A_{B(m)})$ be the $m \times m$ matrix formed by the basis columns, then $x_B = B^{-1}b$.
• A vector $x \in \mathbb{R}^n$ is a basic feasible solution if $x$ is a basic solution and $x \ge 0$.

Algoritmos de Busca

Busca não informada (Uninformed Search)

• Do not have information about the search space beyond that inherent in the definition of the problem.
• Apply a fixed strategy.

Busca em Largura (BFS - Breadth-First Search)

• All nodes at a level are expanded before any node at the next level.
• Implementation: queue (FIFO).
• Complete: Yes (if the branching factor b is finite).
• Optimal: Yes (if the cost is 1 per step).
• Time complexity: $O(b^d)$.
• Space complexity: $O(b^d)$.

Busca de Custo Uniforme (Uniform Cost Search)

• Expand the lowest cost node g(n).
• Implementation: priority queue.
• Complete: Yes (if the cost is greater than a positive value $\epsilon$).
• Optimal: Yes.
• Time complexity: $O(b^{\lceil C*/\epsilon \rceil})$.
• Space complexity: $O(b^{\lceil C*/\epsilon \rceil})$.

Busca em Profundidade (DFS - Depth-First Search)

• Expand the deepest node in the current frontier.
• Implementation: stack (LIFO).
• Complete: No (fails in spaces with infinite depth, may enter a loop).
• Optimal: No.
• Time complexity: $O(b^m)$.
• Space complexity: $O(bm)$.

Busca com Profundidade Limitada (Depth-Limited Search)

• Depth-first search with a depth limit l.
• Complete: Yes, if l $\ge$ d.
• Optimal: No.
• Time complexity: $O(b^l)$.
• Space complexity: $O(bl)$.

Busca em Aprofundamento Iterativo (IDS - Iterative Deepening Search)

• Executes a sequence of depth-limited searches with increasing limits.
• Complete: Yes.
• Optimal: Yes, if the cost is 1 per step.
• Time complexity: $O(b^d)$.
• Space complexity: $O(bd)$.

Busca Informada (Heurística - Informed Search (Heuristic))

• Use problem-specific knowledge to guide the search.
• Heuristic function h(n): estimate of the cost of a path from node n to a goal node.

Busca Gulosa (Greedy Search)

• Expand the node that seems to be closest to the goal.
• Evaluated using the heuristic: h(n) (lowest estimated cost to the goal).
• Implementation: priority queue.
• Complete: No (may enter loops).
• Optimal: No.
• Time complexity: $O(b^m)$.
• Space complexity: $O(b^m)$.

Busca A* (A* Search)

• Minimizes the total path cost: $f(n) = g(n) + h(n)$.
  • g(n) = cost to reach node n.
  • h(n) = estimated cost from node n to the goal.
• Implementation: priority queue.
• Complete: Yes (unless there are infinite nodes with $f \le f(G)$).
• Optimal: Yes.
• Time complexity: $O(b^m)$.
• Space complexity: $O(b^m)$.

Fonction Exponentielle

Définition

• La fonction exponentielle, notée $exp(x)$ ou $e^x$, est l'unique fonction définie et dérivable sur $\mathbb{R}$.
  • $f'(x) = f(x)$ pour tout $x \in \mathbb{R}$
  • $f(0) = 1$

Propriétés

• $e^0 = 1$
• $e^1 = e \approx 2.718$
• $e^{a+b} = e^a \cdot e^b$
• $e^{a-b} = \frac{e^a}{e^b}$
• $e^{-x} = \frac{1}{e^x}$
• $(e^a)^b = e^{ab}$
• $e^x > 0$ pour tout $x \in \mathbb{R}$

Limites

• $\lim_{x \to +\infty} e^x = +\infty$
• $\lim_{x \to -\infty} e^x = 0$
• $\lim_{x \to +\infty} \frac{e^x}{x} = +\infty$
• $\lim_{x \to -\infty} xe^x = 0$
• $\lim_{x \to 0} \frac{e^x - 1}{x} = 1$

Dérivée

• La dérivée de $e^x$ est $e^x$.
• Si $u(x)$ est une fonction dérivable, alors la dérivée de $e^{u(x)}$ est $u'(x)e^{u(x)}$.

Variations

• La fonction exponentielle est strictement croissante sur $\mathbb{R}$.

Représentation Graphique

• La représentation graphique de la fonction exponentielle est une courbe croissante qui passe par le point $(0, 1)$. Elle s'approche de l'axe des abscisses lorsque $x$ tend vers $-\infty$, et tend vers $+\infty$ lorsque $x$ tend vers $+\infty$.

Bernoulli's Principle

• Bernoulli's principle states that for an inviscid flow, an increase in the speed of the fluid occurs simultaneously with a decrease in pressure or a decrease in the fluid's potential energy.
• The principle was discovered by Daniel Bernoulli in the 18th century.

How Wings Generate Lift

• Airplane wings are designed to direct air to travel faster over the top of the wing than under the wing.
• Faster moving air exerts less pressure.
• The air moving over the top of the wing exerts less pressure than the air moving under the wing.
• The higher pressure from below pushes the wing up, creating lift.

Airfoil

• The cross-sectional shape of a wing is called an airfoil.

Pressure and Velocity

• Faster-moving fluids exert less pressure.

Lift

• The upward force on a wing caused by the pressure difference between the top and bottom of the wing is called lift.

Air Pressure

• The force exerted by the weight of air on a surface.

Parts of an Airplane

• A: Wing
• B: Fuselage
• C: Empennage (Tail)
• D: Engine
• E: Cockpit
• F: Propeller

The Poisson Process

Definition

• $N(t)$ counts the number of events that occur in the interval $[0, t]$.
• A counting process ${N(t), t \geq 0}$ is a Poisson process with rate $\lambda > 0$ if:
  • $N(0) = 0$
  • Independent increments
  • The number of events in any interval of length $t$ is Poisson with mean $\lambda t$.
• $P{N(t+s) - N(s) = n} = e^{-\lambda t} \frac{(\lambda t)^n}{n!}, \quad n = 0, 1, \dots$

Interarrival Times

• $T_i$ is the time between event $i-1$ and event $i$.
• The interarrival times $T_1, T_2, \dots$ are i.i.d. exponential random variables with parameter $\lambda$.
• $T_i \sim Exp(\lambda), \quad i = 1, 2, \dots$

Properties

• If $N_1(t)$ and $N_2(t)$ are independent Poisson processes with rates $\lambda_1$ and $\lambda_2$, then $N_1(t) + N_2(t)$ is a Poisson process with rate $\lambda_1 + \lambda_2$.
• Conditional on $N(t) = n$, the $n$ event times are distributed as $n$ independent uniform random variables on $[0, t]$.

Nonhomogeneous Poisson Process

• A counting process ${N(t), t \geq 0}$ is a nonhomogeneous Poisson process with rate function $\lambda(t), t \geq 0$ if:
  • $N(0) = 0$
  • Independent increments
  • $P{N(t+h) - N(t) = 1} = \lambda(t)h + o(h)$
  • $P{N(t+h) - N(t) \geq 2} = o(h)$
• $o(h)$ is a function such that $\lim_{h \rightarrow 0} \frac{o(h)}{h} = 0$.

Mean Value Function

• The mean value function is given by:
  • $m(t) = \int_0^t \lambda(s) ds$
• The number of events in the interval $(s, t]$ is Poisson distributed with mean $m(t) - m(s)$:
  • $P{N(t) - N(s) = n} = e^{-(m(t) - m(s))} \frac{(m(t) - m(s))^n}{n!}, \quad n = 0, 1, \dots$

Lecture 14: Sequential Estimation

Definition (Sequential Estimation)

• Estimator is sequential if the number of observations $n$ is not fixed in advance, but is determined by the observations as they are taken.

Definition (Stopping Rule)

• A stopping rule is a criterion for deciding when to stop sampling, based on the observations.

Theorem

• Let $X_1, X_2,...$ be i.i.d. random variables with density $f(x;\theta)$, $\theta \in \Omega$.
• Let $\hat{\theta}_n = \hat{\theta}_n(X_1,..., X_n)$ be a sequence of estimators.
• If $N$ is a stopping rule, then ${\hat{\theta}_n, N}$ is a sequential estimation procedure.

Example

• $X_1, X_2,... \stackrel{iid}{\sim} Bernoulli(p)$, $p \in (0,1)$.
• $N = \min{n: \sum_{i=1}^n X_i = r }$, $r \geq 1$ is fixed.
• $N \sim NB(r, p)$. Estimator of $p$ given $N = n$ is $\hat{p}_n = \frac{r}{n}$.
• $E[\hat{p}_n] = E[\frac{r}{N}] = r E[\frac{1}{N}]$.
• $E[\frac{1}{N}] \neq \frac{1}{E[N]}$, then $\hat{p}_n$ is biased.
• $\lim_{r \to \infty} \hat{p}_n = p$, then $\hat{p}_n$ is consistent.

Definition (Sufficient Statistics)

• A statistic $T(\mathbf{X})$ is sufficient for $\theta$ if the conditional distribution of the sample $\mathbf{X}$ given $T(\mathbf{X})$ does not depend on $\theta$.

Theorem (Factorization Theorem)

• $f(\mathbf{x}; \theta)$ denotes the joint p.d.f. or p.m.f. of the sample $\mathbf{X} = (X_1,..., X_n)$.
• A statistic $T(\mathbf{X})$ is sufficient for $\theta$ if and only if there exist functions $g(t, \theta)$ and $h(\mathbf{x})$ such that for all $\mathbf{x}$ and $\theta$: $f(\mathbf{x}; \theta) = g(T(\mathbf{x}), \theta) h(\mathbf{x})$.

Properties of Sufficient Statistics

• If $T(\mathbf{X})$ is a sufficient statistic for $\theta$, then any one-to-one function of $T(\mathbf{X})$ is also a sufficient statistic for $\theta$
• If $T(\mathbf{X})$ is a sufficient statistic for $\theta$, then the maximum likelihood estimator (MLE) of $\theta$ is a function of $T(\mathbf{X})$

Theorem

• If $T(\mathbf{X})$ is a sufficient statistic for $\theta$, then any estimator based on $T(\mathbf{X})$ will have a smaller variance than any estimator not based on $T(\mathbf{X})$

Pressure Drop Correlations

Friction Factor

• Laminar Flow (Re $\leq$ 2100):

  • $f = \frac{16}{Re}$

• Turbulent Flow (Re > 4000):

  • Smooth Tubes (Blasius): $f = 0.0791 Re^{-0.25}$
  • Smooth Tubes (Nikuradse): $\frac{1}{\sqrt{f}} = 2.0 \ log (Re \sqrt{f}) - 0.8$
  • Rough Tubes (Nikuradse): $\frac{1}{\sqrt{f}} = 1.74 - 2.0 \ log (\frac{\epsilon}{D})$
  • Colebrook: $\frac{1}{\sqrt{f}} = -2.0 \ log (\frac{\epsilon}{3.7D} + \frac{2.51}{Re \sqrt{f}})$
  • Swamee-Jain: $f = \frac{0.25}{[log (\frac{\epsilon}{3.7D} + \frac{5.74}{Re^{0.9}})]^{2}}$

Pressure Drop

• $\Delta P = f \frac{L}{D} \frac{\rho V^{2}}{2}$
  • f = Fanning friction factor
  • L = Length of pipe
  • D = Diameter of pipe
  • $\rho$ = Density of fluid
  • V = Average velocity of fluid

Reynolds Number

• $Re = \frac{D V \rho}{\mu}$
  • D = Diameter of pipe
  • V = Average velocity of fluid
  • $\rho$ = Density of fluid
  • $\mu$ = Viscosity of fluid

Darcy Friction Factor

• $f_{Darcy} = 4f_{Fanning}$

Notes

• $\epsilon$ = roughness of the pipe
• Use consistent units.
• Empirical correlations have limitations.
• The Moody chart is a graphical representation of the Colebrook equation.

Lecture 14: Data Models

Data Model

• A set of concepts to describe the structure of a database.
• The operations for manipulating structures, and constraints that the database should obey.
  • Structure: Data types, relationships, and constraints
  • Operations: For specifying database retrievals and updates
  • Constraints: Rules that data must adhere to

Categories of Data Models

• Conceptual (high-level, semantic) data models: Concepts close to how users perceive data.
• Physical (low-level, internal) data models: Describe details of how data is stored.
• Implementation (representational) data models: Balance user views with computer storage.

Data Model Schema vs. Instance

• Schema: The description of a database.
  • Includes data element descriptions, relationships, and constraints.
• Instance: The actual data stored in a database at a moment in time.
• Database systems support multiple schemas:
  • Database schema: The overall design.
  • External schema: User views.
  • Conceptual schema: Logical structure.
  • Internal schema: Physical storage structure.

Data Independence

• The capacity to change the schema at one level without changing the schema at the next higher level.
• Two Types:
  • Logical Data Independence: Change conceptual schema without changing external schemas.
  • Physical Data Independence: Change internal schema without changing the conceptual schema.
• When is a schema at a lower level changed, only the mapping between these and higher levels schemas needs to be changed.

Database Languages

• Data Definition Language (DDL): Used by designers to define each database schema (e.g., SQL).
• Data Manipulation Language (DML): Used to specify database retrievals and updates (i.e., "Query language").
  • High-level (Non-procedural) DML: Specify what data is needed (e.g., SQL).
  • Low-level (Procedural) DML: Specify how to get the data. Rarely used directly.

Database System Architecture

• Centralized Database Systems: Use a single computer site, all functions are performed on one machine.
• Client/Server Database Systems: Specialized servers with specialized functions, clients can access the servers via SQL.
  • Two-Tier Architecture: The application resides at the client, directly invoking database access.
  • Three-Tier Architecture: The application server resides between the client and database server.
  • Benefits include increased security, improved concurrency, and simpler updates.

Classification of Database Management Systems

• Based on the data model: Relational, object-oriented, object-relational, hierarchical, network.
• Based on the number of users: Single-user, multi-user.
• Based on the number of sites: Centralized, distributed.
• Based on the purpose: General-purpose, special-purpose.

Entity-Relationship (ER) Model

• ER Model: A popular high-level conceptual data model.
• ER diagrams: a graphical notation for representing ER model.

ER Model Concepts

• Entity: A "thing" with independent existence.
• Attribute: Property of an entity or a relationship type.
• Relationship: Association among two or more entities.

Entities

• Entities are represented by a set of attributes. Key attribute's value is distinct for each individual entity in the entity set
• Entity Set: A set of entities of the same type.
• Each entity set has a key attribute.

Attributes

• Simple vs. Composite attributes. Composite attributes can be divided into smaller subparts.
• Single-valued vs. Multi-valued attributes. An employee can have multiple college degrees.
• Stored vs. Derived attributes. The value of derived attributes can be derived from other attributes.

Relationship Types

• Relationship Type R among n entity types $E_1, E_2,..., E_n$: a set of associations among entities from these entity types.
• Relationship Set: The current set of relationship instances represented in the database.

Relationship Degree

• Degree of a relationship type: The number of participating entity types.
  • Unary relationship: degree is one.
  • Binary relationship: degree is two.
  • Ternary relationship: degree is three.

Cardinality Constraints

• Cardinality ratio for binary relationships.
  • Specifies the maximum number of relationship instances that an entity can participate in.
  • one-to-one (1:1).
  • one-to-many (1:N).
  • many-to-one (N:1).
  • many-to-many (M:N).
• Participation constraint: Total participation (existence dependency).
  • Partial participation.

Weak Entity Types

• An entity that does not have a key attribute of its own.
• Identified by being related to another entity type (identifying owner).
• Identifier of a weak entity is the combination of:
  • Partial key of the weak entity.
  • Key of the identifying owner entity.

ER Diagram Notation

• Entities are represented as rectangles.
• Attributes are represented as ovals.
• Relationships are represented as diamonds.
• Entity sets are connected to relationship sets via straight lines.
• Multi-valued attributes are represented as double ovals.
• Derived attributes are represented as dashed ovals.
• Composite attributes are represented as ovals with ovals inside.
• Weak entity types are represented as double rectangles.
• Identifying relationship types are represented as double diamonds.
• Total participation is represented as a double line connecting the entity type to the relationship type.
• Cardinality ratios are written on each line connecting entity sets to the relationship set. 1, N, M.