# How to Read the Mathematics in This Paper

This guide explains every piece of mathematical notation used in the paper,
in the order you will encounter it. No prior math background beyond basic
arithmetic is assumed.

---

## The Basics

### Variables and Subscripts

A variable is a letter that stands for a number. In this paper:

- $n$ = the total number of tasks
- $p_i$ = the processing time (how many hours of work) for task $i$
- $C_i$ = the completion time (when task $i$ is finished) under a given schedule
- $q_i$ = the priority class of task $i$ (1 = Critical, 4 = Low)
- $w(q)$ = the weight assigned to priority class $q$

The subscript $i$ is just a label. $p_1$ means "the processing time of
task 1," $p_2$ means "the processing time of task 2," and so on. When we
write $p_i$, we mean "the processing time of task $i$, for any $i$."

### Lists of Things

$p_1, p_2, \ldots, p_n$ means "a list of processing times, from task 1
up to task $n$." The $\ldots$ just means "and so on." If there are 5 tasks,
this is $p_1, p_2, p_3, p_4, p_5$.

---

## Symbols You Will See

| Symbol | Name | What it means | Example |
|--------|------|---------------|---------|
| $=$ | Equals | Left side is the same as right side | $2 + 3 = 5$ |
| $\ne$ | Not equal | These two things are different | $3 \ne 4$ |
| $>$ | Greater than | Left is bigger | $5 > 3$ |
| $<$ | Less than | Left is smaller | $3 < 5$ |
| $\le$ | Less than or equal to | Left is smaller or the same | $3 \le 5$, $3 \le 3$ |
| $\ge$ | Greater than or equal to | Left is bigger or the same | $5 \ge 3$, $5 \ge 5$ |
| $\approx$ | Approximately equal | Close but not exact | $10/3 \approx 3.33$ |
| $\cdot$ | Multiplication | Same as $\times$ | $3 \cdot 4 = 12$ |
| $\perp$ | Independent of | No relationship between them | $p_i \perp q_i$ means task size and priority are unrelated |
| $\forall$ | For all | "This is true for every..." | $S_i = S_j \; \forall \, i, j$ means "slowdown is equal for all tasks" |
| $\in$ | Is a member of | Belongs to a set | $q_i \in \{1, 2, 3, 4\}$ means priority is one of 1, 2, 3, or 4 |
| $\blacksquare$ | End of proof | "The proof is complete" | Appears at the end of every proof |

---

## The Big Sigma: Summation ($\sum$)

This is the most important symbol in the paper. It means "add up a list
of things."

$$\sum_{i=1}^{n} p_i$$

Read this as: "Add up $p_i$ for every $i$ from 1 to $n$."

If there are 3 tasks with processing times $p_1 = 2$, $p_2 = 5$, $p_3 = 3$:

$$\sum_{i=1}^{3} p_i = p_1 + p_2 + p_3 = 2 + 5 + 3 = 10$$

The letter under the $\sum$ ($i = 1$) tells you where to start counting.
The number on top ($n$ or $3$) tells you where to stop. The expression
after the $\sum$ ($p_i$) tells you what to add up.

### Variations You Will See

**Summing a product:**

$$\sum_{i=1}^{n} w(q_i) \cdot C_i$$

Add up $w(q_i) \times C_i$ for each task. If task 1 has weight 8 and
completion time 3, and task 2 has weight 1 and completion time 5:

$$= 8 \cdot 3 + 1 \cdot 5 = 24 + 5 = 29$$

**Summing with a condition:**

$$\sum_{\substack{a \ne b}} p_a \, p_b$$

Add up $p_a \times p_b$ for every pair of tasks $a$ and $b$ where $a$
and $b$ are different tasks. The condition ($a \ne b$) filters which
terms to include.

**Summing up to a variable position:**

$$\sum_{j=1}^{k} p_{\sigma(j)}$$

Add up processing times for the first $k$ tasks in the schedule. This is
how completion time is defined — it is the total work done up to and
including position $k$.

---

## Fractions

$$\frac{a}{b}$$

This means $a \div b$. The top is the numerator, the bottom is the
denominator. When you see:

$$\bar{C}(\sigma) = \frac{1}{n} \sum_{k=1}^{n} C_{\sigma(k)}$$

This means: add up all the completion times, then divide by $n$ (the
number of tasks). This is an **average** — the same operation as
calculating a mean in everyday life.

### Nested Fractions

