Hypothesis Testing: Power and Error Types

Review of Last Lecture

• Hypothesis testing was previously discussed.
• Significance level $\alpha$ was another key concept.
• P-values play a crucial role in hypothesis testing.
• Type I error (False Positive) involves rejecting $H_0$ when it is actually true.
• Type II error (False Negative) means failing to reject $H_0$ when $H_A$ is true.
• Power is defined as $1 - P(\text{Type II error})$.

Power (Continued)

• Power of a test is the probability of rejecting the null hypothesis when the alternative hypothesis is true.
• Power can be expressed as $1 - P(\text{Type II error}) = P(\text{Reject } H_0 | H_A \text{ is true})$.
• Aim for a high power value in statistical tests
• Power can be increased in three ways:
  • Increase $\alpha$
  • Increase the sample size $n$
  • Increase the effect size

Example Scenario

• Testing if the average rent in SLO (San Luis Obispo) is $2,000.
  • $H_0: \mu = 2000$
  • $H_A: \mu > 2000$
• Assume the true average rent is $2,200.
• Assume that $\sigma = 500$.
• Considering a sample size of $n = 25$ apartments.

Impact of Increasing $\alpha$

• With $\alpha = 0.05$:
  • Reject $H_0$ if $\bar{x} > 2000 + 1.645 \cdot \frac{500}{\sqrt{25}} = 2164.5$
  • Power $= P(\bar{x} > 2164.5 | \mu = 2200) = P(z > \frac{2164.5 - 2200}{500 / \sqrt{25}}) = P(z > -0.355) = 0.639$
• With $\alpha = 0.1$:
  • Reject $H_0$ if $\bar{x} > 2000 + 1.282 \cdot \frac{500}{\sqrt{25}} = 2128.2$
  • Power $= P(\bar{x} > 2128.2 | \mu = 2200) = P(z > \frac{2128.2 - 2200}{500 / \sqrt{25}}) = P(z > -0.718) = 0.764$
• Increasing $\alpha$ leads to an increase in power.

Impact of Increasing Sample Size $n$

• With $\alpha = 0.05$ and $n = 25$, Power $= 0.639$.
• With $\alpha = 0.05$ and $n = 100$:
  • Reject $H_0$ if $\bar{x} > 2000 + 1.645 \cdot \frac{500}{\sqrt{100}} = 2082.25$
  • Power $= P(\bar{x} > 2082.25 | \mu = 2200) = P(z > \frac{2082.25 - 2200}{500 / \sqrt{100}}) = P(z > -2.355) = 0.991$
• Increasing $n$ leads to an increase in power.

Impact of Increasing Effect Size

• With $\alpha = 0.05$ and $n = 25$, Power $= 0.639$ when the true average rent is $2,200.
• If the true average rent is $2,300:
  • Reject $H_0$ if $\bar{x} > 2000 + 1.645 \cdot \frac{500}{\sqrt{25}} = 2164.5$
  • Power $= P(\bar{x} > 2164.5 | \mu = 2300) = P(z > \frac{2164.5 - 2300}{500 / \sqrt{25}}) = P(z > -1.355) = 0.912$
• Increasing the effect size increases the power.

T-Tests

• T-tests are needed when population standard deviation $\sigma$ is unknown.
• Estimate $\sigma$ using the sample standard deviation $s$.
• $t = \frac{\bar{x} - \mu}{s / \sqrt{n}}$
• Degrees of freedom $= n - 1$.
• The t-distribution is more spread out than the normal distribution.
• As $n$ increases, the t-distribution approaches the normal distribution.

T-Test Example

• Testing if the average height of Cal Poly students is 5'8" = 68 inches.
  • $H_0: \mu = 68$
  • $H_A: \mu \neq 68$
• Sample $n = 20$ students, $\bar{x} = 70$ inches, and $s = 5$ inches
• Test at $\alpha = 0.05$
• $t = \frac{70 - 68}{5 / \sqrt{20}} = 1.789$
• Degrees of freedom $= 20 - 1 = 19$
• The critical values are $\pm 2.093$
• Fail to reject the null hypothesis since $1.789 < 2.093$.
• Conclusion: there is not enough evidence to suggest that the average height of Cal Poly students differs from 5'8".

Chapter 3 - The Relational Model

Introduction

• Used to represent databases.

Advantages

• Simple structure
• Easy to use
• Mathematical foundation

Structure of Relational Databases

• Consists of a set of tables.
• Each table has a unique name.
• A table consists of a set of attributes (columns).
• Each attribute has a unique name.
• A tuple (row) is a set of attribute values.

