An Algorithm Challenge (finding the five fastest horses out of a large group)

[Vanadium 50]

@PeroK I don't follow your reasoning, but we might be saying the same thing.

I know there are four horses faster than A5: A1, A2, A3 and A4.
I know that there are eight horses faster than E5: A1, B1, C1, D1, E1, E2, E3 and E4.
So on average, A5 is faster than E5.

Ready for the extra extra credit?

Running a similation on a computer may be harder than it appears. There are a lot of ways to place 25 horses in 25 slots (liike 25!) so you need to worry about uniformity of sampling.

Instead I have been thinking about average ranking. If you consider a two lane track and 4 horses, B1 is slightly faster (n average) than A2. The reason is that being the slowest horse is a possibility for A2 but not for B1. Another way to look at it is that, going back to the original problem, B1 is known to be faster than 4 other horses, but A2 is only known to be faster than 3.

 

[Frabjous]

Edited: Wrong answer

 

[Vanadium 50]

I think you have to be verty careful about "equal probability". Certain cases have been eliminatedl

For example, E5 cannot be 9 if E4 is 10.

Similarly, B1 is likely to be faster than A2. To be B1 you need to beat 19 horses. To be A2 you only need to beat 3.

 

[Frabjous]

I think you have to be verty careful about "equal probability". Certain cases have been sliminated.

For example, E5 cannot be 9 if E4 is 10.

Similarly, B1 is likely to be faster than A2. To be B1 you need to beat 19 horses. To be A2 you only need to beat 3.

Agreed. My answer is wrong.

 

[PeroK]

I’ll be the idiot.
After the first five races, there is equal probability (1/5) that that slowest horse is A5,B5,C5, D5 or E5.
The sixth and seventh race only involve horses with zero probability of being the slowest. Given that we have learned nothing new about the slowest, the probabilities do not change.
What am I doing wrong?

One way to look at this is to place the fastest horse in a group at random, then place the slowest horse in a group at random. There is, therefore, a probability of $\frac 4 {24} = \frac 1 6$ that the fastest and slowest horses are in the same group. This is less than the naive $\frac 1 5$. That means that the probability that A5 is the slowest horse is $\frac 1 6$.

Note that if you try the same trick by placing the second fastest horse first, then there is also a probability of $\frac 1 6$ that the second fastest and slowest horses are in the same group. But, there is also a probability that the fastest horse in is that group, so that the slowest horse is not necessarily B5 in this case. Also, that's not the only way that B5 will be the slowest horse. If the two fastest horses are in the same group, then B1 might be the third fastest horse etc.

 

[PeroK]

@PeroK I don't follow your reasoning, but we might be saying the same thing.

I know there are four horses faster than A5: A1, A2, A3 and A4.
I know that there are eight horses faster than E5: A1, B1, C1, D1, E1, E2, E3 and E4.
So on average, A5 is faster than E5.

Ready for the extra extra credit?

Running a similation on a computer may be harder than it appears. There are a lot of ways to place 25 horses in 25 slots (liike 25!) so you need to worry about uniformity of sampling.

The idea is that the original draw into five groups is uniformly random. We can then calculate various probabilities, such as the probability that the fastest and slowest horses are in the same race etc.

The initial set of five races effectively sorts the horses in each group. That gives us no new information about the distribution. Likewise the WOW race simply sorts the groups. We can't yet tell anything about the initial random distribution of horses from this. Each initial random distribution is still equally likely. All this has done is label the horses A1-E5. I was planning to calculate the average rank for each horse from this. That's a straightforward exercise. I could probably do a sample size of 1-10 million, but not all $25!$.

The result of the playoff race between A2, A3, B1, B2, C1 will eliminate some of the initial possible distributions. But, there are many possibilities for the result of this race. If we pick a single possible outcome, such as B1-A2-C1-A3-B2, then we can recalculate the various probabilities, based on this knowledge of the distribution. I wasn't intending to do this.

 

[PeroK]

PS to show the idea, let's assume only four horses and two races with two horses in each. There are only three equally likely possibilities for the initial distribution. Let's label the horses from fastest to slowest F1-F4:

Group A: F1, F2
Group B: F3, F4

Group A: F1, F3
Group B: F2, F4

Group A: F1, F4
Group B: F2, F3

We can see immediately why the slowest horse (F4) is more likely to be in group B than group A. And, we can calculate the average rank of horses A1-B2:

A1 = 1, A2 = 3, B1 = 7/3, B2 = 11/3

This shows that, indeed, B2 is on average slower than A2. And, also, on average B1 is faster than A2.

It also raises the question of whether I should simulate a head-to-head race between A5 and E5; or, as I was intending, calculate the average rank of each horse in the range 1-25. I might even be able to do the former analytically.

 

[PeroK]

PPS I did a quick calculation for nine horses in three races. Horse A3 is faster than C3 with probability $\frac {181}{280}$. In the case of four horses above, the probability that A2 is faster than B2 is $\frac 2 3$.

It doesn't look like there is a nice formula to extend to twenty-five horses, so I'll have to resort to Python.

 

[PeroK]

Here's the result of a simulation of 10 million random draws of 25 horses.

A5 is faster than E5 0.61
Average rank for group A [1.0, 6.0, 11.0, 16.0, 21.0]
Average rank for group B [2.19, 6.95, 11.72, 16.48, 21.24]
Average rank for group C [3.68, 8.14, 12.61, 17.07, 21.53]
Average rank for group D [5.71, 9.76, 13.82, 17.88, 21.94]
Average rank for group E [9.09, 12.47, 15.85, 19.24, 22.62]