$$\bar{C}_w(\sigma) = \frac{\sum_{k=1}^{n} p_{\sigma(k)} \cdot C_{\sigma(k)}}{\sum_{k=1}^{n} p_{\sigma(k)}}$$

The top (numerator) is: add up (processing time $\times$ completion time)
for each task. The bottom (denominator) is: add up all the processing
times. This is a **weighted average** — tasks with more work count more
heavily.

---

## Schedules and Permutations ($\sigma$)

$\sigma$ (the Greek letter "sigma") represents a **schedule** — the order
in which tasks are done.

If you have 3 tasks and decide to do them in order 2, 3, 1, then:
- $\sigma(1) = 2$ — the first task you do is task 2
- $\sigma(2) = 3$ — the second task you do is task 3
- $\sigma(3) = 1$ — the third task you do is task 1

When you see $p_{\sigma(k)}$, it means "the processing time of whichever
task is in position $k$ of the schedule."

### Ordering Symbols

- $b \preceq_\sigma a$ means "task $b$ is scheduled at the same time as
  or before task $a$" — i.e., $b$ comes first (or they are the same task)
- $a \prec_\sigma b$ means "task $a$ is scheduled strictly before task $b$"

These are just ways of saying "which task comes first in the schedule."

---

## The Bar: Averages ($\bar{C}$)

A bar over a letter means "average." So:

- $\bar{C}$ = average completion time
- $\bar{C}_w$ = weighted average completion time (the subscript $w$ distinguishes it)
- $\bar{p}$ = average processing time

---

## The Delta: Change ($\Delta$)

$\Delta$ (capital delta) means "the change in" or "the difference."

- $\Delta_i = C_i - p_i$ — the delay for task $i$ (how much longer it
  waited beyond its own processing time)
- $\Delta D = w(q_j) \cdot p_i - w(q_i) \cdot p_j$ — how much the
  priority-weighted delay cost changes when you swap two tasks

---

## Subscripts and Superscripts

**Subscripts** (below) are labels or indices:
- $p_i$ = processing time of task $i$
- $p_{\max}$ = the largest processing time
- $p_{\min}$ = the smallest processing time
- $\bar{C}_{\text{SPT}}$ = average completion time under the SPT schedule
- $\bar{C}_{\text{priority}}$ = average completion time under priority scheduling

**Superscripts** (above) indicate context or power:
- $p_a^2$ = $p_a \times p_a$ (squared)
- $\bar{C}^{\text{SPT}}$ = completion time under SPT (same idea as subscript, just different formatting)

---

## Set Notation

$$q_i \in \{1, 2, 3, 4\}$$

The curly braces $\{ \}$ define a **set** — a collection of possible
values. $\in$ means "is a member of." So this reads: "the priority
$q_i$ is one of the values 1, 2, 3, or 4."

---

## The Piecewise Function (Cases)

$$w(q) = \begin{cases} 8 & q = 1 \text{ (Critical)} \\ 4 & q = 2 \text{ (High)} \\ 2 & q = 3 \text{ (Medium)} \\ 1 & q = 4 \text{ (Low)} \end{cases}$$

This defines a function that gives different outputs depending on the
input. Read it as: "If $q$ is 1, then $w$ is 8. If $q$ is 2, then $w$
is 4." And so on. It is just a lookup table written in math notation.

---

## Limits and Convergence

$$\lim_{T \to \infty} \frac{W(T)}{T} = \mu$$

Read as: "As $T$ gets larger and larger (approaching infinity), the value
of $W(T) / T$ gets closer and closer to $\mu$." In this paper, it means:
over a long enough time horizon, the throughput settles to a fixed rate
$\mu$ regardless of scheduling order.

- $\to$ means "approaches" or "goes toward"
- $\infty$ means infinity (without bound)

---

## Mutual Information ($I$)

$$I(\sigma_{\text{SPT}}) = 0 \quad \text{when } p_i \perp q_i$$

$I$ here measures **how much knowing one thing tells you about another**.
$I = 0$ means "knowing a task's position in the SPT schedule tells you
absolutely nothing about its priority." The schedule and the priority
system are statistically independent — they contain no information about
each other.

---

## Functions

$f(\bar{C})$ means "some function of $\bar{C}$." A function takes an
input and produces an output. When the paper writes:

$$U_{\text{client}} = f\!\left(\bar{C}(\sigma)\right), \quad f' < 0$$

It means: client satisfaction ($U$) depends on the average completion
time, and $f' < 0$ means the function is **decreasing** — when the
average goes up, satisfaction goes down. The $'$ (prime) notation refers
to the derivative, which indicates the direction of change.

