Hypothesis Testing and Analysis

• Study notes on Hypothesis Testing and Analysis of Algorithms
• Study notes in spanish for thesis preparation

Basics of Hypothesis Testing

• Null Hypothesis ($H_0$): A statement asserting no change, effect, or difference
• Alternative Hypothesis ($H_1$ or $H_a$): Contradicts the null hypothesis, aiming to find evidence for it
• An Example:
  • $H_0$: Average height of men is 5'10".
  • $H_1$: Average height of men is not 5'10".
• Test Statistic: A value from sample data used to decide whether to reject the null hypothesis
• P-value: Probability of observing a test statistic as extreme or more extreme, assuming $H_0$ is true
• A small P-value (≤ 0.05) indicates strong evidence against $H_0$
• A large P-value implies weak evidence against $H_0$
• Significance Level ($\alpha$): Predetermined threshold for rejecting $H_0$, common values are 0.05 and 0.01
• Decision Rules:
  • If P-value $\leq \alpha$, reject $H_0$.
  • If P-value $>\alpha$, fail to reject $H_0$.

Types of Errors

• Type I Error (False Positive): Rejecting a true $H_0$, probability = $\alpha$
• Type II Error (False Negative): Failing to reject a false $H_0$, probability = $\beta$
• Power of the test: Probability of correctly rejecting a false $H_0$
• Power = $1 - \beta$

Common Hypothesis Tests

• Z-test: Used with known population standard deviation or large sample size ($n \geq 30$)
• Formula for Z-test: $$ Z = \frac{\bar{x} - \mu_0}{\frac{\sigma}{\sqrt{n}}} $$
• $\bar{x}$ is the sample mean
• $\mu_0$ is the hypothesized population mean
• $\sigma$ is the population standard deviation
• $n$ is the sample size
• T-test: Used with unknown population standard deviation and small sample size ($n < 30$)
• Formula for t-test: $$ t = \frac{\bar{x} - \mu_0}{\frac{s}{\sqrt{n}}} $$
  • $\bar{x}$ is the sample mean
  • $\mu_0$ is the hypothesized population mean
  • $s$ is the sample standard deviation
  • $n$ is the sample size
• Degrees of freedom: $df = n - 1$
• Chi-Square Test: Used for categorical data to test independence or goodness of fit
• Formula for Chi-Square Test: $$ \chi^2 = \sum \frac{(O - E)^2}{E} $$
  • $O$ is the observed frequency
  • $E$ is the expected frequency
• ANOVA (Analysis of Variance): Used to compare means of two or more groups
• The test statistic is F-statistic
• Variances are partitioned into different sources

Steps in Hypothesis Testing

• State the null and alternative hypotheses
• Choose a significance level ($\alpha$)
• Calculate the test statistic
• Determine the P-value associated with the test statistic
• Making a decision: If P-value $\leq \alpha$, reject $H_0$, else, fail to reject $H_0$
• Interpret the result in the context of the original problem

Example Problem

• Problem: A company claims that the average lifespan of their light bulbs is 1000 hours. A sample of 40 light bulbs is tested, the sample mean is 980 hours with a sample standard deviation of 80 hours, with $\alpha = 0.05$
• Solution:
  • $H_0: \mu = 1000$
  • $H_1: \mu \neq 1000$
  • Significance Level: $\alpha = 0.05$
  • Test statistic: Since the sample size is reasonably large, we can use a t-test. $$ t = \frac{980 - 1000}{\frac{80}{\sqrt{40}}} \approx -1.58 $$
• P-value: Using a t-distribution with $df = 39$, the P-value for $t = -1.58$ is approximately 0.122.
• Decision: P-value > $\alpha$ we fail to reject the null hypothesis
• Interpretation: There is not enough evidence to reject the company's claim that the average lifespan of their light bulbs is 1000 hours

Algorithmic Complexity

• Algorithmic complexity measures the amount of resources (time or space) required by an algorithm as a function of the input size
• It provides a way to compare the efficiency of different algorithms for solving the same problem

Big O Notation

• Describes the upper bound of an algorithm's growth rate

Common Complexities for Algorithmic Complexity Table

Example Searching for an element in a sorted array

• Linear Search*
• Complexity: O(n)
• Explanation: In the worst case, we might have to iterate through every element in the array.
• Binary Search*
• Complexity: O(log n)
• Explanation: We repeatedly divide the search interval in half.

Sorting Algorithms Table

Practical Implications

• Choosing the right algorithm can significantly impact performance, especially for large datasets.
• Understanding algorithmic complexity helps in making informed decisions about algorithm selection.
• Always consider the trade-offs between time complexity, space complexity, and implementation complexity.

Guía de Estilo Para Tesis

Introducción

• Proporciona instrucciones para preparar y presentar la tesis
  • Asegura una presentación clara y profesional de la investigación

Estructura De La Tesis

• Página de título:
  • Título de la tesis
  • Nombre del autor
  • Afiliación institucional
  • Fecha de presentación