As predicted, A5 is faster than E5 most of the time (about 61%). That said, there's not a lot to choose between the horses that finish last in each race!

Before running the play-off race, the most likely top three horses are the first three in the WOW race: A1, B1 and C1. It's quite easy to work out that B1 is usually the second fastest horse (with probability $\frac 5 6$).

Very much as predicted, although it's good to see the numbers come out!

 

[PeroK]

Here's the Python code:

import random
#
# Choose the number of times to run the simulation
num_sim = 10_000_000
#
# Count the number of times A5 beats E5
a5_win = 0
#
# g_list keeps a tally of relative rank of horses A1-A5, B1-B5 etc.
g_list=[[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0],[0,0,0,0,0]]
#
for k in range(0, num_sim):
    horses = list(range(1,26))
    random.shuffle(horses)
#
#    Split the random selection into the five groups (first races)
#
    g_0 = [horses[0],horses[1],horses[2],horses[3],horses[4]]
    g_1 = [horses[5],horses[6],horses[7],horses[8],horses[9]]
    g_2 = [horses[10],horses[11],horses[12],horses[13],horses[14]]
    g_3 = [horses[15],horses[16],horses[17],horses[18],horses[19]]
    g_4 = [horses[20],horses[21],horses[22],horses[23],horses[24]]
#
# sorting each group equates to running the first set of races
#
    g_0.sort()
    g_1.sort()
    g_2.sort()
    g_3.sort()
    g_4.sort()
#
# sorting the list of lists equates to running the WOW race (by default Python sorts by the first nunber in each list)
    g_temp = [g_0,g_1, g_2, g_3, g_4]
#
    g_temp.sort()
#
#    Check whether A5 is faster than E5)
#
    if g_temp[0][4] < g_temp[4][4]:
        a5_win += 1
#
# Add the rankings for this race to the overall tally:
    for i in range(0, 5):
        for j in range(0, 5):
            g_list[i][j] += g_temp[i][j]
#
# Calculate the average rank for each horse:
for i in range(0, 5):
        for j in range(0, 5):
            g_list[i][j] = round(g_list[i][j]/num_sim,2)
#
print("A5 is faster than E5 {:.2f}".format(a5_win/num_sim))
print("Average rank for group A", g_list[0])
print("Average rank for group B", g_list[1])
print("Average rank for group C", g_list[2])
print("Average rank for group D", g_list[3])
print("Average rank for group E", g_list[4])

 

[PeroK]

Here's the result of another simulation to calculate the probability of which is the slowest horse (after the WOW race):

A5 is the slowest horse: 0.1675
B5 is the slowest horse: 0.1753
C5 is the slowest horse: 0.1879
D5 is the slowest horse: 0.2086
E5 is the slowest horse: 0.2608

Note that he probability that A5 is the slowest horse is $\frac 1 6$ as previously calculated precisely.

 

[Vanadium 50]

On the extra extra credit, it shows B4 is faster than A5, which I expected. Both lose to 4 other horses, but we know B4 is faster than one other horse - we don't know that for A5.

I was surprised that C3 was not 13.00.

 

[Vanadium 50]

Been playing with a much more subtle problem: identify the median-speed horse.

One reason this is subtle is the condition "fewest races" - is this on average? Or the smallest maximum guranteed to find the answer? Or something else?

 

[Hornbein]

Been playing with a much more subtle problem: identify the median-speed horse.

One reason this is subtle is the condition "fewest races" - is this on average? Or the smallest maximum guranteed to find the answer? Or something else?

Dunno. I'll have to check with the sheik.

 

[Hornbein]

If I understand the question, you can model this by considering the numbers 1-25 put at random into five groups of five. The numbers in each group are then sorted in ascending sequence. We then choose group A as the group with the number 1 in it. A1 is the number 1 and A5 is the highest number in that group. Group B is the group with the next lowest first number. E.g., if the number 2 is not in group A, then group B will be the group with the number 2 in it. Group E is the group with the highest first number.

It's clear than the distribution for E5 has a higher mean than the distribution for A5.

This could be simulated using a Python (or C++) script, or possibly calculated - if it wasn't so late in the day.

PS the lower the number, the faster the horse it represents.

Though I no longer play the game of bridge, I frequent a group of bridge players. They are confronted with such situations all the time. The also have the constraint of solving the problem without any aids and doing so in a timely manner. The problem is quite similar as the number of cards in a hand is fixed and a higher rank in one hand means lower ranks in the other hands.

The way they would approach this is called "empty spaces." In the A group we know that one of the horses isn't the slowest. This leaves 4 empty spaces in group A. The chance that A contains the slowest is 4/24 = 1/6. In the E group we know that none of the horses is in the top four. The chance that E contains the slowest is about 5/(25-4). That's 24%, as opposed to the simulation value of 26%. Close enough for bridge.

 

[Hornbein]

Dunno. I'll have to check with the sheik.

Sheik al-Abdullah said, "What may I ask is this "average" of which you are speaking?" When I tried to explain he replied, "I hear your words only as they rattle about in the deep well of time. The horses win or not win by the will of Allah, peace be upon him. So it is written." I elected not to pursue the matter further.