A regatta is a series of sailboat races. In the fleet where I race, the regatta winner is determined using a method called "Low Point Scoring". In any given race, the 1st place boat gets 1 point, the second place boat gets 2 points, the nth place boat receives n points. Individual races never have ties for any positions. The overall regatta is won by the boat with the lowest total number of points for all races. (If there is a tie for lowest total points, then the regatta is won by whichever of the tied boats had the better performance in the last race).
Consider a relatively small fleet of only 4 boats, each of which is equally likely to win any given race.
a) If there are only two races, the boat that wins the regatta will have a score of 2, 3, 4 or possibly even 5. What is the expected value of the winning score?
b) If there are three races, what is the expected value of the winning score? (I found even this simple case hard to calculate exactly, and I am hoping that somebody will come up with a better method than mine. And yes, I know that it is easy to simulate.)
c) If there is a large number of races, how might I approximate the expected winning score? (Among other things, I think I'd welcome a simulation here)
Any given regatta will have 1st, 2nd, 3rd and 4th place winners for the first race. The ultimate total of the winning boat will depend on how these boats finish in the remaining n1 races. There are 24 equally likely orders of finish in each of the remaining races, identifying each boat by its order of finish in the first race.
If there are 2 races, then, there are 24 distinguishable outcomes, based on how the placefarers in the first race do in the second.
If there are 3 races, there are 24*24 = 576 distinguishable outcomes. With 4 races there would be 24^3 = 13824 distinguishable outcomes. ... etc.
The following table lists, per number of races: the expected value of the winning score, the expected value divided by the number of races (sort of a perrace average), the raw number of points accumulated over all possible equally likely outcomes, the number of those equally likely outcomes, and the latter two numbers reduced by their gcd:
2 3.125 1.5625 75 24 25 8
3 5.170138888888889 1.72337962962963 2978 576 1489 288
4 7.327690972222222 1.831922743055556 101298 13824 16883 2304
5 9.513979311342593 1.902795862268519 3156510 331776 526085 55296
6 11.73184618537809 1.955307697563014 93416280 7962624 3892345 331776
7 13.9726596199109 1.99609423141584 2670216836 191102976 667554209 47775744
so for example, for 3 races there are 24^2 = 576 possible outcomes (relative to the order of the first race's outcome), and the total of the winners scores was 2978, for an average winner's score of 2978/576 = 1489/288, or 5.17013888888... or 1.72337962962962... per race average.
The program producing this output was
DECLARE FUNCTION gcd# (a#, b#)
DECLARE SUB race ()
DECLARE SUB permute (a$)
CLEAR , , 25000
DEFDBL AZ
CLS
DIM SHARED t(4), tt, n, lvl, races
FOR i = 1 TO 4
t(i) = i
NEXT
FOR races = 2 TO 6
lvl = 1: tt = 0: n = 0
race
g = gcd(tt, n)
PRINT races; tt / n; TAB(23); tt / n / races; TAB(42); tt; n; TAB(62); tt / g; n / g
NEXT
FUNCTION gcd (a, b)
x = a: y = b
DO
q = INT(x / y)
r = x  y * q
x = y: y = r
LOOP UNTIL r = 0
gcd = x
END FUNCTION
. . .
DEFDBL AZ
SUB race
STATIC ctr
lvl = lvl + 1
a$ = "1234": h$ = a$
DO
FOR i = 1 TO 4
t(i) = t(i) + VAL(MID$(a$, i, 1))
NEXT
IF lvl = races THEN
low = 99999999
FOR i = 1 TO 4
IF t(i) < low THEN low = t(i)
NEXT
tt = tt + low
n = n + 1
ELSE
race
END IF
FOR i = 1 TO 4
t(i) = t(i)  VAL(MID$(a$, i, 1))
NEXT
permute a$
LOOP UNTIL a$ = h$
lvl = lvl  1
END SUB
The permute function is shown elsewhere on the site. The result for 7 races used the equivalent Visual Basic program as the Quick Basic program was running too slowly.
Note that the average points for the winner per race can't exceed 2.5, so it's possible that 2.5 is the limit reached asymptotically, so the overall expected value might approach, but not reach 2.5 * n, where n is the number of races.
The following program simulates a larger number of races:
DEFDBL AZ
RANDOMIZE TIMER
FOR races = 2 TO 7: GOSUB test: NEXT
races = 10: GOSUB test
races = 20: GOSUB test
races = 50: GOSUB test
races = 100: GOSUB test
END
test:
tt = 0: n = 0
FOR trial = 1 TO 100000
FOR i = 1 TO 4
t(i) = i
s(i) = i
NEXT
FOR race = 2 TO races
FOR i = 1 TO 3
r = i + INT(RND(1) * (5  i))
IF r > i THEN
SWAP s(i), s(r)
END IF
NEXT
FOR i = 1 TO 4
t(i) = t(i) + s(i)
NEXT
NEXT race
lowest = 999999999
FOR i = 1 TO 4
IF t(i) < lowest THEN lowest = t(i)
NEXT
tt = tt + lowest
n = n + 1
NEXT trial
PRINT races; TAB(5); tt / n; TAB(30); tt / n / races
RETURN
For comparison with the exact figures, it simulates n=2 through 7, then the higher numbers:
average total avg. total per race
2 3.12473 1.562365
3 5.1698 1.723266666666667
4 7.32807 1.8320175
5 9.51294 1.902588
6 11.7317 1.955283333333333
7 13.97819 1.996884285714286
10 20.79182 2.079182
20 44.05422 2.202711
50 115.61174 2.3122348
100 236.69128 2.3669128

Posted by Charlie
on 20051128 10:58:21 