• Resumen:
  • Resumen conciso del propósito, métodos y hallazgos de la investigación (máximo 250 palabras).
  • Palabras clave relevantes.
• Introducción:
  • Establece el contexto y la importancia del tema de investigación.
  • Presenta la pregunta de investigación o hipótesis
  • Describe brevemente la metodología utilizada.
  • Destaca las contribuciones originales de la tesis.
• Revisión de la literatura:
  • Proporciona una visión general exhaustiva de la literatura existente relacionada con el tema de investigación
  • Identifica las brechas en el conocimiento que la tesis pretende abordar.
  • Sintetiza y evalúa críticamente las fuentes relevantes
• Metodología:
  • Describe detalladamente los métodos de investigación utilizados para recopilar y analizar datos
  • Justifica la elección de los métodos en relación con los objetivos de la investigación
  • Proporciona información sobre la población o muestra estudiada
  • Describe los procedimientos de recopilación de datos y las técnicas de análisis utilizadas
• Resultados:
  • Presenta los hallazgos de la investigación de manera clara y concisa
  • Utiliza tablas, figuras y gráficos para visualizar los datos cuando sea apropiado
  • Describe los resultados de manera objetiva, sin interpretaciones ni conclusiones
• Discusión:
  • Interpreta y analiza los resultados en relación con la pregunta de investigación o hipótesis
  • Compara los hallazgos con la literatura existente.
  • Discute las implicaciones teóricas y prácticas de la investigación
• Reconoce las limitaciones del estudio y sugiere áreas para futuras investigaciones
• Conclusiones:
  • Resume los principales hallazgos y conclusiones de la tesis
  • Reitera la importancia de la investigación y sus contribuciones al campo
  • Ofrece recomendaciones basadas en los resultados obtenidos
• Referencias:
  • Lista completa de todas las fuentes citadas en la tesis
• Sigue un estilo de citación consistente (por ejemplo, APA, MLA, Chicago)
• Apéndices (opcional):
  • Material complementario que respalda o complementa la tesis (por ejemplo, cuestionarios, transcripciones de entrevistas, datos adicionales)

Formato

• Márgenes: 2.5 cm en todos los lados.
• Fuente: Times New Roman, tamaño 12.
• Doble espacio en todo el documento, excepto en las notas al pie, encabezados de tablas y leyendas de figuras
• Numeración de páginas:
  • En la esquina superior derecha, a partir de la página de título (utilizar números romanos en las páginas preliminares).

Estilo de Escritura

• Utilizar un lenguaje claro, conciso y preciso.
• Evitar jerga innecesaria y ambigüedades.
• Escribir en tercera persona o voz impersonal (evitar el uso de "yo" o "nosotros").
• Mantener la coherencia en el estilo y la terminología a lo largo de la tesis.
• Revisar cuidadosamente la gramática, ortografía y puntuación.

Presentación

• Entregar la tesis en formato electrónico (PDF) y, si es requerido, en formato impreso
• Asegurarse de que la tesis esté correctamente encuadernada y etiquetada
• Seguir las instrucciones específicas del departamento o programa académico en cuanto a los requisitos de presentación

Consejos Adicionales

• Planificar y organizar el tiempo de manera efectiva para completar la tesis dentro del plazo establecido.
• Buscar la retroalimentación de profesores, compañeros y asesores a lo largo del proceso de investigación y escritura
• Citar todas las fuentes de manera adecuada para evitar el plagio
• Mantener la motivación y perseverancia a lo largo del proceso de elaboración de la tesis
• ¡Confiar en sus habilidades y conocimientos!

La Fonction Exponentielle

Définition

• La fonction exponentielle, notée exp(x) ou $e^x$, est définie comme la solution de l'équation différentielle:

$f'(x) = f(x)$

vec la condition initiale $f(0) = 1$.

Propriétés

• La fonction exponentielle est définie et continue sur $\mathbb{R}$.
• Elle est strictement positive sur $\mathbb{R}$ : $e^x > 0$ pour tout $x \in \mathbb{R}$.
• Elle est strictement croissante sur $\mathbb{R}$.
• $\lim_{x \to -\infty} e^x = 0$
• $\lim_{x \to +\infty} e^x = +\infty$
• $e^0 = 1$
• $e^1 = e \approx 2.718$

Relations fonctionnelles

• Pour tous réels $a$ et $b$:
• $e^{a+b} = e^a \cdot e^b$
• $e^{a-b} = \frac{e^a}{e^b}$
• $e^{-a} = \frac{1}{e^a}$
• $(e^a)^b = e^{ab}$

Dérivée

• La dérivée de la fonction exponentielle est elle-même:

$(e^x)' = e^x$

• Plus généralement, si $u(x)$ est une fonction dérivable:

$(e^{u(x)})' = u'(x)e^{u(x)}$

Limites remarquables

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

Vectores - Physics Topic

• Vector: A directed line segment with magnitude, direction, and sense

Vector Components

