formed without requesting additional examples. This iteration requires .0257n additional majority-class examples. The best-performing distribution contains 10% minority-class examples. Total Budget: .0860 n (.0297n minority, .0563n majority). 

j = 2 Training-set size = 1/8 n. Since the 10% distribution performed best, the beam search evaluates the 5%, 10%, and 18.2% minority-class distributions. The 20% class distribution is also evaluated since this requires only .0250n of the .0297n previously obtained minority-class examples. A total of .1188n (95% of 1/8 n) majority-class examples are required. The best performing distribution contains 10% minority-class examples. This iteration requires .0625n additional majority-class examples. Total Budget: .1485n
(.0297n minority, .1188n majority). 

j = 3 Training-set size = 1/4 n. The distributions to be evaluated are 5%, 10%, and 18.2%. 

There are no "extra" minority-class examples available to evaluate additional class distributions. This iteration requires .0455n (18.2% of 1/4 n) minority-class examples and 
.2375n (95% of 1/4 n) majority-class examples. The best-performing class distribution contains 10% minority-class examples. Total Budget: .2830n (.0455n minority, .2375n majority) 
j = 4 Training-set size = 1/2 n. The 5%, 10%, and 18.2% class distributions are evaluated. 

This iteration requires .0910n (18.2% of 1/2 n) minority-class examples and .4750n (95% 
of 1/2 n) majority-class examples. The best-performing distribution contains 10% minority-class examples. Total Budget: .5660n (.0910n minority, .4750n majority). 

j = 5 Training-set size = n. For this last iteration only the best class distribution from the previous iteration is evaluated. Thus, a data set of size n is formed, containing .1n minorityclass examples and .9n majority-class examples. Thus .0090n additional minority-class examples and .4250n additional majority-class examples are required. Since all the previously obtained examples are used, there is no "waste" and the budget is not exceeded. 

Total Budget: 1.0n (.1000n minority, .9000n majority) 
Table C1: A Detailed Example of the Sampling Algorithm (Phone Data Set using Error Rate) 

| Expressed as a fraction on n   |                        |             |       |                   |          |                 |       |
|--------------------------------|------------------------|-------------|-------|-------------------|----------|-----------------|-------|
| j                              | size                   | class-distr | best  | min-need maj-need | minority | majority budget |       |
| 0 1/32 n all                   | 18.2%                  | .0297       | .0306 | .0297             | .0306    | .0603           |       |
| 1 1/16 n 10, 18.2 , 20, 30, 40 | 10%                    | .0250       | .0563 | .0297             | .0563    | .0860           |       |
| 2                              | 1/8 n 5, 10 , 18.2, 20 | 10%         | .0250 | .1188             | .0297    | .1188           | .1485 |
| 3                              | 1/4 n 5, 10 , 18.2     | 10%         | .0455 | .2375             | .0455    | .2375           | .2830 |
| 4                              | 1/2 n 5, 10 , 18.2     | 10%         | .0910 | .4750             | .0910    | .4750           | .5660 |
| 5                              | 1 n 10                 | .1000       | .9000 | .1000             | .9000    | 1.0000          |       |

Table C2: Compact Description of the Results in Table B1a for the Phone Data Set 