1 #!/usr/bin/ocamlrun /usr/bin/ocaml
  2 (**
  3     n number of actors
  4     t number of possible events in a sequence (eg 365 days per year)
  5     e number of critical events per actor (eg 1 birthday per year)
  6     s is a sequence of length t giving when the critical events happened for
  7         each actor
  8     S is the set of all possible sequences (for a given t, n, e)
  9     a critical cooccurence is an event where all actors have a critical event
 10 *)
 11 
 12 (** Arbitrary precision numbers *)
 13 #load "nums.cma";;
 14 open Num
 15 
 16 (** x choose n **)
 17 let choose x n =
 18     let num = ref (num_of_int 1) in
 19     let den = ref (num_of_int 1) in
 20     let diff = x -/ n in
 21     for i = (int_of_num (diff +/ (num_of_int 1))) to (int_of_num x) do
 22         num := (num_of_int i) */ !num
 23     done;
 24     for i = 1 to (int_of_num n) do
 25         den := (num_of_int i) */ !den
 26     done;
 27     let answer = !num // !den in
 28     print_string ("choose " ^ (string_of_num x) ^ " " ^ (string_of_num n) ^
 29             " = " ^ (string_of_num !num) ^ " / " ^ (string_of_num !den) ^ " = " ^
 30             (string_of_num answer) ^ "\n");
 31     answer
 32 
 33 
 34 (** [countPossibleSequences numActors numCritEvents numEvents] is the number
 35     of distinct outcomes possible when [numActors] actors each have [numCritEvents]
 36     critical events in a series of length [numEvents]. This returns how many unique
 37     sequences are possible.
 38 *)
 39 let countPossibleSequences numActors numCritEvents numEvents =
 40     (*number of ways one actor can distribute numCritEvents over numEvents tries*)
 41     let x = choose numEvents numCritEvents in
 42     (* every actor has x possibilities, multiply together *)
 43     let possSequences = x **/ numActors in
 44         print_string ("countPossibleSeqs (numEvents=" ^
 45             (string_of_num numEvents) ^ " numActors=" ^ (string_of_num numActors) ^
 46             " numCritEvents=" ^ (string_of_num numCritEvents) ^") = " ^
 47             (string_of_num possSequences) ^ "\n");
 48     possSequences
 49 (** [exactlyXCriticalOccurences x numEvents numActors numCritEvents] gives the 
 50     number of sequences that have exactly x critical occurences with the given
 51     parameters. x must be < numCritEvents. 
 52 *)
 53 let rec exactlyXCriticalCooccurences x numEvents numActors numCritEvents =
 54     (**First calculate the total number of sequences that have (at least)
 55     x critical cooccurences. The number of ways x critEvents can be picked out 
 56     of the total numEvents, multiplied by the number of ways the remaining
 57     critical events can picked out of the remaining numEvents*)
 58     let atLeastXCrit = (choose numEvents x) */
 59             (countPossibleSequences numActors (numCritEvents -/ x) (numEvents -/ x))
 60     in
 61     print_string ("atLeastXCrit (x=" ^ (string_of_num x) ^ " numEvents=" ^
 62         (string_of_num numEvents) ^ " numActors=" ^ (string_of_num numActors) ^
 63         " numCritEvents=" ^ (string_of_num numCritEvents) ^") = " ^
 64         (string_of_num atLeastXCrit) ^ "\n");
 65     if (x = numCritEvents) then
 66     (* if x is the number of critEvents each actor has, there's no risk of counting
 67     a sequence with more than x *)
 68     atLeastXCrit
 69     else
 70     begin
 71         (* otherwise tally the number of sequences with more than x critical 
 72         cooccurences *)
 73         let doubleCounts = ref (num_of_int 0) in
 74         for i = ((int_of_num x) + 1) to (int_of_num numCritEvents) do
 75             doubleCounts := !doubleCounts +/ (
 76                     (exactlyXCriticalCooccurences (num_of_int i)
 77                     numEvents numActors numCritEvents) */
 78                     (choose (num_of_int i) x))
 79         done;
 80         let answer = atLeastXCrit -/ !doubleCounts in
 81             print_string ("exactlyXCritCo (x=" ^ (string_of_num x) ^ " numEvents=" ^
 82             (string_of_num numEvents) ^ " numActors=" ^ (string_of_num numActors) ^
 83             " numCritEvents=" ^ (string_of_num numCritEvents) ^") = " ^
 84             (string_of_num answer) ^ "\n");
 85         answer
 86     end
 87 (** given the number of Critical events per actor per numEvents, returns the
 88     expected number of co-occurences of all actors having a critical event at
 89     the same time every numEvents. 
 90 
 91     eg, if a critical event is a failure, and the actors are redundant systems 
 92     that do the same thing, this returns the number of times all systems are 
 93     expected to fail at the same time in numEvents if each system fails 
 94     numCritEvents in that time period.
 95     *)
 96 
 97 let expectedCriticalCooccurences numEvents numActors numCritEvents =
 98     (* calculate a weighted average of the number sequences that have some
 99     number of critical coocurrences*)
100     let weightedSum = ref (num_of_int 0) in
101     for i = 1 to (int_of_num numCritEvents) do
102         weightedSum := !weightedSum +/ ((num_of_int i) */
103                 (exactlyXCriticalCooccurences (num_of_int i) numEvents
104                 numActors numCritEvents))
105         done;
106     let possibleSequences =
107             countPossibleSequences numActors numCritEvents numEvents in
108     let expectedCrits = !weightedSum // possibleSequences in
109     print_string ("expectedCritCo ( numEvents=" ^
110             (string_of_num numEvents) ^ " numActors=" ^ (string_of_num numActors) ^
111             " numCritEvents=" ^ (string_of_num numCritEvents) ^") = " ^
112             (string_of_num expectedCrits) ^ "\n");
113     expectedCrits
114 
115 
116 
117 let _ = print_string (" \n\nExpected critical Cooccurence sequences: " ^
118         (string_of_num (expectedCriticalCooccurences
119         (Int 365) (Int 3) (Int 50))) ^ "\n\n")