a football post?!

I am not interested in football, neither as a player (a primary school trauma when I was the last being picked!) or as a fan, contrary to my dad (who was a football referee in his youth) and my kids, but Gareth Roberts (University of Warwick) and Jeff Rosenthal wrote a paper on football draws for the (FIFA) World Cup, infamously playing in Qatar by the end of the year, which Gareth presented in a Warwick seminar.

For this tournament, there are 32 teams, first playing against opponent teams supposedly drawn from a uniform distribution over all draw assignments, within 8 groups of 4 teams, with constraints like 1-2 EU teams per group, 0-1 from the other regions. As done at the moment and on TV, the tournament is filled one team at time by drawing from Pot 1, then Pot 2, then Pot 3, & Pot 4. &tc.. Applying the constraints one draw at a time, conditional on the past draws and the constraints, rather obviously creates non-uniformity! Uniformity would be achievable by rejection sampling (with a success probability of 1/540!) But this is not televisesque enough…

A debiasing solution is found by using several balls for each team in the right proportion, correcting for the sequential draws. Still impractical when requiring 10¹⁴ balls…!

The fun in their paper is that the problem can be formulated as a particle filter, estimating the right probabilities by randomising the number of balls [hidden randomness] and estimating the probability for team j to be included by a few thousands draws. With some stratified sampling on the side to minimise randomness. Removing the need for the (intractable?) distribution is thus achieved by retrospective sampling, as in pseudo-marginal MCMC. Alternatively, one could swap pairs of teams by a simplistic MCMC algorithm, with no worry about stationarity and the possibility of on-screen draws. (Jeff devised a Java applet to simulate an actual draw.) Obviously, it is still a far stretch that this proposal will be implemented for the next World Cup. If so, I will watch it!

la finale

A very pleasant stroll through central Paris this afternoon, during “la” finale, when France was playing Croatia. Bars were all overflowing onto the pavements and sometimes the streets, each action was echoed throughout town, and we certainly did not miss any goal, even from the heart of the Luxembourg gardens! Which were deserted except for the occasional tourist, just as the main thoroughfares, except for police cars and emergency vehicles. Since the game ended, horns have been honking almost nonstop, even in the quietest suburbs.

the penalty method

“In this paper we will make conceptually simple generalization of Metropolis algorithm, by adjusting the acceptance ratio formula so that the transition probabilities are unaffected by the fluctuations in the estimate of [the acceptance ratio]…”

Last Friday, in Paris-Dauphine, my PhD student Changye Wu showed me a paper of Ceperley and Dewing entitled the penalty method for random walks with uncertain energies. Of which I was unaware of (and which alas pre-dated a recent advance made by Changye).  Despite its physics connections, the paper is actually about estimating a Metropolis-Hastings acceptance ratio and correcting the Metropolis-Hastings move for this estimation. While there is no generic solution to this problem, assuming that the logarithm of the acceptance ratio estimate is Gaussian around the true log acceptance ratio (and hence unbiased) leads to a log-normal correction for the acceptance probability.

“Unfortunately there is a serious complication: the variance needed in the noise penalty is also unknown.”

Even when the Gaussian assumption is acceptable, there is a further issue with this approach, namely that it also depends on an unknown variance term. And replacing it with an estimate induces further bias. So it may be that this method has not met with many followers because of those two penalising factors. Despite precluding the pseudo-marginal approach of Mark Beaumont (2003) by a few years, with the later estimating separately numerator and denominator in the Metropolis-Hastings acceptance ratio. And hence being applicable in a much wider collection of cases. Although I wonder if some generic approaches like path sampling or the exchange algorithm could be applied on a generic basis… [I just realised the title could be confusing in relation with the current football competition!]

appliBUGS (wet)

This morning I gave my talk on ABC; computation or inference? at the appliBUGS seminar. Here, in Paris, BUGS stands for Bayesian United Group of Statisticians! Presumably in connection with a strong football culture, since the talk after mine was Jean-Louis Foulley’s ranking of the Euro 2012 teams. Quite an interesting talk (even though I am not particularly interested in football and even though I dozed a little, steaming out the downpour I had received on my bike-ride there…) I am also sorry I missed the next talk by Jean-Louis on Galton’s quincunx. (Unfortunately, his slides are not [yet?] on-line.)

As a coincidence, after launching a BayesComp page on Google+ (as an aside, I am quite nonplussed by the purpose of Google-), Nicolas Chopin also just started a Bayes in Paris webpage, in connection with our informal seminar/reading group at CREST. With the appropriate picture this time, i.e. a street plaque remembering…Laplace! May I suggest the RER stop Laplace and his statue in the Paris observatory as additional illustrations for the other pages…

Red card on Lenin stadium

Last weekend, my son played football in what may be the last remaining Lenin stadium in France (actually no, there is another one in Ivry) and managed to get a red card (if not a red flag) for complaining to the referee. How appropriate!.(The above plaque reads: “This stadium made in 1938 by the workmen township of Malakoff was named V.I. Lenin in honour of the founder of the Soviet Union. This plaque was set on Aug. 22, 1970, for his 100th birthday.”)