Leaving Facebook

On August 9, I permanently deleted my Facebook account. Well, not quite. Facebook accounts, after request of permanent deletion, stay for fourteen entire days before they actually allegedly remove the stuff. And because this is Facebook, they probably retain a whole bunch of stuff that they probably do something with.

Anyway, around now, the account should be disappearing.

I have often mentioned that one reason I don’t like xkcd as much as most people believe I would is because they keep executing the same ideas I have before I do. This time, however, I did it first: I defriended my Facebook friends in generalized reverse chronological order of friending before this was posted. Ha. Grr.

Why did I leave Facebook? As you guys hopefully know to some extent, Facebook is extremely sketchy. The set of things I could look up on Facebook and arrive at my page in the suggestions with really irked me. In addition, recent things Facebook added were utterly ridiculous. There were many changes that are almost objectively inferior, and the addition of ads to the main stream of stati are just egregious. I’ve decided I’ve had enough and I am glad I no longer use Facebook: no more W(v)u account (2010.10.07-2013.08.09).

Fun fact: the 6th character of my Facebook password was o.

Advertisements

Two Years

This blog has now been here for two years.

Wow. Already.

The most popular page on this blog so far is The BART Map, to Scale, with 11106 views. Next is the home page, with 7762 views, followed by 2013 USAMO Qualifier Statistics, with 2213 views. The least popular (non-deleted) page so far is Volcanos, Cyclones, Earthquakes, with 4 views, although despite its small view count it somehow received 4 likes, that is, one for each view. (Of course now that I mention this page, this 100% like record will probably not hold long.)

The United States is the country that has visited my blog the most, a total of 31818 times. Taiwan is next, with 612, followed by Canada with 513, United Kingdom with 327, Australia with 176, and India with 154. Germany, Brazil, France, South Korea, and Indonesia have also had over a hundred view totals to this blog.

The most popular search query leading to this blog so far is “bart map,” followed by “usamo qualifiers 2013,” “2013 usamo qualifiers,” “how to pronounce chinese names in english,” “zyxyvy,” “sonnhard graubner,” “usamo qualifiers 2012,” “world map outline labeled,” “zeus sex,” “b a r t map,” “titularly,” and “world map outline.”

The day with the most views so far was this blog’s 654th day, with 1331 views.

A couple of weeks ago, I got a new banner. Can anyone figure out what it symbolizes?

And now, my favorite posts so far. I think I liked these two the most.

The Huasu Keyboard Layout

This is a layout designed to be optimal for typing Pinyin-romanized Chinese. It offers a 0% chance of intra-syllable consecutive finger-repetition. Index fingers go on A and H.

hua

One thing that really surprised me while I was doing frequency analysis research for designing this keyboard is how rare “c” was in Pinyin Chinese. Even after including instances of it before “h” in “ch,” it is somehow still one of the rarest letters in Pinyin Chinese.

Literacy Rates

(mostly from CIA World Factbook)

From dark blue to dark red, most exclusive true category of {>99%, >98%, >95%, >90%, >world average (84.1%), >75%, >50%, >0%}. literacy

North Korea is higher than South Korea? What?

A Random Generator Expected Time Sequence

Suppose we have a binary random generator, that is, one that picks between two possibilities with equal probability. Now let’s say we want to create any finite-option random generator, specifically that picks between any n possibilities for any natural number n, incorporating just usages of this binary random generator. If n is a power of 2, one can just distribute the results over the ending possibilities of running the binary random generator \log_2 n times; as an example, if we want to choose between 8 equally likely possibilities, our first run can choose between one set of 4 and the other, our second run can choose between one set of 2 in the 4 and the other, and our third can determine which one to choose out of the 2 we have narrowed down to, a total of \boxed{3} runs of the binary random generator.

But say we want to choose between a number of options that is not a power of 2, say 3. What can we do now?

We can still choose between them with equal probability, using a binary random generator. We build the same type of decision tree as we do for 4 possibilities, but one of the end results is labeled “re-run,” that is, an instruction to go through the process again, hoping that the next time we end up on one of the three other end results (which starting here I will term “leaves”), corresponding to the three choices among which the random generator we have hired will choose. Note that this process could take an infinite amount of time, but with infinitesimal probability; the expected amount of callings of the binary generator is still finite, and can be computed. Call the expected value of the number of callings of the binary generator E. We can then write the equation E=2+\frac{1}{4}E. The process will always take at least 2 usages, but has a \frac{1}{4} chance of needing to be run again, in which case it is expected to take an additional whatever-the-expectation-was-in-the-first-place, since if one ends up in the re-run leaf, it is as if the system said “try again,” and one is back where one started. Solving this simple equation, we get that E=\boxed{2 \frac{2}{3}}, so the expected number of usages of the binary generator needed is actually just under 3, not as quick as in the case with four choices, but definitely not only doable but in fact swifter on average than the next power of 2 after 4, the case with 8 choices.

In fact, we can take this approach with all integers that are not powers of 2. For example, in the case where we are choosing among 7 choices, we can assign one of 8 ending leaves as a re-run leaf and see that we are expected to run the binary generator E=3+\frac{1}{8}E \implies E=\boxed{3 \frac{3}{7}} times. If we are choosing among 6 choices, doing the same but with marking two leaves as re-run leaves gives us E=3+\frac{1}{4}E \implies E=4 for an expected value of number of times the generator is run.

In the case of 6 choices, though, we can do better. Since each of the two re-run leaves are chosen equally likely, and each of the results of the first binary decision are equally likely, we could re-route the locations these leaves go to as the two possibilities after the first decision rather than before the first decision. But what is the expected value of the number of times the generator will need to be used now? If we place the two re-run leaves as close together as possible, it is E=\frac{1}{2}(3)+\frac{1}{2}(1+D), where D is the expected value of the number of times the generator must be used from after the first decision is made (hence, the addition of 1 in the term containing D) and the result is the one where the re-run leaves are possibilities. Building an equation for D, D=2+\frac{1}{4}(2)+\frac{1}{4}D \implies D=\frac{10}{3}. Using this value of D and solving for E above, we get E=\frac{1}{2}(3)+\frac{1}{2}(1+\frac{10}{3})=\frac{3}{2}+\frac{13}{6}=\frac{11}{3}=3 \frac{2}{3}. Note that if we alternatively place the two re-run leaves as far away from each other, then we get the case of making one decision and then redirecting to the case of 3 choices on either result of the first binary generator run, thus having expected value of total binary generator runs be 1+2 \frac{2}{3} (1 for the initial decision, then the expected number of runs for the case with 3 choices), again evaluating to \boxed{3 \frac{2}{3}}.

What if we have 5 choices? There now seems to be a forest of possibilities of where re-run leaves redirect. We could even incorporate the method to choose between 3, each result of which directs to three choose-between-2 cases, where one of the final leaves redirects to the root. We can see that 3 is a clear lower bound for the number of usages of the binary generator needed, but is there a way to easily tell what system of redirections is most efficient?