Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Football (soccer)

If, during a football match, there is a total of k goals scored (by both teams), we can consider the game as divided into (k+1) time-intervals (the count includes the initial interval before the first goal, as well as the interval after the last goal). During some of those time-intervals there may well be a (temporary) draw. Given the final score, we want to find the expected number of such intervals.

We may assume that, at any stage, the probability of a team scoring the next goal is proportional to the number of goals it has yet to score. For example, if the final score is 3-2 and at some stage during the game the score is 1-1, team A has two more goals to score and team B has one more. So the probability of team A scoring the next goal is 2/3 and that of team B is 1/3.

Given a final score of 3-2, there are 10 different ways that the game may develop (the letters 'a' and 'b' mark the order of scoring by the two teams and asterisks mark the time-intervals during which there is a draw):

*aaabb
*aabab
*aabb*a
*ab*aab
*ab*ab*a
*ab*ba*a
*ba*aab
*ba*ab*a
*ba*ba*a
*bbaa*a

We can see that, if the final score is 3-2, the expected number of time-intervals during which there is a draw is
E(3,2) = E(2,3) = 22/10 = 11/5 = 2.2

Find E(20, 19) as a reduced fraction.

Remarks
1. With a bit of care, 32-bit integers are sufficient for E(14,15) and 64-bit ints are good enough at least up to E(25,25).

2. Up to about E(14,15) one can simply go through all the possible arrangements and count the required cases, with less than one minute cpu time. For the higher numbers, I don't think that this is an option.

3. An equivalent problem is "Counting Votes".
While reading off (at random) and counting the votes of two candidates, there may be one or more instances when both of them have the same number of votes.
Given the final count of votes that the two candidates received (x and y), calculate the expected number of such instances E'(x,y).
[ Now, however, it is perhaps appropriate to skip the time-interval before the counting starts, so the asterisks at the beginning of each line must be deleted and E(x,y) should be reduced by 1, ie E'(2,3)=E'(3,2)=12/10=6/5 ].

Variant B. (I found it much harder to get to grips with this version.)
Instead of assuming that "...at any stage, the probability of a team scoring the next goal is proportional to the number of goals it has yet to score", we might say:

"At any stage, the probability of a team scoring the next goal is:
(a) 0.5, if neither team has reached their final score yet,
(b) zero, if a team has reached their final score, and
(c) one, if a team has not reached their final score yet, whereas their opponents have."

For the 3-2 case, the same ten sequences exist as previously listed, but now each sequence has a different probability.
So, this is a different problem with different answers (and it cannot be realistically converted to a corresponding "counting votes" problem).

Find F(2,3), F(14,15), F(20,19).

joshbowman205
Posts: 59
Joined: Wed Oct 31, 2007 4:28 pm

### Re: Straight algorithmic questions

Edit by harryh: The first paragraph is a response to this post, now on a separate topic /Edit

Just that they are about what is expected for an average of 3.5 per roll. Without anything to test the program on
should need: 24*size_of_int*board_size2 bytes of memory, about 25MB

Some others ( i think )
Football
E(3,2): 11/5
E(14,15): 57414019/9694845
E(19,20): 240416274739/34461632205

Variant B
E(3,2): 35/16
E(14,15): 319385207/67108864
E(19,20): 374557902443/68719476736

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

### Re: Straight algorithmic questions

Football : Yes, all your answers agree exactly with mine (so, either we are both correct or both wrong )

Die: When I first worked on that one (a couple of years ago), my approach needed lots of memory: (24*size2)2 ints. So I'll have to find some time and take a new look at it ...

Eigenray
Posts: 62
Joined: Mon Jul 14, 2008 5:20 pm

We can solve both just by counting: we find the probability of a tie on the 2n-th step.

In the original version, all strings are equally likely, so we just have E(a,b) = sumn=0a C(2n,n)C(a+b-2n,a-n)/C(a+b,a), assuming a <= b.

For the variant, it's a bit trickier. The probability of a string is proportional to 2x, where x is the length of the last run. (In particular, if A scores fewer points than B, then the most likely pattern is that A scores all their points first. Not the most realistic model.)

First suppose n < a <= b. Suppose a game has a tie at 2n. The probability of this game is 1/4n times the probability of the last (a+b)-2n letters, considered as a game with scores a-n, b-n. Therefore if we fix a string of n A's and n B's, the sum of the probabilities of all games with this initial string is just 1/4n, so the probability of a tie at 2n is just C(2n,n)/4n.

The tricky case is a tie at 2a. If a=b, this always happens of course. Otherwise, the game ends with an A followed by a string of (b-a)+k B's, where 0 <= k <= a. There are C(2a-1-k, a-1) such strings, and each has probability 2k/4a. But we actually have

sumk=1a C(2a-1-k, a-1)2k/4a = 1/2,

because the above is the probability that a game with scores (a,a) ends with a string of k A's for some k > 0. Adding the term when k=0, we get that the probability of a tie at 2a is 1/2 + C(2a-1,a-1)/4a = 1/2*(1 + C(2a,a)/4a).

So finally we have
F(a,a) = 1 + sumn=0a-1 C(2n,n)/4n,
F(a,b) = 1/2*(1 + C(2a,a)/4a) + sumn=0a-1 C(2n,n)/4n, if a<b.

For the original we have E(a,a) ~ sqrt(pi a), but if b/a converges to some value c > 1, then E(a,b) converges to (c+1)/(c-1). For the variant, F(a,a) ~ 2 sqrt(a/pi), and F(a,b) depends only on min(a,b) as long as a != b.