SYSTEM AND METHOD FOR BOUNDING MEANS OF DISCRETE-VALUED DISTRIBUTIONS

1 . A method implemented on at least one processor, a memory, and a communication platform for characterizing data, comprising:

receiving data including categorical classes and a number of observations with respect to each of the categorical classes, wherein each of the categorical classes is associated with a category value and the categorical classes are arranged in a first order based on their corresponding category values;

determining a total of observations based on the numbers of observations with respect to the respective categorical classes; and

estimating a bound of an average value of the data based on the categorical classes, the total of observations, and the numbers of observations with respect to the categorical classes in accordance with a dot product of a probability vector and a categorical class vector comprising the category values of the categorical classes.

2 . The method of claim 1 , wherein observations associated with the categorical classes correspond to a discrete-valued distribution.

3 . The method of claim 1 , wherein the category value associated with each of the categorical classes represents an assessment of a return value associated with the categorical class.

4 . The method of claim 1 , wherein

the bound of the average value of the data is specified by a lower bound and an upper bound;

the lower and upper bounds are estimated based on the data with respect to an expected confidence level.

5 . The method of claim 4 , wherein the upper bound of the average value of the data is estimated by:

generating the categorical class vector V=[v 1 , v 2 , . . . , v m ] and the corresponding number of observations to generate a sample number vector K=[k 1 , k 2 , . . . , k m ], wherein m represents a number of categorical classes;

calculating

a plurality oft measures, t 0 , t 1 , . . . t m , wherein t 0 =0, t m =1, t i =lower bound of (n, k 1 +k 2 + . . . +, k i , d) for 1<=i<m, where d is a function of the expected confidence level, and

the probability vector P=[p 1 , p 2 , . . . , p m ] with p i =t i −t i−1 ; and

computing the upper bound of the average value as the dot product of vectors P and V.

6 . The method of claim 4 , further comprising

reversing the first order of the categorical classes to generate a reversed categorical class vector −V=[v m , v m−1 , . . . , v 1 ] in a second order;

reversing the order of the number of observations corresponding to the reversed categorical classes to generate a reversed sample number vector −K=[k m , k m−1 , . . . , k 1 ].

7 . The method of claim 6 , wherein the lower bound of the average value is computed by

calculating

a plurality of reversed t measures, t 0 , t 1 , . . . t m , wherein t 0 =0, t m =1, t i =lower bound of (n, (k m )+(k m−1 )+(−k i ), d) for 1<=i<m, and

a reversed probability vector −P with m probability measures, including p i =t i −t i−1 ; and

computing the lower bound of the average value as the dot product of the reversed categorical class vector −V and the reversed probability vector −P.

8 . Machine readable and non-transitory medium having information recorded thereon for characterizing data, wherein the information, when read by the machine, causes the machine to perform the following steps:

receiving data including categorical classes and a number of observations with respect to each of the categorical classes, wherein each of the categorical classes is associated with a category value and the categorical classes are arranged in a first order based on their corresponding category values;

determining a total of observations based on the numbers of observations with respect to the respective categorical classes; and

estimating a bound of an average value of the data based on the categorical classes, the total of observations, and the numbers of observations with respect to the categorical classes in accordance with a dot product of a probability vector and a categorical class vector comprising the category values of the categorical classes.

9 . The medium of claim 8 , wherein observations associated with the categorical classes correspond to a discrete-valued distribution.

10 . The medium of claim 8 , wherein the category value associated with each of the categorical classes represents an assessment of a return value associated with the categorical class.

11 . The medium of claim 8 , wherein

the bound of the average value of the data is specified by a lower bound and an upper bound;

the lower and upper bounds are estimated based on the data with respect to an expected confidence level.

12 . The medium of claim 11 , wherein the upper bound of the average value of the data is estimated by:

generating the categorical class vector V=[v 1 , v 2 , . . . , v m ] and the corresponding number of observations to generate a sample number vector K=[k 1 , k 2 , . . . , k m ], wherein m represents a number of categorical classes;

calculating

