Bandit Algorithms

2.1 Probability spaces and random elements 19

Figure 2.2A key idea in probability theory is the separation of sources of randomness

from game mechanisms. A mechanism creates values from the elementary random

outcomes, some of which are visible for observers, while others may remain hidden.

We follow the standard convention in probability theory where random

variables are denoted by capital letters. Be warned that capital letters are

also used for other purposes as demanded by different conventions.

Pick some numberv∈N. What is the probability of seeingX =v? As
described above, this probability is (1/6)^7 times the size of the setX−^1 (v) =
{ω∈Ω :X(ω) =v}. The setX−^1 (v) is called thepreimageofvunderX. More
generally, the probability thatXtakes its value in some setA⊆Nis given by
(1/6)^7 times the cardinality ofX−^1 (A) ={ω∈Ω :X(ω)∈A}, where we have
overloaded the definition ofX−^1 to set-valued inputs.
Notice in the previous paragraph we only needed probabilities assigned to
subsets of Ω regardless of the question asked. To make this a bit more general,
let us introduce a mapPthat assigns probabilities to certain subsets of Ω. The
intuitive meaning ofPis as follows. Random outcomes are generated in Ω. The
probability that an outcome falls into a setA⊂Ω isP(A). IfAis not in the
domain ofP, then there is no answer to the question of the probability of the
outcome falling inA. But let’s postpone the discussion of whyPshould be
restricted to only certain subsets of Ω later. In the above example with the dice,
the set of subsets in the domain ofPare not restricted and, in particular, for any
subsetA⊆Ω,P(A) = (1/6)^7 |A|.
The probability of seeingXtaking the value ofvis thusP

(

X−^1 (v)

)

. To
minimize clutter, the more readable notation for this isP(X=v). But always
keep in mind that this familiar form is just a shorthand forP

(

X−^1 (v)

)

. More
generally, we also use

P(predicate(U,V,...)) =P({ω∈Ω : predicate(U(ω),V(ω),...) is true})