The number of alpha vectors needed to perform PBVI is one for each of your belief sample. Which is a bad idea. Perseus is essentially PBVI, where this idea is explored slightly.

The preamble is the same as PBVI:

we keep track of a bunch of alpha vectors and belief samples (which we get from point selection):

\begin{equation} \Gamma = \{\alpha_{1}, \dots, \alpha_{m}\} \end{equation}

and

\begin{equation} B = \{b_1, \dots, b_{m}\} \end{equation}

To preserve the lower-boundedness of these alpha vectors, one should seed the alpha vectors via something like blind lower bound

a randomized turing machine is a turing machine with functions \(\delta_{0}\), \(\delta_{1}\). During computation, we take either \(\delta_{0}\) or \(\delta_{1}\) each with probability \(\frac{1}{2}\).

See also randomized algorithm.

decision

a randomized TM decides a particular language \(L\) if, \(\forall x \in \Sigma^{*}\), we have that:

\begin{align} &x \in L \implies \text{Pr}\qty [M\text{ accepts } x] \geq \frac{2}{3} \\ &x \not\in L \implies \text{Pr}\qty [M\text{ accepts } x] \leq \frac{1}{3} \end{align}

NOTE! we have to prove this for all \(x\). “most \(x\)” is not good enough.

The range (image, column space) is the set that some function \(T\) maps to.

constituents

some \(T: V\to W\)

requirements

The range is just the space the map maps to:

\begin{equation} range\ T = \{Tv: v \in V\} \end{equation}

additional information

range is a subspace of the codomain

This result is hopefully not super surprising.

zero

\begin{equation} T0 = 0 \end{equation}

as linear maps take \(0\) to \(0\), so \(0\) is definitely in the range.