>

Kernels

Definition 4   A kernel is a computable object on $\Omega$ provided of two methods: $best()$ and $draw()$. The method $draw()$ executes a random selection over $\Omega$ by using the distribution probability $f^*(\omega)$ implicitly defined by $compute(\cdot)$, (see Expression (1.1)). The method $best()$ is defined as follow:

$$best() = \omega \in \Omega : compute(\omega)\geq compute(\omega_i) ~\forall \omega_i \in \Omega$$ (1.2)

that is, $best()$ is the variable value $\omega\in\Omega$ that maximize $compute(\cdot)$. Otherwise stated $best()$ returns the variable value with the highest probability value.

Let's look a minimal example for showing the use of a kernel and its method $draw()$, at the same time we illustrate how to define variable types, spaces and values. Our first program consists on a simple and frequently used model in probability: throwing a die. Program 1 simulates throwing a symmetric six sides die as many times as the user ask for.

Program 1: Throwing a die.

     1  /*=============================================================================
     2   * File           : die.cpp
     3   *=============================================================================
     4   *
     5   *------------------------- Description ---------------------------------------
     6   * This program simulates throwing a symmetric 6 sides die
     7   * 
     8   *-----------------------------------------------------------------------------
     9  */
    10
    11  #include <pl.h>
    12
    13  main()
    14  {
    15
    16    /**********************************************************************
    17       Defining the variable type set and values plus the kernel for the
    18       variable set
    19    ***********************************************************************/
    20    
    21    plIntegerType die_type(1,6);       // Variable type for a die [1,2,...,6]
    22    plSymbol die_set("Die",die_type);  // Variable space for a die
    23    plValues die_value(die_set);       // A variable value for a die space
    24    plUniform P_die(die_set);          // Distribution of the variable space
    25
    26    /**********************************************************************
    27      Displaying the defined data
    28    ***********************************************************************/
    29    
    30    cerr<<"die_type = "<<die_type<<"\n";   // Print the type
    31    cerr<<"die_set = "<<die_set<<"\n";     // Print the variable set
    32    cerr<<"die_value = "<<die_value<<"\n"; // Print the variable values
    33    cerr<<"P_die : "<<P_die<<"\n\n";       // Print the kernel
    34
    35    /**********************************************************************
    36     Throwing the die
    37    ***********************************************************************/
    38    
    39    int i,n_times;
    40    cout<<"How many times shall I throw the die? : ";
    41    cin>>n_times;                  // Read the number of times to throw the die
    42    cout<<"\n";
    43
    44    for (i=0;i<n_times;i++) {
    45      cout<<i+1<<"th throw ";            
    46      P_die.draw(die_value);       // Getting a variable value with draw
    47      cout<<die_value<<endl;       // Print the die value
    48    }
    49
    50  }

As you should notice our code include line numbers. These numbers are not part of the code and they are used to better refer and explain programs. The file ``pl.h'' (line 11) should be included in all yours programs, the ProBT classes are defined there. Line 21 is the definition of a variable type going from one to six, that is die_type $= [1,2,\ldots,6]$. Line 22 defines a variable set or space composed of a one dimensional variable, die_set $=\{Die\}$ with $Die \in$ die_type. Note that we passed two arguments to the plSymbol constructor. The first argument, the print name, is a string that will be used when printing expressions containing the symbol. The second argument is the variable type. In our example the variable set contains a one dimensional variable, that's why it is a symbol (plSymbol). At the end of this section we will explain how to define a variable set with multiple variables in order to simulate throwing two or more dices. We arrive to line 23 defining a variable value for the space die_set. This variable value will be used for storing values such as $\{ Die = 6\}$, $\{ Die = 1\}$, etc. A built-in kernel is defined at line 24, P_die is defined with an uniform function $compute($die_set$) = 1/6$. The value $1/6$ is computed by ProBT, in this case by taking into account the cardinality of all the variables in die_set. At this stage, all the necessary data for our model is defined. Lines 30 to 33 display all the objects defined before. Line 33 displays the kernel P_die and the expression that is associated to its compute function, in this case the constant $1/6$. Finally, line 46 sets the variable values $die\_value$ by making a random selection with P_die. Note that the syntax is ``P_die.draw(die_value);'' rather than ``die_value=P_die.draw();'' this because of efficiency reasons^1.1.

The output of our program should be something like^1.2:

die_type = [1,2,...,6]
die_set = {Die}
die_value = {Die=1} 
P_die : P(Die) =  1/6

