IIT M FOUNDATION AN EXAM QDF4 31 Aug - 31 Aug 2025

Concepts this paper tests

Auto-generated summary from the source site. Handy as a checklist; the lessons above explain each idea from scratch.

Here’s a structured summary of core topics, concepts, principles, and equations for the exam, followed by Mermaid knowledge graphs to visualize relationships.

1. Core Topics & Key Concepts

A. Probability & Statistics

1. Markov’s Inequality

   • For non-negative random variable $X$ and $a > 0$:

• Application: Bounding tail probabilities (e.g., $\mathbb{P}(X \geq 2pn) \leq \frac{1}{2}$ for binomial $X \sim \text{Binomial}(n, p)$).

1. Chebyshev’s Inequality

   • For any random variable $X$ with mean $\mu$, variance $\sigma^2$, and $k > 0$:

• Application: Bounding deviation from mean (e.g., $\mathbb{P}(X \geq 2pn) \leq \frac{1-p}{np}$).

1. Normal Distribution

   • If $X \sim \text{Normal}(\mu_X, \sigma_X^2)$ and $Y \sim \text{Normal}(\mu_Y, \sigma_Y^2)$ are independent, then:

• Standardization: $Z = \frac{X - \mu}{\sigma} \sim \text{Normal}(0, 1)$.

1. Joint Probability Density Function (PDF)

   • For continuous random variables $X, Y$, the marginal PDF of $Y$ is:

• Variance: $\text{Var}(Y) = \mathbb{E}[Y^2] - (\mathbb{E}[Y])^2$.

1. Conditional Probability

   • $\mathbb{P}(C \mid D) = \frac{\mathbb{P}(C \cap D)}{\mathbb{P}(D)}$.
   • Example: Permutations of 4 distinct items with constraints.

B. Linear Algebra

1. Vector Spaces & Span

   • $\text{span}(v_1) = \{ \alpha v_1 \mid \alpha \in \mathbb{R} \}$.
   • Projection: Projection of $v_2$ onto $\text{span}(v_1)$ is $\text{proj}_{v_1} v_2 = \left( \frac{v_2 \cdot v_1}{v_1 \cdot v_1} \right) v_1$.

1. Orthogonality

   • Vectors $v_1$ and $v_2$ are orthogonal if $v_1 \cdot v_2 = 0$.

1. Eigenvalues & Diagonalizability

   • For matrix $A$, eigenvalues $\lambda$ satisfy $\det(A - \lambda I) = 0$.
   • Hermitian Matrix: $A = A^H$ (conjugate transpose).
   • Unitary Matrix: $A^H A = I$.
   • Diagonalizable: $A$ has $n$ linearly independent eigenvectors.

1. Matrix Operations

   • If $\lambda_1, \lambda_2, \lambda_3$ are eigenvalues of $A$, then eigenvalues of $2A^2 - 3I$ are $2\lambda_i^2 - 3$.
   • Product of Eigenvalues: $\lambda_1 \lambda_2 \lambda_3 = \det(A)$.

C. Optimization

1. Convex Functions

   • A function $f$ is convex if for all $x, y$ and $\theta \in [0, 1]$:

• Tests:

  • Hessian $\nabla^2 f \succeq 0$ (positive semidefinite).
  • For $f(x, y) = x^2 + y^2$, Hessian is $I \succeq 0$ (convex).
  • For $f(x) = x^\alpha y^\beta$ with $\alpha + \beta \leq 1$, check Hessian.

1. Constrained Optimization

   • Primal Problem: Minimize $f(x, y)$ subject to $g_i(x, y) \leq 0$.
   • Lagrangian:

• KKT Conditions:

  • Stationarity: $\nabla f + \sum u_i \nabla g_i = 0$.
  • Complementary Slackness: $u_i g_i = 0$.

1. Quadratic Optimization

   • Minimize $x^2 + y^2$ subject to linear constraints (e.g., closest point to origin in a polytope).

D. Probability Distributions

1. Binomial Distribution

   • $X \sim \text{Binomial}(n, p)$:

     • Mean: $\mathbb{E}[X] = np$.
     • Variance: $\text{Var}(X) = np(1-p)$.

1. Uniform Distribution

   • Joint PDF over a simplex (e.g., $f(x, y) = 24xy$ for $x + y < 1$).

2. Key Equations

Graph 2: Linear Algebra

Graph 3: Optimization

Graph 4: Probability Distributions

Graph 5: Relationships Between Topics

4. Exam Tips

1. Markov/Chebyshev: Memorize the inequalities and their conditions (non-negativity, variance).
2. Normal Distribution: Practice linear combinations and standardization.
3. Convexity: Check Hessian for convexity/concavity.
4. Lagrangian: Write the correct objective and constraints (e.g., $u_i \geq 0$ for inequalities).
5. Eigenvalues: For $2A^2 - 3I$, first find eigenvalues of $A$, then apply the transformation.
6. Projection: Use the formula $\text{proj}_{v_1} v_2 = \left( \frac{v_2 \cdot v_1}{v_1 \cdot v_1} \right) v_1$.