Attribute Types

• Each attribute has an associated domain.
• Domain specifies a set of permitted values.
• Examples include integer, string, date, currency etc.

Database Schema

• Representation of relations within a database.

Keys

• $K \subseteq R$ is a superkey of R if values for K are sufficient to identify a unique tuple of each possible relation r(R)
  • Example: {account_number} is a superkey of account
  • Example: {account_number, branch_name} is a superkey of account
• K is a candidate key if K is minimal
  • Example: {account_number} is a candidate key of account
• One of the candidate keys is selected to be the primary key.
• A foreign key is a set of attributes in a relation schema R1 whose values are required to match one of the candidate keys of relation schema R2.
  • R1 is called the referencing relation
  • R2 is called the referenced relation Example: account.branch_name is a foreign key referencing branch.branch_name

Lecture 16: Dynamic Programming

Fibonacci Numbers

• $F_0 = 0$
• $F_1 = 1$
• $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$
• The first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...
• Problem: Given $n$, compute $F_n$.

Algorithm 1: Recursive algorithm

RecursiveFibonacci(n):
 if n == 0:
 return 0
 if n == 1:
 return 1
 return RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2)

Runtime Analysis:

• $T(0) = T(1) = O(1)$
• $T(n) = T(n-1) + T(n-2) + O(1)$ for $n \geq 2$
• Since $F_n \approx 1.618^n$, the runtime of the recursive algorithm is exponential in $n$.

Algorithm 2: Dynamic programming

DynamicProgrammingFibonacci(n):
 F = new array of size n+1
 F = 0
 F = 1
 for i = 2 to n:
 F[i] = F[i-1] + F[i-2]
 return F[n]

Runtime Analysis

• The runtime of the dynamic programming algorithm is $O(n)$.

Space Analysis

• The space complexity is $O(n)$.

Algorithm 3: Dynamic programming with constant space

DynamicProgrammingFibonacciConstantSpace(n):
 if n == 0:
 return 0
 if n == 1:
 return 1
 F_n_minus_2 = 0
 F_n_minus_1 = 1
 for i = 2 to n:
 F_n = F_n_minus_1 + F_n_minus_2
 F_n_minus_2 = F_n_minus_1
 F_n_minus_1 = F_n
 return F_n

Runtime Analysis

• The runtime of the dynamic programming algorithm is $O(n)$.

Space Analysis

• The space complexity is $O(1)$.

Dynamic Programming Paradigm

• Dynamic programming is a technique for solving optimization problems with overlapping subproblems.

Key idea

• Solve each subproblem only once and store the result in a table.

Four steps to develop a dynamic programming algorithm:

• Define subproblems
• Define recurrence relation
• Solve base cases
• Build table and return solution

Example: Longest Common Subsequence

• Common subsequence is a subsequence that is common to both $X$ and $Y$.
• The longest common subsequence (LCS) is the longest such subsequence.

Problem

• Given two sequences $X = \langle x_1, x_2, \dots, x_m \rangle$ and $Y = \langle y_1, y_2, \dots, y_n \rangle$, find the length of the longest common subsequence of $X$ and $Y$.

Step 1: Define subproblems

• Let $c[i, j]$ be the length of the LCS of $X[1..i]$ and $Y[1..j]$.

Step 2: Define recurrence relation

• $c[i, j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \ c[i-1, j-1] + 1 & \text{if } i, j > 0 \text{ and } x_i = y_j \ \max(c[i-1, j], c[i, j-1]) & \text{if } i, j > 0 \text{ and } x_i \neq y_j \end{cases}$

Step 3: Solve base cases

• $c[i, 0] = 0$ for all $i$
• $c[0, j] = 0$ for all $j$

Step 4: Build table and return solution

LongestCommonSubsequence(X, Y):
 m = length(X)
 n = length(Y)
 c = new array of size (m+1) x (n+1)
 for i = 0 to m:
 c[i, 0] = 0
 for j = 0 to n:
 c[0, j] = 0
 for i = 1 to m:
 for j = 1 to n:
 if X[i] == Y[j]:
 c[i, j] = c[i-1, j-1] + 1
 else:
 c[i, j] = max(c[i-1, j], c[i, j-1])
 return c[m, n]

Runtime Analysis

• The runtime is $O(mn)$.

Space Analysis

• The space complexity is $O(mn)$.

Optimal Substructure

• Problem must have optimal substructure to apply dynamic programming.

Definition

• An optimal solution to the problem contains within it optimal solutions to subproblems.