A random variable is a quantity that can take on different values, whereby there is a separate probability associated with each value:

• discrete: finite number of values
• continuous: infinitely many possible values

probability mass function

A discrete random variable is encoded as a probability mass function

probability density function

A continuous random variable is represented as a probability density function.

summary statistics

• probability mass function is a description for the random variable: and random variables are usually communicated via probability mass functions
• expected value

adding random variables

“what’s the probability of \(X + Y = n\) with IID \(X\) and \(Y\)?” “what’s the probability of two independent samples from the same exact distribution adding up to \(n\)?”

The Random Walk Hypothesis is a financial econometric hypothesis that stocks have the same distribution and independent of each other: that stocks are a random variable and not predictable in a macro space.

To set up the random walk hypothesis, let’s begin with some time \(t\), an asset return \(r_t\), some time elapsed \(k\), and some future asset return \(r_{t+k}\).

We will create two random variables \(f(r_t)\) and \(g(r_{t+k})\), which \(f\) and \(g\) are arbitrary functions we applied to analyze the return at that time.

randomized algorithm is a type of algorithm, similar to relaxation.

• Make a hard problem easier by changing the problem
• What if, instead of guaranteeing we find the best/correct answer, we only provide some chance of finding the best/correct answer?

primality testing

primality testing is very important for modern crypto systems; we need to be able to find large prime numbers, and be able to generate them quickly.

traditional primality testing

We can divide every prime number below \(\sqrt x\). In theory, this is pretty fast, but we need to know all the primes we need to test.