You are the president, and you are trying to choose the secretary of state. You can only interview people in sequence, and you have to hire on the spot. There are a known number of candidates. We want to maximize the probability of selecting the best candidate. You are given no priors.

How do we know which candidates we explore, and which candidates we exploit?

Sometimes, you don’t have a way of getting data.

Analogous to poisson distribution, but for continuous random variable. Consider a distribution which lasts a duration of time until success; what’s the probability that success is found in some range of times:

“What’s the probability that there are an earthquake in \(k\) years if there’s on average \(2\) earthquakes in 1 year?”

constituents

• $λ$—“rate”: event rate (mean occurrence per time)

requirements

\begin{equation} f(x) = \begin{cases} \lambda e^{-\lambda x}, x\geq 0\\ 0, x< 0 \end{cases} \end{equation}

A Turing Machine can simulate every “reasonable” model of computation with only Polynomial Time increase in time complexity—possibly the “worse possible”

This is only a thesis! There’s a chance, for instance, randomized quantum algorithms may change this.

see also: Church-Turing thesis as local steps

\(\mathbb{F}^n\) is the set of all lists of length \(n\) with elements of \(\mathbb{F}\). These are a special case of matricies.

Formally—

\begin{equation} \mathbb{F}^n = \{(x1,\ldots,x_n):x_j\in\mathbb{F}, \forall j =1,\ldots,n\} \end{equation}

For some \((x_1,\ldots,x_n) \in \mathbb{F}^n\) and \(j \in \{1,\ldots,n\}\), we say \(x_j\) is the \(j^{th}\) coordinate in \((x_1,\ldots,x_n)\).

additional information

addition in \(\mathbb{F}^n\)

Addition is defined by adding corresponding coordinates:

\begin{equation} (x1,\ldots,x_n) + (y_1,\ldots,y_n) = (x_1+y_1, \ldots,x_n+y_n) \end{equation}

addition in \(\mathbb{F}^n\) is commutative

If we have \(x,y\in \mathbb{F}^n\), then \(x+y = y+x\).

We define a set \(\mathbb{F}^{s}\), which is the set of unit functions that maps from any set \(S\) to \(\mathbb{F}\).

closeness of addition

\begin{equation} (f+g)(x) = f(x)+g(x), \forall f,g \in \mathbb{F}^{S}, x \in S \end{equation}

closeness of scalar multiplication

\begin{equation} (\lambda f)(x)=\lambda f(x), \forall \lambda \in \mathbb{F}, f \in \mathbb{F}^{S}, x \in S \end{equation}

commutativity

inherits \(\mathbb{F}\) (for the codomain of functions \(f\) and \(g\))

associativity

inherits \(\mathbb{F}\) for codomain or is just \(\mathbb{F}\) for scalar