**C**onsidering a binary random walk, starting at zero, what is the probability of being almost sure of winning at some point only to lose at the end? This is the question set by the post-election Riddler, with almost sure meaning above 99% and the time horizon set to n=101 steps (it could have been 50 or 538!). As I could not see a simple way to compute the collection of states with a probability of being positive at the end of at least 0.99, even after checking William Feller’s Random Walks fabulous chapter, I wrote an R code to find them, and then ran a Monte Carlo evaluation of the probability to reach this collection and still end up with a negative value. Which came as 0.00212 over repeated simulations. Obviously smaller than 0.01, but no considerably so. As seen on the above picture, the set to be visited is actually not inconsiderable. The bounding curves are the diagonal and the 2.33 √(n-t) bound derived from the limiting Brownian approximation to the random walk, which fits rather well. (I wonder if there is a closed form expression for the probability of the Brownian hitting the boundary 2.33 √(n-t). Simulations with 1001 steps give an estimated probability of 0.505, leading to a final probability of 0.00505 of getting over the boundary and loosing in the end, close to the 1/198 produced by The Riddler.)

## Archive for US elections 2020

## the riddle(r) of the certain winner losing in the end

Posted in Books, Kids, R, Statistics with tags gambler's ruin, Monte Carlo experiment, R, random walk, US elections 2020, William Feller on November 25, 2020 by xi'an## a journal of the plague year [grey November reviews]

Posted in Books, Kids, Mountains, pictures, Travel with tags Agent Orange, amazon associates, Annapurna, book reviews, Caen, chutney, Daniel Defoe, film review, films, green tomatoes, homecooking, homegrown vegetables, Joe Biden, Journal of the Plague Year, marmalade, MIchelin starred restaurant, Normandy, NYT, oysters, scallops, The Guardian, Université Paris Dauphine, US elections 2020 on November 21, 2020 by xi'an**R**ead 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 @ScientistTrump, Agent Orange, America, coronavirus epidemics, COVID-19, decency, Donald Trump, incompetence, John Adams, pandemic, Republicans, The New York Times, Thomas Jefferson, US elections 2020, US politics, US presidents 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

## on arithmetic derivations of square roots

Posted in Books, Kids, pictures, R, Statistics with tags Babylonian mathematics, code golf, insomnia, long integer division, Newton-Raphson algorithm, R, root finding, Stack Exchange, US elections 2020, wikipedia on November 13, 2020 by xi'an**An** intriguing question made a short-lived appearance on the CodeGolf section of Stack Exchange, before being removed, namely the (most concise possible) coding of an arithmetic derivation of the square root of an integer, S, with a 30 digit precision and using only arithmetic operators. I was not aware of the myriad of solutions available, as demonstrated on the dedicated WIkipedia page. And ended playing with three of them during a sleepless pre-election night!

The first solution for finding √S is based on a continued fraction representation of the root,

with a²≤S and r=S-a². It is straightforward to code-golf:

while((r<-S-T*T)^2>1e-9)T=(F<-2*T+r/(2*T+F))-T;F

but I found it impossible to reach the 30 digit precision (even when decreasing the error bound from 10⁻⁹). Given the strict rules of the game, this would have been considered to be a failure.

The second solution is Goldschmidt’s algorithm

b=S T=1/sum((1:S)^2<S) while((1-S*prod(T)^2)^2>1e-9){ b=b*T[1]^2 T=c((3-b)/2,T)} S*prod(T)

which is longer for code-golfing but produces both √S and 1/√S (and is faster than the Babylonian method and Newton-Raphson). Again no luck with high precision and almost surely unacceptable for the game.

The third solution is the most interesting [imho] as it mimicks long division, working two digits at a time (and connection with Napier’s bones)

`~`=length D=~S S=c(S,0*(1:30)) p=d=0 a=1:9 while(~S){ F=c(F,x<-sum(a*(20*p+a)<=(g<-100*d+10*S[1]+S[2]))) d=g-x*(20*p+x) p=x+10*p S=S[-1:-2]} sum(10^{1+D/2-1:~F}*F)

plus providing an arbitrary number of digits with no error. This code requires S to be entered as a sequence of digits (with a possible extra top digit 0 to make the integer D even). Returning one digit at a time, it would further have satisfied the constraints of the question (if in a poorly condensed manner).