Archive for the Running Category

U of T sunset [jatp]

Posted in pictures, Running, Travel, University life with tags , , , , , on December 14, 2017 by xi'an

red Capitol [jatp]

Posted in pictures, Running, Travel with tags , , , , , on December 12, 2017 by xi'an

sunrise over Colorado [jatp]

Posted in pictures, Running, Travel, University life with tags , , , , , , on December 11, 2017 by xi'an

resampling methods

Posted in Books, pictures, Running, Statistics, Travel, University life with tags , , , , , , , , , , on December 6, 2017 by xi'an

A paper that was arXived [and that I missed!] last summer is a work on resampling by Mathieu Gerber, Nicolas Chopin (CREST), and Nick Whiteley. Resampling is used to sample from a weighted empirical distribution and to correct for very small weights in a weighted sample that otherwise lead to degeneracy in sequential Monte Carlo (SMC). Since this step is based on random draws, it induces noise (while improving the estimation of the target), reducing this noise is preferable, hence the appeal of replacing plain multinomial sampling with more advanced schemes. The initial motivation is for sequential Monte Carlo where resampling is rife and seemingly compulsory, but this also applies to importance sampling when considering several schemes at once. I remember discussing alternative schemes with Nicolas, then completing his PhD, as well as Olivier Cappé, Randal Douc, and Eric Moulines at the time (circa 2004) we were working on the Hidden Markov book. And getting then a somewhat vague idea as to why systematic resampling failed to converge.

In this paper, Mathieu, Nicolas and Nick show that stratified sampling (where a uniform is generated on every interval of length 1/n) enjoys some form of consistent, while systematic sampling (where the “same” uniform is generated on every interval of length 1/n) does not necessarily enjoy this consistency. There actually exists cases where convergence does not occur. However, a residual version of systematic sampling (where systematic sampling is applied to the residuals of the decimal parts of the n-enlarged weights) is itself consistent.

The paper also studies the surprising feature uncovered by Kitagawa (1996) that stratified sampling applied to an ordered sample brings an error of O(1/n²) between the cdf rather than the usual O(1/n). It took me a while to even understand the distinction between the original and the ordered version (maybe because Nicolas used the empirical cdf during his SAD (Stochastic Algorithm Day!) talk, ecdf that is the same for ordered and initial samples).  And both systematic and deterministic sampling become consistent in this case. The result was shown in dimension one by Kitagawa (1996) but extends to larger dimensions via the magical trick of the Hilbert curve.

importance demarginalising

Posted in Books, Kids, pictures, Running, Statistics, Travel, University life with tags , , , , , on November 27, 2017 by xi'an

A question on X validated gave me minor thought fodder for my crisp pre-dawn run in Warwick the other week: if one wants to use importance sampling for a variable Y that has no closed form density, but can be expressed as the transform (marginal) of a vector of variables with closed form densities, then, for Monte Carlo approximations, the problem can be reformulated as the computation of an integral of a transform of the vector itself and the importance ratio is given by the ratio of the true density of the vector over the density of the simulated vector. No Jacobian involved.

art brut

Posted in pictures, Running, Travel with tags , , , , on November 11, 2017 by xi'an

New York City Marathon snapshot

Posted in Running with tags , , , , , on November 5, 2017 by xi'an