• A vector $\vec{A}$ in a plane can be represented in its rectangular components $A_x$ and $A_y$ where:
  • $A_x = A \cos(\theta)$
  • $A_y = A \sin(\theta)$
    • $A$ is the magnitude of the vector
    • $\theta$ is the angle between the vector $\vec{A}$ and the positive x-axis.

Vector Sum

• To add vectors, you can sum there components
  • $\vec{A} = (A_x, A_y)$ and $\vec{B} = (B_x, B_y)$
  • $\vec{A} + \vec{B} = (A_x + B_x, A_y + B_y)$
    • The magnitude of a resulting vector $\vec{R} = \vec{A} + \vec{B}$ is
    • $R = \sqrt{(A_x + B_x)^2 + (A_y + B_y)^2}$
    • The angle $\theta$ that forms the resulting vector with the positive x-axis is
      • $\theta = \arctan\left(\frac{A_y + B_y}{A_x + B_x}\right)$

Producto Escalar (Producto Punto)

• The scalar product of two vectors $\vec{A}$ and $\vec{B}$ gives
  • $\vec{A} \cdot \vec{B} = |\vec{A}| |\vec{B}| \cos(\theta)$
  • $\theta$ is the angle between the vectors $\vec{A}$ and $\vec{B}$.
    • In terms of components:
    • $\vec{A} \cdot \vec{B} = A_x B_x + A_y B_y + A_z B_z$

Producto Vectorial (Producto Cruz)

• The vectorial product of two vectors $\vec{A}$ and $\vec{B}$ results in a vector $\vec{C}$ whose magnitude is
  • $|\vec{C}| = |\vec{A}| |\vec{B}| \sin(\theta)$
  • $\theta$ is the angle between the vectors $\vec{A}$ and $\vec{B}$
    • The direction of $\vec{C}$ is perpendicular to the plane formed by $\vec{A}$ and $\vec{B}$, and its sense is given by the right hand rule
      • In terms of components:
        • $\vec{A} \times \vec{B} = (A_y B_z - A_z B_y, A_z B_x - A_x B_z, A_x B_y - A_y B_x)$
          • Or, using a determinant:
            • $\vec{A} \times \vec{B} = \begin{vmatrix}\hat{i} & \hat{j} & \hat{k} \A_x & A_y & A_z \B_x & B_y & B_z\end{vmatrix}$

Vectores Tangente unitario, Vector Normal Principal, y Vector Binormal

• Let $\mathbf{r}(t)$ be a vectorial function that describes a curve in space
• The unit tangential vector $\mathbf{T}(t)$ in the point $\mathbf{r}(t)$ is
• $\mathbf{T}(t) = \frac{\mathbf{r}'(t)}{|\mathbf{r}'(t)|}$
• The Normal Principial vector $\mathbf{N}(t)$ in the point $\mathbf{r}(t)$ is
  • $\mathbf{N}(t) = \frac{\mathbf{T}'(t)}{|\mathbf{T}'(t)|}$
• The Binormal vetor $\mathbf{B}(t) in the point $\mathbf{r}(t)$ is
• $\mathbf{B}(t) = \mathbf{T}(t) \times \mathbf{N}(t)$
• The vectors $\mathbf{T}(t)$, $\mathbf{N}(t)$ y $\mathbf{B}(t)$ are mutually orthogonal and form a moving tried that describes the orientation of the curve in each point.
• The following table shows the time complexity of common operations on various data structures.

• • Linear Independence:
• A set of vectors $$v_1, v_2,..., v_n$$ in $$\mathbb{R}^m$$ is linearly independent if the only solution to the equation $$ c_1v_1 + c_2v_2 +... + c_nv_n = 0 $$ is $$c_1 = c_2 =... = c_n = 0$$.
• A set of vectors $$v_1, v_2,..., v_n$$ in $$\mathbb{R}^m$$ is linearly dependent if there exist scalars $$c_1, c_2,..., c_n$$, not all zero, such that $$ c_1v_1 + c_2v_2 +... + c_nv_n = 0 $$
• Information Retrieval (IR):
  • IR is finding material (usually documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually stored on computers).

How is it different from DataBase (DB) queries?

• IR deals with unstructured data, while DB deals with structured data.
• IR queries are based on keywords, while DB queries are based on structured query language (SQL).
• IR results are ranked based on relevance, while DB results are exact matches.
• recall:
  • $Recall = \frac{#(\text{relevant items retrieved})}{#(\text{all relevant items})}$
• precision:
  • $Precision = \frac{#(\text{relevant items retrieved})}{#(\text{all retrieved items})}$
• F-measure:
  • The F-measure is a way to combine recall and precision into a single measure. $F = \frac{1}{\alpha \frac{1}{P} + (1 - \alpha) \frac{1}{R}} = \frac{PR}{\alpha R + (1 - \alpha)P}$ where
• $P$ is the precision
• $R$ is the recall
• $\alpha \in [0, 1]$ is a parameter that controls the weight given to precision and recall.