## it was the best of times, it was the worst of times

Posted in Books, pictures, Travel with tags , , , , , , , , , , , , , , , on January 7, 2021 by xi'an

## Bernoulli factory in the Riddler

Posted in Books, Kids, R, Statistics with tags , , , , , , , , , , on December 1, 2020 by xi'an

“Mathematician John von Neumann is credited with figuring out how to take a p biased coin and “simulate” a fair coin. Simply flip the coin twice. If it comes up heads both times or tails both times, then flip it twice again. Eventually, you’ll get two different flips — either a heads and then a tails, or a tails and then a heads, with each of these two cases equally likely. Once you get two different flips, you can call the second of those flips the outcome of your “simulation.” For any value of p between zero and one, this procedure will always return heads half the time and tails half the time. This is pretty remarkable! But there’s a downside to von Neumann’s approach — you don’t know how long the simulation will last.” The Riddler

The associated riddle (first one of the post-T era!) is to figure out what are the values of p for which an algorithm can be derived for simulating a fair coin in at most three flips. In one single flip, p=½ sounds like the unique solution. For two flips, p²,(1-p)^2,2p(1-p)=½ work, but so do p+(1-p)p,(1-p)+p(1-p)=½, and the number of cases grows for three flips at most. However, since we can have 2³=8 different sequences, there are 2⁸ ways to aggregate these events and thus at most 2⁸ resulting probabilities (including 0 and 1). Running a quick R code and checking for proximity to ½ of any of these sums leads to

```[1] 0.2062997 0.7937005 #p^3
[1] 0.2113249 0.7886753 #p^3+(1-p)^3
[1] 0.2281555 0.7718448 #p^3+p(1-p)^2
[1] 0.2372862 0.7627143 #p^3+(1-p)^3+p(1-p)^2
[1] 0.2653019 0.7346988 #p^3+2p(1-p)^2
[1] 0.2928933 0.7071078 #p^2
[1] 0.3154489 0.6845518 #p^3+2p^2(1-p)
[1] 0.352201  0.6477993 #p^3+p(1-p)^2+p^2(1-p)
[1] 0.4030316 0.5969686 #p^3+p(1-p)^2+3(1-p)p^2
[1] 0.5
```

which correspond to

1-p³=½, p³+(1-p)³=½,(1-p)³+(1-p)p²=½,p³+(1-p)³+p²(1-p),(1-p)³+2(1-p)p²=½,1-p²=½, p³+(1-p)³+p²(1-p)=½,(1-p)³+p(1-p)²+p²(1-p)=½,(1-p)³+p²(1-p)+3p(1-p)²=½,p³+p(1-p)²+3(p²(1-p)=½,p³+2p(1-p)²+3(1-p)p²=½,p=½,

(plus the symmetric ones), leading to 19 different values of p producing a “fair coin”. Missing any other combination?!

Another way to look at the problem is to find all roots of the $2^{2^n}$ equations

$a_0p^n+a_1p^{n-1}(1-p)+\cdots+a_{n-1}p(1-p)^{n-1}+a_n(1-p)^n=1/2$

where

$0\le a_i\le{n \choose i}$

(None of these solutions is rational, by the way, except p=½.) I also tried this route with a slightly longer R code, calling polyroot, and finding the same 19 roots for three flips, [at least] 271 for four, and [at least] 8641 for five (The Riddler says 8635!). With an imprecision in the exact number of roots due to rather poor numerical rounding by polyroot. (Since the coefficients of the above are not directly providing those of the polynomial, I went through an alternate representation as a polynomial in (1-p)/p, with a straightforward derivation of the coefficients.)

## a journal of the plague year [grey November reviews]

Posted in Books, Kids, Mountains, pictures, Travel with tags , , , , , , , , , , , , , , , , , , , , , , on November 21, 2020 by xi'an

Read Evil for Evil, K.J. Parker’s second tome in the Engineer trilogy, published in 2009! Surprisingly, I remembered enough of the first volume for the story to make sense and I enjoyed it, for the same reason I liked Sixteen ways to defend &tc., namely for its attention to logistics and medieval industry taking over the muscle-display of standard equivalents, plus the self-demeaning attitude of most characters, again a welcome change from the standards! The pace of the story sometimes get bogged down, though.

Slowly cooked pulled pork with a hellish amount of red peppers, meaning I ended up eating most of it by myself over a few days. Tried cauliflower risotto, and liked it. Took my mom to a nice restaurant in Caen, À Contre Sens, after an oyster breakfast with her on the quays of a nearby Channel harbour, with a surprise lunch based on local (Norman) products. Finding hardly anyone in the restaurant due to COVID regulations made the experience even more enjoyable. And such a difference from the previous Michelin we sampled this summer!

Wasted hours watching the US presidential vote counting slowly unraveling, computing & recomputing from the remaining ballots the required percentage of Biden’s votes towards catching up, and refreshing my NYT & Fivethirtyeight webpages way too often. And remain fazed by an electoral system stuck in a past when less than 50,000 men elected George Washington.

Cleaned up our vegetable patch after collecting the last tomatoes, pumpkins, and peppers. And made a few jars of green tomato jam, albeit not too sweet to be used as chutney!

Watched the TV series The Boys, after reading super-positive reviews in Le Monde and other journals. Which is a welcome satire on the endless sequence of super-heroes movies and series, by simply pushing on the truism that with super-powers does not come super-responsibility. Or even the merest hint of ethics. Plus some embarrassing closeness with the deeds and sayings of the real Agent Orange. Among the weaknesses, a definitive excess of blood and gore, ambiguous moral stands of the [far from] “good” guys who do not mind shooting sprees in the least, and some very slow episodes. Among the top items, the boat-meet-whale incident, “Frenchie” from Marseille almost managing a French accent when speaking some semblance of French, and Karl Urban’s maddening accent that’s a pleasure to listen even when I understand a sentence out of two, at best.

## will it ever get better?! [verbatim]

Posted in Kids, pictures, Travel with tags , , , , , , , , , , , , , , , on November 14, 2020 by xi'an

“…after his defeat in the 1800 election, Adams wrote bitterly that “we have no Americans in America,” and that “a group of foreign liars, encouraged by a few ambitious native gentlemen, have discomfited the education, the talents, the virtues, and the property of the country.” Adams was so disgusted that he refused to attend the inauguration of his successor, Thomas Jefferson.” Sean Willenz, 11 November

“This man is a pathological liar. He doesn’t know the difference between truth and lies. He lies practically every word that comes out of his mouth. And in a pattern that I think is straight out of a psychology textbook, his response is to accuse everybody else of lying.” Ted Cruz, 03 May 2016

“No sitting president — no presidential candidate, with the partial exception of Jackson in 1824 — has refused to accept the results of an election. I’m not surprised that Trump is threatening to do so, but refusing to accept the results of an election may be a bridge too far.” James T. Campbell, 11 November

“There is no enchanted village in Pennsylvania full of 50,000 Trump voters that we haven’t heard from already. It doesn’t exist.” John Fetterman, Pennsylvania lieutenant governor, 13 November

## America in line [& the world in the balance]

Posted in Books, pictures with tags , , , , , , , , on November 3, 2020 by xi'an