## an elegant result on exponential spacings

Posted in Statistics with tags , , , , , , , , , , , , , on April 19, 2017 by xi'an

A question on X validated I spotted in the train back from Lyon got me desperately seeking a reference in Devroye’s Generation Bible despite the abyssal wireless and a group of screeching urchins a few seats away from me… The question is about why

$\sum_{i=1}^{n}(Y_i - Y_{(1)}) \sim \text{Gamma}(n-1, 1)$

when the Y’s are standard exponentials. Since this reminded me immediately of exponential spacings, thanks to our Devroye fan-club reading group in Warwick,  I tried to download Devroye’s Chapter V and managed after a few aborts (and a significant increase in decibels from the family corner). The result by Sukhatme (1937) is in plain sight as Theorem 2.3 and is quite elegant as it relies on the fact that

$\sum_{i=1}^n y_i=\sum_{j=1}^n (n-j+1)(y_{(j)}-y_{(j-1)})=\sum_{j=2}^n (y_{(j)}-y_{(1)})$

hence sums up as a mere linear change of variables! (Pandurang Vasudeo Sukhatme (1911–1997) was an Indian statistician who worked on human nutrition and got the Guy Medal of the RSS in 1963.)

## simulation by hand

Posted in Books, Kids, pictures, Statistics, Travel with tags , , , , , , , on November 28, 2016 by xi'an

A rather weird question on X validated this week was about devising a manual way to simulate (a few) normal variates. By manual I presume the author of the question means without resorting to a computer or any other business machine. Now, I do not know of any real phenomenon that is exactly and provably Normal. As analysed in a great philosophy of science paper by Aidan Lyon, the standard explanations for a real phenomenon to be Normal are almost invariably false, even those invoking the Central Limit Theorem. Hence I cannot think of a mechanical device that would directly return Normal generations from a Normal distribution with known parameters. However, since it is possible to simulate by hand Uniform U(0,1) variates [up to a given precision] using a chronometre or a wheel, calls to versions of the Box-Müller algorithm that do not rely on logarithmic or trigonometric functions are feasible, for instance by generating two Exponential variates, x and y, until 2y>(1-x)², x being the output. And generating Exponential variates is easy provided a radioactive material with known half-life is available, along with a Geiger counter. Or, if not, by calling von Neumann’s exponential generator. As detailed in Devroye’s simulation book.

After proposing this solution, I received a comment from the author of the question towards a simpler solution based, e.g., on the Central Limit Theorem. Presumably for simple iid random variables such as coin tosses or dice experiments. While I used the CLT for simulating Normal variables in my very early days [just after programming on punched cards!], I do not think this is a very good or efficient method, as the tails grow very slowly to normality. By comparison, using the same amount of coin tosses to create a sufficient number of binary digits of a Uniform variate produces a computer-precision exact Uniform variate, which can be exploited in Box-Müller-like algorithms to return exact Normal variates… Even by hand if necessary. [For some reason, this question attracted a lot of traffic and an encyclopaedic answer on X validated, despite being borderline to the point of being proposed for closure.]

## Versions of Benford’s Law

Posted in Books, Statistics with tags , , , , on May 20, 2010 by xi'an

A new arXived note by Berger and Hill discusses how [my favourite probability introduction] Feller’s Introduction to Probability Theory (volume 2) gets Benford’s Law “wrong”. While my interest in Benford’s Law is rather superficial, I find the paper of interest as it shows a confusion between different folk theorems! My interpretation of Benford’s Law is that the first significant digit of a random variable (in a basis 10 representation) is distributed as

$f(i) \propto \log_{10}(1+\frac{1}{i})$

and not that $\log(X) \,(\text{mod}\,1)$ is uniform, which is the presentation given in the arXived note…. The former is also the interpretation of William Feller (page 63, Introduction to Probability Theory), contrary to what the arXived note seems to imply on page 2, but Feller indeed mentioned as an informal/heuristic argument in favour of Benford’s Law that when the spread of the rv X is large,  $\log(X)$ is approximately uniformly distributed. (I would no call this a “fundamental flaw“.) The arXived note is then right in pointing out the lack of foundation for Feller’s heuristic, if muddling the issue by defining several non-equivalent versions of Benford’s Law. It is also funny that this arXived note picks at the scale-invariant characterisation of Benford’s Law when Terry Tao’s entry represents it as a special case of Haar measure!

## The Night Angel Trilogy

Posted in Books with tags , , , , , , on January 31, 2010 by xi'an

“There was no thesis, counterpointed with antithesis, harmonized into synthesis. It wasn’t that kind of music. The music of logic was too patrician for the streets, too subtle, the nuances all wrong.” Brent Weeks, Shadow’s Edge

I have finished the Night Angel Trilogy quite a while ago but felt so far little inclination to comment on it as I was quite disappointed by the series. The third volume, Beyond the Shadows, is quite unappealing and at some point it turns into such a bleak story of rape and slaughter that I was close to give up on the book. (This is when one of the main and so far “good” characters turns into a mad homicidal and sadistic Godking. Maybe a necessary part of the plot but unpleasant nonetheless, especially because Weeks makes it sound so reasonable…)

