Random variables

A random variable is a function $X: \Omega \rightarrow {\mathbb R}$. It basically measures a certain value of each atomic event. Let us look at some examples.

• Coin tossing: Each atomic event is an outcome $w \in \{0,1\}^k$ of $k$ coin tosses. Let $X$ be the number of heads and $Y$ the number of occurrences of two consecutive heads. Then both $X$ and $Y$ are random variables; in particular, $X(w) = \sum_i w_i$ for $w \in \Omega$. For $w = 0111011$, we have $X(w) = 5$ and $Y(w) = 3$.

• Random graphs: Each atomic event is a graph in $\Gamma_n$. Let $Z$ be the degree of vertex $1$, and $W$ be the diameter. Then both $Z$ and $W$ are random variables.

For random variable $X$, when we write the event "$X=k$", it means the set $\{w \in \Omega: X(w) = k\}$ (recall that an event is a subset of the sample space). In this way, the notation ${\mathbb P}[X=k]$ is syntactically correct and refers to the probability of the set.

📄️ Expectation

The expected value of random variable $X$ is defined as

📄️ Balls and bins

Recall the balls and bins setting where we randomly put $m$ balls into $n$ bins. The sample space is $\Omega_{m,n} = \{f: [m] \rightarrow [n]\}$ and the distribution is uniform.

📄️ Fixed points of permutation

Recall the example of derangements (Deragements). Let us pick a random permutation $f$ on $[n]$. A fixed point is a value $i \in [n]$ for which $f(i) = i$. (so this is the student who receives their own homework when the homework is returned at random order)

📄️ Professor's misery

Parinya needs to go to a trial for teaching too much mathematical content in the CS department.