How many times shall I throw the die? : 6

1th throw {Die=6} 
2th throw {Die=3} 
3th throw {Die=5} 
4th throw {Die=5} 
5th throw {Die=6} 
6th throw {Die=2}

Note that the output produced by line 32 is ``die_value = {Die=1}'', in fact the variables in a variable value are initialized with the first value on the type, in this case 1. Let's modify Program 1 by replacing line 22 with :

plArray die_set("Die",1,2,die_type);

By making this die_set is defined as a variable set with two variables of type die_type that is die_set = { die_set(0), die_set(1)}. Somehow plArray die_set("Die",1,2,die_type) is similar to die_type die_set[2] in C syntax. By consequence the command :

plValues die_value(die_set);

generates a variable value storing values such as die_value= { die_set(0)=6, die_set(1)=4} or die_value= { die_set(0)=1, die_set(1)=4}. While a plSymbol contains a single symbol variable, a plArray contains an array of symbol of the same type. The second argument of plArray indicates the array dimension, in this case 1. The third argument indicates the number of elements. Later in section we fully explain these arguments. The simple fact of changing line 22 also changes the result of the kernel P_die, it is now defined with the uniform function $compute(die_set) = 1/36$. The result of line 47 will produce then a result such as {Die0 = 1, Die1=4}. A more sophisticated version of Program 1 is given by Program 2: throwing $m$ dice $n$ times.

Program 2: Throwing multiple dice.

     1  /*=============================================================================
     2   * File           : dice.cpp
     3   *=============================================================================
     4   *
     5   *------------------------- Description ---------------------------------------
     6   *   This program simulates throwing m dice n times
     7   *   
     8   *-----------------------------------------------------------------------------
     9  */
    10
    11  #include <pl.h>
    12
    13  main()
    14  {
    15   /**********************************************************************
    16       Defining the variable type, set and values plus the kernel for the
    17       variable set
    18   ***********************************************************************/ 
    19    
    20    plIntegerType die_type(1,6);          // Variable type for a die [1,2,...,6]
    21
    22    int m_dice;
    23    cout<<"How many dice do you want ? : ";
    24    cin>>m_dice;
    25    cout<<"\n";
    26
    27    plArray dice_set("Die",die_type,1,m_dice);  // Variable space for dice
    28    plValues dice_value(dice_set);              // A variable value for dice space
    29    plUniform P_dice(dice_set);                 // Distribution of the dice space
    30
    31   /**********************************************************************
    32      Displaying the defined data
    33    ***********************************************************************/
    34    
    35    cerr<<"die_type = "<<die_type<<"\n";     // Print the type
    36    cerr<<"dice_set = "<<dice_set<<"\n";     // Print the variable set
    37    cerr<<"dice_value = "<<dice_value<<"\n"; // Print the variable values
    38    cerr<<"P_dice : "<<P_dice<<"\n\n";       // Print the kernel
    39
    40   /**********************************************************************
    41     Throwing the dice
    42    ***********************************************************************/
    43    
    44    int i,n_times;
    45    cout<<"How many times shall I throw the dice ? : ";
    46    cin>>n_times;
    47    cout<<"\n";
    48
    49    for (i=0;i<n_times;i++) {
    50      cout<<i+1<<"th throw ";            
    51      P_dice.draw(dice_value);        // Getting a variable value with draw
    52      cout<<dice_value<<endl;         // Print the die value
    53    }
    54
    55  }

The output of Program 2 is then something like:

How many dice do you want ? : 5

die_type = [1,2,...,6]
dice_set = {Die0 Die1 Die2 Die3 Die4}
dice_value = {Die0=1 Die1=1 Die2=1 Die3=1 Die4=1} 
P_dice : P(Die0 Die1 Die2 Die3 Die4) =  1/7776

How many times shall I throw the dice ? : 6

1th throw {Die0=6 Die1=3 Die2=5 Die3=5 Die4=6} 
2th throw {Die0=2 Die1=3 Die2=5 Die3=2 Die4=4} 
3th throw {Die0=3 Die1=4 Die2=3 Die3=4 Die4=6} 
4th throw {Die0=6 Die1=4 Die2=5 Die3=1 Die4=4} 
5th throw {Die0=1 Die1=2 Die2=1 Die3=5 Die4=1} 
6th throw {Die0=3 Die1=1 Die2=1 Die3=6 Die4=2}