a plurality of t measures, t 0 , t 1 , . . . t m , wherein t 0 =0, t m =1, t i =lower bound of (n, k 1 +k 2 + . . . , k i , d) for 1<=i<m, where d is a function of the expected confidence level, and

the probability vector P=[p 1 , p 2 , . . . , p m ] with p i =t i −t i−1 ; and

computing the upper bound of the average value as the dot product of vectors P and V.

13 . The medium of claim 11 , wherein the information, when read by the machine, further causes the machine to perform the following steps:

reversing the first order of the categorical classes to generate a reversed categorical class vector −V=[v m , v m−1 , . . . , v 1 ] in a second order;

reversing the order of the number of observations corresponding to the reversed categorical classes to generate a reversed sample number vector −K=[k m , k m−1 , . . . , k 1 ].

14 . The medium of claim 13 , wherein the lower bound of the average value is computed by

calculating

a plurality of reversed t measures, t 0 , t 1 , . . . t m , wherein t 0 =0, t m =1, t i =lower bound of (n, (k m )+(k m−1 )+ . . . , (−k i ), d) for 1<=i<m, and

a reversed probability vector −P with m probability measures, including p i =t i −t i−1 ; and

computing the lower bound of the average value as the dot product of the reversed categorical class vector −V and the reversed probability vector −P.

15 . A system for characterizing data, comprising:

a data categorization unit configured for receiving data including categorical classes, wherein each of the categorical classes is associated with a category value and the categorical classes are arranged in a first order based on their corresponding category values;

a category observation extractor configured for identifying a number of observations from the data with respect to each of the categorical classes;

a category total determination unit configured for determining a total of observations based on the numbers of observations with respect to the respective categorical classes; and

a bound estimation mechanism configured for estimating a bound of an average value of the data based on the categorical classes, the total of observations, and the numbers of observations with respect to the categorical classes in accordance with a dot product of a probability vector and a categorical class vector comprising the category values of the categorical classes.

16 . The system of claim 15 , wherein observations associated with the categorical classes correspond to a discrete-valued distribution.

17 . The system of claim 15 , wherein the category value associated with each of the categorical classes represents an assessment of a return value associated with the categorical class.

18 . The system of claim 15 , wherein

the bound of the average value of the data is specified by a lower bound and an upper bound;

the lower and upper bounds are estimated based on the data with respect to an expected confidence level.

19 . The system of claim 18 , wherein the bound estimation mechanism includes an upper bound estimation unit for determining the upper bound of the average value of the data by:

generating the categorical class vector V=[v 1 , v 2 , . . . , v m ] and the corresponding number of observations to generate a sample number vector K=[k 1 , k 2 , . . . , k m ], wherein m represents a number of categorical classes;

calculating

a plurality oft measures, t 0 , t 1 , . . . t m , wherein t 0 =0, t m =1, t i =lower bound of (n, k 1 +k 2 + . . . , k i , +d) for 1<=i<m, where d is a function of the expected confidence level, and

the probability vector P=[p 1 , p 2 , . . . , p m ] with p i =t i −t i−1 ; and

computing the upper bound of the average value as the dot product of vectors P and V.

20 . The system of claim 18 , wherein the bound estimation mechanism further comprises a lower bound estimation unit configured for determining the lower bound of the average value of the data by:

reversing

the first order of the categorical classes to generate a reversed categorical class vector −V=[v m , v m−1 , . . . , v 1 ] in a second order, and

the order of the number of observations corresponding to the reversed categorical classes to generate a reversed sample number vector −K=[k m , k m−1 , . . . , k 1 ];

calculating

a plurality of reversed t measures, t 0 , t 1 , . . . t m , wherein t 0 =0, t m =1, t i =lower bound of (n, (k m )+(k m−1 )+ . . . , (−k i ), d) for 1<=i<m, and

a reversed probability vector −P with m probability measures, including p i =t i −t i−1 ; and

computing the lower bound of the average value as the dot product of the reversed categorical class vector −V and the reversed probability vector −P.