Jingyu Cui's Blog

February 19, 2012

How many coin flips needed?

My friend Paul asked me an interesting question:

How many fair coin flips do you need on average for the first “HTT” (head-tail-head) sequence to appear? How about “HTH”? Which sequence takes more flips?

Intuitively, one might think that they all take the same amount of flips. However, due to the internal structure of the sequence, “HTH” needs 10 flips on average, while “HTT” only needs 8.

The two cases both take the same amount of flips to get to “HT”. However, if your target is “HTT” and the next one is “H”, although you fail, since you already have the “H”, you’ve got a head start for the next “HTT”, all you need is the “TT”. On the other hand, if your target is “HTH” and the next one is “T”, you fail and have to start all over again.

The general question for an arbitrary sequence can be solved using dynamic programming:

Given a sequence s with length L, let f(s) denote the average number of flips needed for the first s to appear, then the following holds:

$f(s) = f(s[:-1]) + 0.5 \times 1 + 0.5 \times \left[1 + f(s) - f(t)\right],$

where t = s[:n], and n is the maximum possible i such that s[:i] = s’[-i:], with s’ generated by flipping the last element of s. Intuitively, f(t) is the amount of effort saved by not having to start all over again.

This gives $f(s) = 2 + 2f(s[:-1]) - f(t).$

Some example: f(’111′) = 14, f(’110110′) = 72, f(’100000′) = 64.

One could also come up with tight bounds for f:

$f(s) \in [2^L, 2^{L+1}-2],$ where L is the length of s.

December 6, 2011

Switch or not?

The Trick Question

You are given two envelopes, one containing $x$ dollars and the other containing $2x$ . You randomly choose one and find $y$ dollars inside. Would it be better off if you switch to the other envelope?

Looks easy, right? Since the envelope is chosen randomly, knowing $y$ , the other envelope could contain $2y$ or $\frac{y}{2}$ with equal probability. The expected amount in the other envelope is $0.5 \times 2y + 0.5 \times \frac{y}{2} = 1.25y > y$ . So you should switch.

Wait a minute… If you should choose a random envelope and switch, how is this different from just randomly choose one in the first place (no switch)?

Think about it for a minute. The solution is below.

Solution

Since the envelope is chosen randomly, knowing $y=y_1=x$ or $y=y_2=2x$ , the other envelope could contain $2y_1$ or $\frac{y_2}{2}$ with equal probability. The expected amount in the other envelope is $0.5 \times 2y_1 + 0.5 \times \frac{y_2}{2} = 1.5x$ . The expected return by random choice is also $0.5 \times x + 0.5 \times 2x = 1.5x$ . So it does not make a difference to switch.

The original argument confuses $y_1$ and $y_2$ using $y$ .

A Twist

You randomly choose one of two envelopes and found $y$ dollars inside, the other one contains $2y$ or $\frac{y}{2}$ with equal probability. Would it be better off if you switch to the other?

Yes. In this case, the $y$ in $2y$ and $\frac{y}{2}$ refer to the same physical quantity, so the argument $0.5 \times 2y + 0.5 \times \frac{y}{2} = 1.25y > y$ holds.

Extension 1

For any value $y$ in the chosen envelope, the other one contains $2y$ and $\frac{y}{2}$ with equal probability. Would you switch?

Extension 2

A random $x$ is drawn from distribution $P(x=2^n)=\frac{2^n}{3^{n+1}}, n =0,1,2,\ldots$ . Two envelopes contain $x$ and $2x$ are presented to you. You choose one and it contains $y$ . Would you switch?

It seems that knowing the solution to the original problem and the twist, the extensions are easy. For extension 1, if we switch, we get $0.5 \times 2y + 0.5 \times \frac{y}{2} = 1.25y > y$ . For extension 2, given the chosen envelope containing $y$ , the posterior for the other one to contain $2y$ is $\frac{P(y)}{P(y)+P(\frac{y}{2})}=\frac{2}{5}$ . So the expected return if switch is $\frac{2}{5}\times 2y + \frac{3}{5}\times 0.5y = 1.1y > y$ . So we should switch!

Paradox again. Ahhhh…. Think about it for a minute. The solution is below.

Solution for Extension 1 and 2

The short answer: the expected amount of the money in the two settings does not exist. So the arguments based on concepts of expected value are false.

