optimal Bernoulli factory

Posted in Statistics with tags , , , , , , , , , , on January 17, 2017 by xi'an

One of the last arXivals of the year was this paper by Luis Mendo on an optimal algorithm for Bernoulli factory (or Lovàsz‘s or yet Basu‘s) problems, i.e., for producing an unbiased estimate of f(p), 0<p<1, from an unrestricted number of Bernoulli trials with probability p of heads. (See, e.g., Mark Huber’s recent book for background.) This paper drove me to read an older 1999 unpublished document by Wästlund, unpublished because of the overlap with Keane and O’Brien (1994). One interesting gem in this document is that Wästlund produces a Bernoulli factory for the function f(p)=√p, which is not of considerable interest per se, but which was proposed to me as a puzzle by Professor Sinha during my visit to the Department of Statistics at the University of Calcutta. Based on his 1979 paper with P.K. Banerjee. The algorithm is based on a stopping rule N: throw a fair coin until the number of heads n+1 is greater than the number of tails n. The event N=2n+1 occurs with probability

${2n \choose n} \big/ 2^{2n+1}$

[Using a biased coin with probability p to simulate a fair coin is straightforward.] Then flip the original coin n+1 times and produce a result of 1 if at least one toss gives heads. This happens with probability √p.

Mendo generalises Wästlund‘s algorithm to functions expressed as a power series in (1-p)

$f(p)=1-\sum_{i=1}^\infty c_i(1-p)^i$

with the sum of the weights being equal to one. This means proceeding through Bernoulli B(p) generations until one realisation is one or a probability

$c_i\big/1-\sum_{j=1}^{i-1}c_j$

event occurs [which can be derived from a Bernoulli B(p) sequence]. Furthermore, this version achieves asymptotic optimality in the number of tosses, thanks to a form of Cramer-Rao lower bound. (Which makes yet another connection with Kolkata!)

Jubilee at the University of Calcutta

Posted in Books, pictures, Statistics, Travel, University life with tags , , , , , , , , , on January 2, 2017 by xi'an

The main reason for my trip to India was taking part in the celebrations of the 75th anniversary of the Department of Statistics at the University of Calcutta and of the 100th anniversary of the birth of P.K. Bose (whom I did not know before visiting Kolkata). The Department of Statistics was created in 1941 by Mahalanobis, the very first statistics department in Asia. (Mahalanobis was also instrumental in creating the ISI in 1932. And Sankhyā in 1933.)  Fisher visited Calcutta very often and was very supportive of Mahalanobis’ efforts: in the corridor, the above picture of Fisher is displayed, with him surrounded by faculties and graduates from the Department when he came in 1941.

Although I missed the first two days of the conference (!), I enjoyed very much the exchanges I had with graduate students there, about my talk on folded MCMC and other MCMC and Bayesian issues. (With The Bayesian Choice being an easy conversational bridge-way between us as it is their Bayesian textbook.) The setting reminded me of the ISBA conference in Varanasi four years ago, with the graduate students being strongly involved and providing heavy support in the organisation, as well as eager to discuss academic and non-academic issue. (Plus offering us one evening an amazing cultural show of songs and dances.) Continue reading