Institute of Information Science - University of Miskolc

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== Cheatsheet for Math Exercises =====

==== Probability and Conditional Probability ====

^ Notation  ^ Value  ^ Formula ^
| $$P(A)$$ | Probability of event A occuring. | $$P(A) = \frac{\text{Number of favorable outcomes for } A}{\text{Total number of possible outcomes}}$$ |
| $$P(A \mid B)$$ | Conditional probability of event A occurring, given that event B has occurred. | $$P(A \mid B) = \frac{P(A \cap B)}{P(B)}$$ |
| $$P(A \cap B)$$  | Probability of both events A and B occurring. | In general: $$P(A \cap B) = P(A) \cdot P(B \mid A)$$ If A and B are independent events, then: $$P(A \cap B) = P(A) \cdot P(B)$$ |
| $$P(A \cup B)$$ | Probability that event A or event B (or both) occur. | $$P(A \cup B) = P(A) + P(B) - P(A \cap B)$$ |




==== Information Theory ====
^ Notation     ^ Value                                                                                               ^ Formula                                                                                                                         ^
| $$I(A)$$     | Information content or self-information of an event A.                                              | $$I(A) = -\log_2 P(A) = \log_2 \frac{1}{P(A)}  \text{ [bits]}$$                                                                 |
| $$H(X)$$     | Entropy, which measures the average amount of information (or uncertainty) in a random variable X.  | $$H(X) = -\sum_{x \in X} P(x) \log_2 P(x) = \sum_{x \in X} P(x) \log_2 \frac{1}{P(x)}  \text{ [bits]}$$                         |
| $$H_{max}$$  | Maximum possible entropy (when all outcomes are equally likely).                                    | $$H_{\text{max}} = \log_2 |\mathcal{X}|$$ $$|\mathcal{X}| \text{ is the number of possible outcomes in the set } \mathcal{X}$$  |
| $$R(X)$$     | Redundancy, which measures the portion of duplicative information within a message.                 | $$R = \frac{H_{\text{max}} - H}{H_{\text{max}}}$$          |
==== Combinatorics ====

^ ^ without repetition  ^ with repetition ^
| **Permutations** \\ number of all possible arrangements of $n$ elements | $$P_n = n!$$ | $$P_n^{k_1, k_2,...k_r} = \frac{n!}{k_1! \cdot k_2! \cdot ... \cdot k_r!}$$ |
| **Variations** \\ the number of all possible arrangements of any $k$ elements from $n$ elements | $$V_n^k=\frac{n!}{(n-k)!}$$ | $$\overline{V}_n^k=n^k$$ |
| **Combinations** \\ number of ways to choose $k$ items from $n$ items, regardless of order | $$C_n^k=\binom{n}{k}=\frac{n!}{k! \cdot (n - k)!}$$ | $$\overline{C}_n^k=\binom{n+k-1}{k}$$ |

=== What formula to use? ===
| | |  **Repetition**   ||
| | |  //Not possible//  |  //Possible//  |
| **Order** | //Matters// |  $$V_n^k$$ (variation without repetition)  |  $$\overline{V}_n^k$$ (variation with repetition)  | 
| ::: | //Doesn't matter// |  $$C_n^k$$ (combination without repetition)  |  $$\overline{C}_n^k$$ (combination with repetition)  |