---

## Correlation ($\text{Corr}$)

$$\text{Corr}(p_i, q_i) \approx 0$$

Correlation measures whether two quantities move together. A correlation
of 0 means they are unrelated — knowing the size of a task tells you
nothing about its priority. A positive correlation means they increase
together; a negative correlation means one goes up when the other goes
down.

---

## Variance ($\text{Var}$) and Standard Deviation ($\sigma_p$)

Variance measures how spread out a set of numbers is. If all tasks take
about the same time, variance is low. If some are 15 minutes and others
are 40 hours, variance is high.

The **coefficient of variation** $CV = \sigma_p / \bar{p}$ normalizes
the spread by dividing by the average. Here $\sigma_p$ is the standard
deviation (the square root of variance) of the processing times, and
$\bar{p}$ is the mean. A $CV$ above 1 means the spread is wider than
the average — the data is highly variable.

(Note: $\sigma_p$ uses the same Greek letter as schedule $\sigma$, but
they are different things. Context tells you which is which — $\sigma_p$
with a subscript $p$ always means standard deviation of processing times;
$\sigma$ alone or $\sigma(k)$ always means a schedule.)

---

## How to Read the Proofs

### The Exchange Argument

The most common proof technique in this paper works like this:

1. Assume you have any schedule.
2. Find two adjacent tasks that are in the "wrong" order.
3. Swap them and show that the metric improves (or stays the same).
4. Conclude: since every "wrong" pair can be improved by swapping,
   the best schedule has no "wrong" pairs — i.e., everything is in
   the "right" order.

This is like proving that a sorted list is optimal by showing that
any out-of-order pair can be fixed by swapping, and each swap makes
things better.

### Reading a Proof Step by Step

Take the simplest proof in the paper (Theorem 1):

> *"Consider any schedule in which two adjacent tasks $i, j$ satisfy*
> *$p_i > p_j$ with task $i$ scheduled immediately before task $j$."*

Translation: Pick any two neighboring tasks where the bigger one comes
first.

> *"Let $t$ be the start time of task $i$."*

Translation: Call the clock time when we start working on task $i$ by
the name $t$. We don't need to know what $t$ actually is.

> *"The change in the sum of completion times is:*
> *$(2p_i + p_j) - (p_i + 2p_j) = p_i - p_j > 0$"*

Translation: When the bigger task comes first, the total completion time
is $p_i - p_j$ hours **more** than if the smaller task came first. Since
$p_i > p_j$, this difference is positive — swapping them makes it better.

> *"Therefore SPT uniquely minimizes $\bar{C}(\sigma)$."* $\blacksquare$

Translation: Since every swap of big-before-small improves the metric,
the best possible schedule is all tasks sorted from smallest to largest.
Proof complete.

---

## Quick Reference Card

| When you see... | It means... |
|----------------|-------------|
| $\sum_{i=1}^{n}$ | Add up for each task from 1 to $n$ |
| $\frac{a}{b}$ | $a$ divided by $b$ |
| $\bar{X}$ | The average of $X$ |
| $\Delta X$ | The change in $X$ |
| $\sigma$ | A schedule (the order tasks are done) |
| $\sigma(k)$ | Which task is in position $k$ |
| $p_i$ | How long task $i$ takes |
| $C_i$ | When task $i$ finishes |
| $q_i$ | Priority class of task $i$ |
| $w(q_i)$ | How much priority class $q_i$ is weighted |
| $\le, \ge$ | Less/greater than or equal to |
| $\ne$ | Not equal to |
| $\in$ | Is a member of |
| $\forall$ | For all |
| $\perp$ | Independent of |
| $\blacksquare$ | End of proof |

---

## A Note on Reading Math

Mathematical notation is a compression format. The formula:

$$\bar{C}(\sigma) = \frac{1}{n} \sum_{k=1}^{n} C_{\sigma(k)}$$

says in 15 characters what takes a full sentence in English: "The average
completion time under schedule $\sigma$ equals the sum of all individual
completion times divided by the number of tasks."

If a formula looks intimidating, break it apart:
1. Find the main operation (usually $=$ splitting left from right)
2. Identify the pieces on each side
3. Replace the symbols with words using the tables above
4. Read it as a sentence

Every formula in this paper can be understood this way. The math is not
doing anything more complicated than arithmetic — it is just doing it
for a general case rather than specific numbers.

---

*This guide accompanies the paper "Unweighted Average Completion Time
Is Not a Fair Metric for Task Scheduling" (2026-03-28).*