example consider an experiment that consists of flipping coin until it comes up heads this sample space is infinitewith each outcome being sequence of tails followed by single flip that comes up headsfor probability space is sample space together with probability function pr that maps subsets of to real numbers in the interval [ it captures mathematically the notion of the probability of certain "eventsoccurring formallyeach subset of is called an eventand the probability function pr is assumed to possess the following basic properties with respect to events defined from pr( pr( <pr( < for any if ab and then pr( bpr(apr(btwo events and are independent if pr( bpr(apr(ba collection of events { an is mutually independent if pr(ai ai aik pr(ai pr(ai pr(aik for any subset {ai ai aik the conditional probability that an event occursgiven an event bis denoted as pr( | )and is defined as the ratio pr( bpr(bassuming that pr( an elegant way for dealing with events is in terms of random variables intuitivelyrandom variables are variables whose values depend upon the outcome of some experiment formallya random variable is function that maps outcomes from some sample space to real numbers an indicator random variable is random variable that maps outcomes to the set { often in data structure and algorithm analysis we use random variable to characterize the running time of randomized algorithm in this casethe sample space is defined by all possible outcomes of the random sources used in the algorithm we are most interested in the typicalaverageor "expectedvalue of such random variable the expected value of random variable is defined as ( pr( ) where the summation is defined over the range of (which in this case is assumed to be discrete