All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Winning The Regatta (Posted on 2005-11-28)
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)

 See The Solution Submitted by Steve Herman Rating: 4.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 2-7 races exactly; simulation above | Comment 2 of 6 |

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 n-1 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 place-farers 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 per-race 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 A-Z
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 A-Z
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 A-Z
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 2005-11-28 10:58:21

 Search: Search body:
Forums (0)