“You realize it might make a quantitative rather than qualitative difference?” “Huh?” Brent Weeks, Beyond the Shadows

As posted earlier, I did like the first volume The Way of Shadows as it truly made for a compelling and unusual read. But the characters do not evolve nor take much depth in the subsequent volumes, Shadow’s Edge and Beyond the Shadows (except for the female assassin Vi who alas often acts as a lovelorn teenager…) The interesting parallel structure of the thief society all but disappears once the new king comes to power, the influential (Aes Sedai or Bene Gesserit like) sisterhood is almost invisible and thus hardly influential. The fight for survival of the (future) king Logan in the dungeon filled with psychopaths is a better-written part, but the psychopaths turn up being a wee too nice to be credible! The central character Elene who was creating the (rather predictable) tension about the antagonistic inclinations of the other central character Kylar, torn between a prospect for family life and a magical assassin’s career, mostly drops from the last volume, Beyond the Shadows, only to reappear at the end to save the day. While the disappearance of major characters is a good novelist’s trick to keep the pace going and the reader hooked, I find the slaughter of many main characters overdone.  At last, the crudity and cruelty of the story, which were innovative in the first volume, end up wearing up in the following ones. Unless you specialise into gory fantasy (!), I would thus not recommend the Night Angel Trilogy. (There is an interview of Brent Weeks by Patrick Rothfuss that does not bring much about the books… Patrick Rothfuss should better be working on the sequel of The Name of the Wind I am desperate for! I also just found Linus Torvald, yes THE Linus Torvald!, recommended the trilogy two years ago…)

## The Book of the New Sun

Posted in Books with tags , , , on August 4, 2009 by xi'an

During the flight to Washington D.C. on Saturday, I finished Shadow & Claw, by Gene Wolfe, that I had started on my previous trip to the US and which is the first part of The Book of the New Sun (or alternatively is made of the two first volumes, The Shadow of the Torturer and The Claw of the Conciliator, of this quadrilogy). I started reading these books upon the suggestion of a fellow mathematician in Paris Dauphine, who considers them as an higher (the highest!) kind of fantasy. After reading thru the first half, I cannot but agree with this assessment: The literary style of Gene Wolfe is much more involved and deeper than the usual fantasy syntax and his plot construction is much more intricate, to the point of being almost obscure. There are links with the standards of this literature, including the author being a former military (similar to Robert Jordan and many others), the young apprentice being left to his own device who starts a discovery journey and the chance encounters during this journey that bring him luck or woe, as well as side information about the dangers that threaten him. But I find at least as many links with a much older fantasy literature, namely the Arthurian novels of Chrestien de Troyes and others, i.e.~the medieval version of the genre, with the same kind of perpetual wonder at the marvels and dangers of the world, with characters always unexpectedly bumping into quests and challenges, in a rather linear and unavoidable fashion that relates to the 2D paintings of the time, as well as an archaic and somehow naïve way of behaving towards others and especially towards women. (This antiquated style, although the book was written in the early 80’s, may confuse modern readers who will find the roles played by female characters rather limited, since they are either nuns or prostitutes!, but besides the hero, whose actions and point of view are the only ones provided to the reader, all other essential characters are women.)

The convolved and slowly unraveling plot of Shadow & Claw also reflects this unusual approach to the fantasy literature: the dangers that usually beset the young hero (or more rarely the young heroin) are not so obvious there. Nor is the quest that almost inevitably sets the backbone of a modern fantasy novel. In the case of The Shadow of the Torturer, besides chance encounters of the hero (Severian) with dangerous situations, there is only a vague global threat represented by a rebel leader Severian meets and idealises from the first pages of the novel, but the motivations for the rebellion are never clearly defined, even when Severian meets again with this leader. Even the structure of the society is explained indirectly and progressively through Severian’s eyes and opinions. Similarly, almost from the beginning, the hero fails in his duties (as a Torturer) for the love of a highborn prisoner and he is driven by his guild upon a penance trip to a faraway place, but he does not seem particularly eager or in a hurry to reach it over the first part of the novel. At last, while there are magical powers and magical beings, like witches, giants, or undines, present in the world of Shadow & Claw, Wolfe’s descriptions remain, once again, so vague as to leave a good part to imagination. In connection with this feature, dreams and riddles also play a good part in the development of the plot. There is for instance a complete theatre play, called Eschatology and Genesis (!), that serves as a political satire of the current autocratic (or autharcic?!) regime.

The closest (and only) book I can relate to this one is the equally unique and daunting Gormenghast trilogy by Mervyn Peake, with which it shares a strong and sombre Gothic atmosphere, an elusive description of the outer world(s), with completely alien behaviours from the characters (a lacking feature of most of the current fantasy literature is that characters behave much too closely to our 21st Century ways, even when handling a sword or launching a spell!) and incomprehensible codes in the current society) , and an almost deterministic destiny weighting upon the characters. Like this (other) masterpiece, The Book of the New Sun stands on its own as part of the world literature, rather than as a good representant of the fantasy genre. I am definitely looking forward reading the second half Shadow & Citadel while here in the U.S. and finishing the cycle!