I continue the discussion from last post. We are trying to add unpredictability to tennis by looking for a monotone, transitive and balanced function such that has a wide threshold window, that is, we want the range of where is, say, between 0.01 and 0.99, to be as large as possible. A formal treatment of this problem could be found in the seminal paper of Kalai and Freidgut. The major simplifying step we take is to look at the derivative of at the point as a proxy for the width of the window. Think of it as the first order linear approximation for the (inverse of the) width of the threshold window: the smaller the derivative the wider the window.
The main tool to help us reason about the derivative is Russo’s formula, but first a definition: given we say that bit is pivotal if flipping changes the value of . The total influence of the function is the expected number of pivotal bits when are drawn uniformly at random. Russo’s formula states that for monotone functions the derivative of at is exactly the total influence of !
One way to see why Russo’s formula makes sense is to think about the definition of a derivative and observe that increasing by a small amount could be thought of as picking a bit at random and setting it to 1. Now, the probability that changes its value is proportional to the number of pivotal bits.
We now face a well-defined challenge of coming up with a function satisfying our constraints and with small total influence. As a sanity check it is easy to observe that the total influence of the majority function is indeed roughly . The reason is that with probability about the majority is by exactly one point, in which case half the bits are pivotal.
What about majority of majorities, or better yet , recursive-majority of three values? Well, the total influence of recursive majority can be computed to be roughly , which is an improvement over simple majority (not surprising since simple majority could be shown to have the maximal total influence of all monotone Boolean functions). But is it the best?
The answer is given in the celebrated theorem by Kahn, Kalai and Linial which implies in our case that the total influence is . A tight example was provided by Ben-Or and Linial in the TRIBES function. In the TRIBES function the bits are partitioned to sets (‘tribes’) of roughly – bits each. Player ‘1’ wins if there is a tribe with all its bits set to 1. Player ‘0’ wins otherwise. The function is clearly transitive and monotone. Exact parameters can be set so that it is approximately balanced. To see that the total influence is small observe that for a bit to be pivotal it has to belong to a tribe where all the other bits are 1, which happens with probability about so the total influence is .
So is TRIBES a good candidate for an athletic game? I don’t think so, for several reasons. First, it is not exactly balanced, I can’t imagine an athlete happy with a game where he is unlikely to win even when competing on equal grounds point by point. Second, there is a difference between the role of player 1, which plays offense trying to obtain a tribe, and player 0 which plays defense trying to block player 1. Both problems are rectified by adding another requirement. We want the function to be symmetric, that is . This means that when flipping all bits the outcome also flips and since is also monotonic it also means it is balanced.
Here is a suggestion for a transitive, monotone, symmetric function, with low total influence. We call it Cycle-Run and it could be viewed as a symmetric version of TRIBES. Call a consecutive sequence of ‘1’’s a 1-run. Similarly a consecutive sequence of zeros is a ‘0-run’. We allow runs to wrap around, so if a run reaches it may continue with . The value of is determined as follows:
- Check which player has the longest run.
- In case of tie check which player has a larger number of maximal runs.
- In case of tie check the total length of segments between maximal runs, where a segment starting from a 1-run clockwise is counted for the 1-player and a segment starting at a 0-run clockwise is counted for the 0-player. The player that has a larger total count is declared the winner.
In the example below both players have a single maximal run of length 3, but player 0 wins the tie breaker 9-2.
Monotonicity and symmetry are readily verifiable. Transitivity is obtained via rotations of the cycle. Why is the total influence logarithmic? One way to see it is to observe that the expected number of runs of length is , so the expected number of runs longer than is smaller than 1. Further work is required, but basically this is the reason. If you want to do the calculations yourself you may find this survey useful.
So is this useful? In practice most tennis matches consist of roughly 200-400 points. Below we plot Majority, Recursive Majority and Cycle-Run for n=243.
We see that indeed Majority has the narrowest threshold window and Cycle-Run the widest. The difference between Cycle-Run and Recursive-Majority is not that big. When the probability of an upset rises from roughly 3% to 5.3%. Asymptotics however don’t lie and when n is increased to 2187 the differences are quite striking.
Now, when , for simple majority the probability of an upset is negligible. For recursive majority it is less than 2% and for cycle run it is more than 11%.
What about real life? I have the data of three tennis matches.
In these three examples all rules have the same result. An anecdotal observation is that at least in these cases the winning run tends to be very close to the end of the match, suggesting that the mental aspect of the game plays an important role.
So should we petition the ATP for a rule change?
This post is the outcome of discussions with Parikshit Gopalan, Yuval Peres, Omer Reingold and Kunal Talwar.
The data was given to me through the generosity of Daniele Paserman and the facilitation of Ran Abramitzky.