Vanity of Vanities, all is Vanity

In Radon’s urn there are \(n\) balls — \(r\) of them are red, and the rest are blue. In each iteration of the game is as follows:

1. The player picks \(t\) balls out of the urn (\(t\) is a small constant, say \(4\)) [the picking is done with repetition], and let \(s\) be the number of red balls in the sample.
2. The player returns the sample back to the urn.
3. The player picks a random ball from the urn and replaces it with a red ball if \(s \geq 2\) and by a blue ball otherwise.

As such, the number of balls in the urn remains the same throughout the game, and we are interested in the event that all balls become blue (or all red [but that would be bad]).

Let assume that \(r\), the initial number of red balls, is quite small – say \(r \leq n/(4t^2)\).

Several questions:

1. In expectation, how many iterations of the game one has to play till all the balls in the urn are blue?
2. Same as above, but we want the probability of failure to be smaller than some parameter \(\psi\)?
3. What happens if the initial number of red balls is larger, say \(r \geq 8n/t^2\)?

This problem is inspired by a similar process analyzed in the following paper (by Clarkson, Eppstein, Miller, Sturtivant, and Teng) – where Radon’s point makes a surprising appearance. (As pointed out by David Eppstein, a free version of the paper, unfortunately without the figures, is available here.)

Recently UIUC had started requiring using vpn to ssh into computers in UIUC. After some time spent on this, here is the easiest way to work with this under linux (from my own experience – YMMV). It does not seem to require root permissions (except for installing the relevant packages).

1. No need to use the cisco stuff. openconnect works well. Another package that is quite useful is ocyproxy. Assuming you have debian/ubuntu system, first do the following:

   sudo apt-get install openconnect ocproxy

2. Next, you create a proxy socks port on your local computer which goes through the vpn (run this from a terminal/shell script/etc):

   echo "your_netid_password" \
          | openconnect --script-tun --script "ocproxy -D 9052" \
                             --authgroup=SplitTunnel -b \
                             --user=your_net_id --passwd-on-stdin \
                             vpn.cites.illinois.edu
   

3. You need to let your ssh setup know to use this local port for ssh into your remote UIUC machine. To this end, add to the file ~/.ssh/config the following lines:

   Host yourhostname.cs.illinois.edu
     ProxyCommand nc -X 5 -x 127.0.0.1:9052 %h %p
   

4. And thats it – you should be in business. Doing

   ssh yourhostname.cs.illinois.edu
   

   should happily connect you to your uiuc host.

I feel like a spinning top for a dreidel
The spinning don’t stop when you leave the cradle
You just slow down
Round and around this world you go
Spinning through lives of the people you know
We all slow down
— Dreidel, Don McLean

I posted some new class notes on planar graphs. Naturally they contain typos etc, but hopefully they would be useful for somebody out there (or not). Anyway, they are available at the bottom of this page. The notes currently cover (i) planarity checking, (ii) grid embedding, (iii) circle packing theorem, and (iv) planar separator.

Once you have eliminated all candidates, whoever survive would be king. That is my conclusion from reading a book on the war of the roses. A positive conclusion is how rarely democracy elects incompetent people to be head of states, while the war of the roses was caused to a large extent by having several incompetent kings. Henry VI was an infant when he became a king and was never competent. Other turns to the worst were caused by kings dying in inconvenient times. Which is another important feature of democracy – the ability to withstand a change of head of state without much turbulence

As this long and complicated sequence of battles and intrigues in a civil war unfolded, one can only wonder what the regular people thought – as all of this struggle involved only the ruling class. They lived and died just like their rulers.

The book is “The Wars of the Roses: The Fall of the Plantagenets and the Rise of the Tudors” by Dan Jones. I recommend it if you like reading history books.
http://www.goodreads.com/book/show/20821029-the-wars-of-the-roses

There is a cute video on YouTube on conflict free coloring. See here… 

One day he arrived at Senez, which is an ancient episcopal city. He was mounted on an ass. His purse, which was very dry at that moment, did not permit him any other equipage. The mayor of the town came to receive him at the gate of the town, and watched him dismount from his ass, with scandalized eyes. Some of the citizens were laughing around him. “Monsieur the Mayor,” said the Bishop, “and Messieurs Citizens, I perceive that I shock you. You think it very arrogant in a poor priest to ride an animal which was used by Jesus Christ. I have done so from necessity, I assure you, and not from vanity.”

https://goo.gl/photos/kmEUoR8Vx6MrHy4u6

​Discrete Geometry and Convexity

BÁRÁNY 70
Budapest, June 19-23, 2017

http://www.renyi.hu/conferences/barany70/

More info here. 

The abstract deadline for SoCG 2017 is coming up: abstracts (at most 300 words). The submission itself is due on December 5.

May the seasoning be with you!

And I mean ‘nigger’ with the hard r.”

“Why, thank you, white man.”

“And do you know why there aren’t any more niggers?”

“No, sir. I don’t.”

“Because white people are the new niggers. We’re just too full of ourselves to realize it.”

“The ‘new niggers,’ you say?”