For the setup of extension 1 to hold, we need $P(2x)=0.5P(x)$ , so $\sum_x{xP(x)} \le\sum_{x=2^ny, n=0,1,\ldots}{xP(x)}=\sum_{n=0,1,\ldots}{yP(y)}=\infty$ .

The non-existence of $E(y)$ for extension 2 is easy to see.

Disclaimer

The materials presented above are reinterpretations of some original papers and Wikipedia articles. No new discovery is made, but I feel that the thought process is worth sharing.

December 3, 2011

Riding the wind

Ever wonder why it takes much shorter flying from SFO to Miami than back? The simple answer is the wind, or in some cases, jet stream.

At the altitude of 30,000 ft, in the temperate zone of the northern hemisphere, the air flows north due to the Earth Circulation (figure below), and deflects to the east due to the Coriolis effect. Flying east, the airplane is riding the wind, whereas flying west it’s against the wind. If the plane could fly at ultra low altitude, the wind effect would be opposite. (Of course the real situation is much more complicated than this simplified first-order explanation.)

December 1, 2011

Seven PhDs on the sea: what do you see besides fish when snorkeling?

Q: What do PhDs see when they snorkel in the Caribbeans?

A: Interesting pattern of sunlight on the sea floor!

Seven of my friends went to snorkel in the Grand Turk Island this Thanksgiving, and surprisingly, none of us could explain the beautiful, regular, and stable pattern of sunlight on the sea floor.

I decided to dig a little bit. It turns out that the wave pattern can be well described by the genus 2 solution of the Kadomtsev-Petviashvili (KP) Equation. The solution gives hexagonal shape of the waves, and the ridges of the waves focus sunlight on the sea floor, forming the pattern in the picture above.

I know I’m a layman in fluid dynamics. Any corrections or comments are welcome!

April 5, 2010

Man I hate uploading photos one by one, anyone know a better tool?

I do have Picasa, Flickr, Facebook, and Xiaonei albums, but I kept most of my blogs here. I knew MSN has some (IE only) plugin to do batch photo upload, but forgot the name. Anyone has a clue?

January 15, 2010

The Notorious Qualify Exam

Three months ago, I posted a blog officially declaring the start of my qual preparation, and now it’s all done. It’s hard to talk about the torture you suffered without hurting anyone, so I usually don’t do that. Instead, I have to show my two cents on the benefit of qualify exam to the students and to the department, ranked according to importance:

Benefits to the student:

Give you a chance to seriously think about if you really want the PhD degree. The road towards PhD is long and bumpy, and if you are not determined, you will clearly find this out when you are preparing for the quals, and you will quit the exam, altogether with the PhD thing. If you are not so sure, most likely you won’t prepare hard enough. Then for ordinary people, you will fail the exam due to it’s competitive nature (top 50% pass, and most people are equally intelligent). Then you quit PhD as well.
Consolidate your basic knowledge.
Train your communication skills through group study, especially for students who don’t speak good English.
Give you a reason to not quit PhD, if you pass. You make too much effort to give it up if you actually pass.
Stimulate your instinct of competition.
Get to know fellow students through group study, and know professors through impressing them. (For nerds and/or shy people.)
Increase your self confidence if you pass.

For those 7 items, I give them 70, 10, 10, 5, 2, 2, 1, respectively, out of 100.

Benefits to the department:

Improve graduate school admission, which is an art form. Given the limited resources, you can only accommodate a small amount of students compared to those who want to get in. However, you don’t want to be too strict in the first round of selection based on letter, personal statement and transcripts, since you will risk ruling out some good student whose talent cannot be reflected in those materials. So a “two rounds” approach of getting more students and selecting from the pool is good for the department.
Reduce PhD student dropout rate. It’s extremely expensive for the department to have a PhD student, so if the student drops out in the middle, it will be a big waste of resources. Quals can help choose those who are committed.
Give the professors extra chance to discover good students during exams.

For those 3 items, I give them 60, 35, 5, respectively, out of 100.

It’s a hard discrete optimization problem for such a sophisticated exam system, which involves ~150 students and ~50 professors, who has all kinds of preferences and schedule constraints. I salute Professor Gill and other professors who designed the system, and those who donated their precious time to do the exams.

January 15, 2010

Google-China Breakup?

Ok, as we all know, relationship needs mutual understanding to sustain. I love Google products, and I have a lot of friends working there, so I am trying to be supportive. However, I have to say that this is a bad BUSINESS decision.