“That’s right, both me and you—niggers to the last. Disenfranchised equals ready to fight back against the motherfucking system.”

“Except that you’ll get half the jail time.”

Daddy told his jokes the same way he’d ordered pizza, written poetry, and written his doctoral thesis—in APA format. Following the standards of the American Psychological Association, he’d toddle onstage and open up with the oral equivalent of a Title Page. Stating his name and the title of the joke. Yes, his jokes had titles. “This joke is called ‘Racial and Religious Differences in Drinking Establishment Patronage.’” Then he’d deliver the Abstract of the joke. So instead of simply saying, “A rabbi, a priest, and a black guy walk into a bar,” he’d say, “The subjects of this joke are three males, two of whom are clergymen, one of the Jewish faith, the other an ordained Catholic minister. The religion of the African-American respondent is undetermined, as is his educational level. The setting for the joke is a licensed establishment where alcohol is served. No, wait. It’s a plane. I’m sorry, my mistake. They are going parachuting.” Finally, he’d clear his throat, stand too close to the mike, and deliver what he liked to call “The Main Body” of the joke. Comedy is war. When a comedian’s routine works, they’ve killed; if the bits fall flat, they refer to it as dying. My father didn’t die onstage. He martyred himself for that other unrecognized completely unfunny black man who, just as there must be extraterrestrial life, is out there somewhere. I’ve seen self-immolations that were funnier than my father’s routine, but there were no gongs to ring or oversized canes with which to pull him offstage. He’d just ignore the booing and segue from the punch line to the Conclusion. The Results of the joke were a smattering of coughing. A chorus of vocalized disapproval and a plethora of yawning found to be significant. He’d end with the joke’s Reference Section:

“Jolson, Al (1918). ‘Sambo and Mammy Cleared for Takeoff on Runaway 5,’ Ziegfeld Follies.

“Williams, Bert (1917). ‘If Niggers Could Fly,’ The Circuitous Chitterling Tour.

“The Unknown Minstrel (circa 1899). ‘Dem Vaudeville Peckerwoods Sho’ Am Stealing My Shit,’ The Semi-Freemason Hall, Cleveland, Ohio.

“And don’t forget to tip your waitress.”

“I tried to read this book, Huckleberry Finn, to my grandchildren, but I couldn’t get past page six because the book is fraught with the ‘n-word.’ And although they are the deepest-thinking, combat-ready eight- and ten-year-olds I know, I knew my babies weren’t ready to comprehend Huckleberry Finn on its own merits. That’s why I took the liberty to rewrite Mark Twain’s masterpiece. Where the repugnant ‘n-word’ occurs, I replaced it with ‘warrior’ and the word ‘slave’ with ‘dark-skinned volunteer.’”

UIUC CS department is hiring this year in crypto. This is for a security-focused slot with interest in crypto people (both theoretical and applied). See here. Apply now while supply lasts!

Then the hard, dry Spaniards came exploring through, greedy and realistic, and their greed was for gold or God. They collected souls as they collected jewels. They gathered mountains and valleys, rivers and whole horizons, the way a man might now gain title to building lots. These tough, dried-up men moved restlessly up the coast and down. Some of them stayed on grants as large as principalities, given to them by Spanish kings who had not the faintest idea of the gift.

Konstantinos and Chao have a new version of their subset sum paper on the arxiv.  They speed up  the classical subset sum algorithm by a factor of sqrt(n)  using clever divide and conquer strategy.  This version is reasonably well written and is quite elegant. A nice paper!

“I do not understand why the British government needs until October to decide whether to send the divorce letter to Brussels,” Jean-Claude Juncker, the president of the European Commission, told German television.

http://nyti.ms/293Hp1m

Whatever the cost may be, we shall leave on the beaches, we shall leave on the landing grounds, we shall leave in the fields and in the streets, we shall leave in the hills; we shall never stay, and even if, which I do not for a moment believe, this Island or a large part of it were bored and without internet connection, then our Empire beyond the seas, armed and guarded by the British Fleet, would carry on the leaving, until, in God’s good time, the New World, with all its power and might, steps forth to the rescue and the liberation of the old.

Naturally everyone answered in the affirmative, shouting out in their respective tongues, but, unfortunately, says Poitiers, the guards outside the church thought that this loud clamour was some sort of last-minute English treachery, and responded by setting fire to the nearby houses.

Describing his unhappiness over the shogunate’s signing treaties with barbarians, a development for which he had no excuse to offer the gods or his ancestors, he mentioned his reluctance to send Kazunomiya, the daughter of an emperor, to a part of Japan where foreigners roamed.

Men reading tweets insulting women to their faces. m.youtube.com/watch?v=9tU-D-…

Exciting news on the Erdos-Szekeres convex polygon problem. arxiv.org/abs/1604.08657

Sanders to declare victory and withdraw from the Democratic party.

Not creepy at all… twitter.com/ABC/status/722…

“Your lie in April” en.wikipedia.org/wiki/Your_Lie_…

Michigan governor to fly over Flint and inspect the devastation through the window. twitter.com/nytimes/status…