Minimal Distance to Pi

Here is a problem from Week of Code 29 hosted by Hackerrank.

Problem Given two integers \(q_1\) and \(q_2\) (\(1\le q_1 \le q_2 \le 10^{15}\)), find and print a common fraction \(p/q\) such that \(q_1 \le q \le q_2\) and \(\left|p/q-\pi\right|\) is minimal. If there are several fractions having minimal distance to \(\pi\), choose the one with the smallest denominator.

Note that checking all possible denominators does not work as iterating for \(10^{15}\) times would exceed the time limit (2 seconds for C or 10 seconds for Ruby).

The problem setter suggested the following algorithm in the editorial of the problem:

  1. Given \(q\), it is easy to compute \(p\) such that \(r(q) := p/q\) is the closest rational to \(\pi\) among all rationals with denominator \(q\).
  2. Find the semiconvergents of the continued fraction of \(\pi\) with denominators \(\le 10^{15}\).
  3. Start from \(q = q_1\), and at each step increase \(q\) by the smallest denominator \(d\) of a semiconvergent such that \(r(q+d)\) is closer to \(\pi\) than \(r(q)\). Repeat until \(q\) exceeds \(q_2\).

Given \(q\), let \(d = d(q)\) be the smallest increment to the denominator \(q\) such that \(r(q+d)\) is closer to \(\pi\) than \(r(q)\). To justify the algorithm, one needs to prove the \(d\) is the denominator of one of the semiconvergents. The problem setter admits that he does not have a formal proof.

Inspired by the problem setter’s approach, here is a complete solution to the problem. Note that \(\pi\) should not be special in this problem, and can be replaced by any other irrational number \(\theta\). Without loss of generality, we may assume that \(\theta\in(0,1)\).

Let me first introduce the Farey intervals of \(\theta\).

  1. Start with the interval \((0/1, 1/1)\).
  2. Suppose the last interval is \((a/b, c/d)\). Cut it by the mediant of \(a/b\) and \(c/d\) and choose one of the intervals \((a/b, (a+c)/(b+d)), ((a+c)/(b+d), c/d)\) that contains \(\theta\) as the next interval.

We call the intervals appeared in the above process Farey intervals of \(\theta\). For example, take \(\theta = \pi – 3 = 0.1415926…\). The Farey intervals are:

$$(0/1, 1/1), (0/1, 1/2), (0/1, 1/3), (0/1, 1/4), (0/1, 1/5), (0/1, 1/6), (0/1, 1/7), (1/8, 1/7), (2/15, 1/7), \cdots$$

The Farey sequence of order \(n\), denoted by \(F_n\), is the sequence of completely reduced fractions between 0 and 1 which when in lowest terms have denominators less than or equal to \(n\), arranged in order of increasing size. Fractions which are neighbouring terms in any Farey sequence are known as a Farey pair. For example, Farey sequence of order 5 is

$$F_5 = (0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1).$$

Using the Stern–Brocot tree, one can prove that

Lemma 1 For every Farey interval \((a/b, c/d)\) of \(\theta\), the pair \((a/b, c/d)\) is a Farey pair. Conversely, for every Farey pair \((a/b, c/d)\), if \(\theta \in (a/b, c/d)\), then \((a/b, c/d)\) is a Farey interval.

We say \(p/q\) is a good rational approximation of \(\theta\) if every rational between \(p/q\) and \(\theta\) (exclusive) has a denominator greater than \(q\).

By the definition of Farey sequence, incorporating with Lemma 1, we know that

Lemma 2 A rational is an endpoint of a Farey interval of \(\theta\) if and only if it is a good rational approximation of \(\theta\).

In fact, one can show that the endpoints of Farey intervals and semiconvergents of continued fraction are the same thing! Thereof, the problem setter’s claim follows immediately from:

Proposition Given \(q\), let \(r(q) = p / q\) be the rational closest to \(\theta\) with denominator \(q\). If \(d = d(q)\) is the minimal increment to \(q\) such that \(r(q + d) = (p + c) / (q + d)\) is closer to \(\theta\) than \(r(q)\), then \(c/d\) is a good rational approximation.

Remark The proposition states that the increments to \(p/q\) always come from a good rational approximation. It is stronger than the problem setter’s statement, which only asserts that the increment to the \(q\) comes from a good rational approximation.

Proof In \((x, y)\)-plane, plot the trapezoid defined by

$$\left| y/x – \theta \right| < \left|p/q – \theta\right|, q < x < q + d.$$

Geometric interpretation

Also we interpret rational numbers \(p/q, (p+c)/(q+d)\) as points \(A = (q, p), B = (q+d, p+c)\). Let the line through \((q, p)\) parallel to \(y=\theta x\) intersect the vertical line \(x = q+d\) at \(C = (q+d, p+\theta d)\). By the definition of \(d\), we know that the trapezoid does not contain lattice points. In particular, there is no lattice point in the interior of the triangle \(ABC\). In the coordinate system with origin at \(A\), \(B\) has coordinate \((d, c)\) and the line through \(A, C\) is \(y = \theta x\). Since triangle \(ABC\) contains no lattice points, there is no \((b, a)\) with \(b < d\) such that \(a/b\) is between \(\theta\) and \(c/d\). In other words, \(c/d\) is a good rational approximation. QED.

Here is a fine print of the algorithm. Because floats may not have enough precision for the purpose of computation, we will instead use a convergent of the continuous fraction of \(\pi\) instead. All the computations will then happen in \(\mathbb{Q}\). Finally, we present the algorithm.

P = Rational(5706674932067741, 1816491048114374) - 3

# find endpoints of Farey intervals
a, b, c, d = 0, 1, 1, 1
farey = [[a,b],[c,d]]
while (f = b + d) <= max - min
  farey << [e = a + c, f]
  if P < Rational(e, f)
    c, d = e, f
  else
    a, b = e, f
  end
end

min, max = gets.split.map(&:to_i)
p_min = (P * q).round

# increase p_min/min by frations in farey
while min <= max
  c, d = nil, nil
  farey.each do |a, b|
    break if min + b > max
    if (Rational(p_min + a, min + b) - P).abs < (Rational(p_min, min) - P).abs
      c, d = a, b
      break
    end
  end
  break if d == nil
  p_min += c; min += d
end

puts "#{p_min + 3 * min}/#{min}"
0 (be the first to like this)

Shalom to Ning

I had never expected that Feb 19, 2017 would be the last day we say farewell to each.

Red Sea from Eilat

We used to talk about math puzzles, from blue-eyed islander puzzle to the hardest logic puzzle ever, every time on the bus from or to Shuk. We joked about the possibility that the apple cores we throw in the Carmel national park would one day become apple trees. We had plans to host a hot-pot party and introduce Mahjong to our Israeli friends…

I realized that all these can only expressed in past tense when I saw you forever asleep in Eilat.

We were so close, yet we are so far apart.

0 (be the first to like this)

First week in Israel

Here is a list of things I have experienced during the first week in Israel and some tips for those of you who plan to visit me in Haifa!

Hainan airline has a direct flight from Beijing to Tel Aviv, and they have a resting area for transiting passengers in Beijing.

If this is your first time in Israel, make sure your arrival day is not Saturday or any holiday. Saturday (or holiday) means almost no public transportation, almost no restaurants and fewer people on the street whom you can ask help from.

Most Israelis are quite friendly and speak decent English. Even if someone does not speak English at all, he or she is always able to grab someone closeby to help.

You can exchange all major currencies (eg. US dollars, Chinese yuan) for new Israeli shekels at the airport in Tel Aviv at Bank Hapoalim. Expectedly, the rate is not as good as what you can get outside the airport. A lot of places accept major credit cards, such as Visa and Mastercard. Some places ask for a purchase of 20 shekels or more if you use credit card.

The vending machines for train tickets did not accept my Mastercard. The ticket from the airport to Haifa (Hof Hacarmel station) costs 35 shekels. The train is on platform 2 and it has WiFi connection. Use Google map to tell which station you are arriving if you, like myself, do not understand enough Hebrew.

The train from Tel Aviv to Haifa goes along the coastal line of the mediterranean sea. Highway no.2 lies between the rails and the coast, which resembles highway no.1 in California.

Bus no.11 goes from Hof Hacarmel to Technion. The bus fare is something slightly less than 6 shekels. Moovit is a must for public transportation planning, and it can send you notification when you are approaching at your destination.

Uber and Lyft do not have services in Haifa (but Uber does in Tel Aviv). People use Gett (aka Get Taxi) to call cabs. Since tipping is not required for taxi, remember to turn off automatic tipping in the app. You can use my code GTMLIYK for 15 shekels off your 1st ride.

The most popular messaging app is WhatsApp. I was asked for my WhatsApp contact for quite a few times.

Google Fi (global cellular service including data) works quite well in Israel. For the first week, I’ve heavily relied on my smart phone for navigation, transportation and information retrieving. It’s probably a good idea to carry a power bank. The outlet sockets in Israel are Type C and H.

IMG_20160825_180131
Mediterranean sea from Hof Hacarmel.

Other random observations:

On Sunday, the train is full of soldiers. A few were probably carrying M4 carbines when I was on the train.

The rent for the property listed online (eg. yod2.co.il or Facebook group) usually does not include city tax and building management fee.

Some apartments in Haifa have a separate room for the toilet only.

You give all the checks for the rent to the landlord when you sign the contract. Technion is able to write a guarantee letter to the landlord saying that they will freeze your last payment as the security deposit.

You will not be able to change the PIN, set by the bank, of your debit card, at least for Bank Leumi, the other major bank in Israel besides Bank Hapoalim.

Hebrew calendar and Chinese calendar are both lunisolar, so they are similar in a lot of ways. Friday and Saturday are weekends in Israel.

High schoolers can choose how difficult the math they want to learn. For example, calculus (including formulas like \(e^{i\theta} = \cos \theta + i\sin\theta\)) is offered in high schools.

However, most high school graduates need to go to army for 2-3 years and it’s hard to recall what they have learnt after the army. Top students might have the option to delay their military service.

Pork and shellfish are not Kosher, so you will not be able to see them in most supermarkets. It is also not Kosher to eat meat with milk.

0 (be the first to like this)

A Short Proof of the Nash-Williams’ Partition Theorem

Notations

  1. \(\mathbb{N}\) – the set of natural numbers;
  2. \(\binom{M}{k}\) – the family of all subsets of \(M\) of size \(k\);
  3. \(\binom{M}{<\omega}\) – the family of all finite subsets of \(M\);
  4. \(\binom{M}{\omega}\) – the family of all infinite subsets of \(M\);

The infinite Ramsey theorem, in its simplest form, states that for every partition \(\binom{\mathbb{N}}{k} = \mathcal{F}_1 \sqcup \dots \sqcup \mathcal{F}_r\), there exists an infinite set \(M\subset \mathbb{N}\) such that \(\binom{M}{k}\subset \mathcal{F}_i\) for some \(i\in [r]\). The Nash-Williams‘ partition theorem can be seen as a strengthening of the infinite Ramsey theorem, which considers a partition of a subset of \(\binom{\mathbb{N}}{<\omega}\).

Notations

  1. \(\mathcal{F}\restriction M\) – \(\mathcal{F}\cap 2^M\), that is, the set \(\{s\in\mathcal{F} : s\subset M\}\).
  2. \(s \sqsubset t \), where \(s,t\) are subsets of \(\mathbb{N}\) – \(s\) is an initial segment of \(t\), that is \(s = \{n\in t : n \le \max s\}\).

Definition Let set \(\mathcal{F} \subset \binom{\mathbb{N}}{<\omega}\).

  1. \(\mathcal{F}\) is Ramsey if for every partition \(\mathcal{F}=\mathcal{F}_1\sqcup \dots\sqcup\mathcal{F}_r\) and every \(M\in\binom{\mathbb{N}}{\omega}\), there is \(N\in\binom{M}{\omega}\) such that \(\mathcal{F}_i\restriction N = \emptyset\) for all but at most one \(i\in[r]\).
  2. \(\mathcal{F}\) is a Nash-Williams family if for all \(s, t\in\mathcal{F}, s\sqsubset t \implies s = t\).

Theorem [NASH-WILLIAMS 1965] Every Nash-Williams family is Ramsey.

The proof presented here is based on the proof given by Prof. James Cummings in his Infinite Ramsey Theory class. The purpose of this rewrite is to have a proof that resembles the one of the infinite Ramsey theorem.

Notation Let \(s\in\binom{\mathbb{N}}{<\omega}\) and \(M\in\binom{\mathbb{N}}{\omega}\). Denote $$[s, M] = \left\{t \in \binom{\mathbb{N}}{<\omega} : t \sqsubset s \text{ or } (s \sqsubset t \text{ and } t\setminus s \subset M)\right\}.$$

Definition Fix \(\mathcal{F}\subset \binom{\mathbb{N}}{<\omega}\) and \(s\in \binom{\mathbb{N}}{<\omega}\).

  1. \(M\) accepts \(s\) if \([s, M]\cap \mathcal{F}\neq \emptyset\) and \(M\) rejects \(s\) otherwise;
  2. \(M\) strongly accepts \(s\) if every infinite subset of \(M\) accepts \(s\);
  3. \(M\) decides \(s\) if \(M\) either rejects \(s\) or strongly accepts it.

We list some properties that encapsulates the combinatorial characteristics of the definitions above.

Properties

  1. If \(M\) decides (or strongly accepts, or rejects) \(s\) and \(N\subset M\), then \(N\) decides (respectively strongly accepts, rejects) \(s\) as well.
  2. For every \(M\in\binom{\mathbb{N}}{\omega}\) and \(s\in\binom{\mathbb{N}}{<\omega}\), there is \(N_1\in\binom{M}{\omega}\) deciding \(s\). Consequently, there is \(N_2\in\binom{M}{\omega}\) deciding every subset of \(s\).

Proof of Theorem Enough to show that if \(\mathcal{F} = \mathcal{F}_1\sqcup \mathcal{F}_2\), then for every \(M\in\binom{\mathbb{N}}{\omega}\), there is infinite \(N\in \binom{M}{\omega}\) such that \(F_i \restriction N = \emptyset\) for some \(i\in[2]\).

We are going to use \(\mathcal{F}_1\) instead of \(\mathcal{F}\) in the definitions of “accept”, “reject”, “strongly accept” and “decide”. Find \(N\in \binom{M}{\omega}\) that decides \(\emptyset\). If \(N\) rejects \(\emptyset\), by definition \(\mathcal{F}_1\restriction N = [\emptyset, N]\cap \mathcal{F}_1 = \emptyset\). Otherwise \(N\) strongly accepts \(\emptyset\).

Inductively, we build a decreasing sequence of infinite sets \(N \supset N_1 \supset N_2\supset \dots \), an increasing sequence of natural numbers \(n_1, n_2, \dots\), and maintain that \(n_i\in N_i, n_i < \min N_{i+1}\) and that \(N_i\) strongly accepts every \(s\subset \{n_j : j < i\}\). Initially, we take \(N_1 = N\) as \(N\) strongly accepts \(\emptyset\).

Mental picture of how \(n_i\) and \(N_i\) look like.
A mental picture of the construction.
Suppose \(N_1 \supset \dots \supset N_i\) and \(n_1 < \dots < n_{i-1}\) have been constructed. In the following lemma, when taking \(M = N_i\) and \(s = \{n_j : j < i\}\), it spits out \(m\) and \(N\), which are exactly what we need for \(n_i\) and \(N_{i+1}\) to finish the inductive step.

Lemma Suppose \(M\in\binom{\mathbb{N}}{\omega}\), \(s\in\binom{\mathbb{N}}{<\omega}\) and \(\max s < \min M\). If \(M\) strongly accepts every subset of \(s\), then there are \(m \in M\) and \(N \in \binom{M}{\omega}\) such that \(n < \min N\) and \(N\) strongly accepts every subset of \(s\cup \{n\}\)

Proof of lemma We can build \(M = M_0 \supset M_1\supset M_2 \supset \dots\) such that for every \(i\), \(m_i := \min M_i < \min M_{i+1}\) and \(M_{i+1}\) decides every subset of \(s\cup \{m_i\}\). It might happen that \(M_{i+1}\) rejects a subset of \(s\cup \{m_i\}\). However, we claim that this cannot happen for infinitely many times.

Otherwise, by the pigeonhole principle, there is \(t\subset s\) such that \(I = \{i : M_{i+1} \text{ rejects }t\cup\{m_{i}\}\}\) is infinite. Let \(M’ = \{m_i : i\in I\}\). Note that \([t, M’] \subset \cup_i [t\cup\{m_i\}, M_{i+1}]\), and so \([t,M’]\cap \mathcal{F}_1\subset \cup_i \left([t\cup\{m_i\}, M_{i+1}]\cap\mathcal{F}_1\right) = \emptyset\). Hence \(M’\subset M\) rejects \(t\subset s\), which is a contradiction.

Now we pick one \(i\) such that \(M_{i+1}\) strongly accepts every subset of \(s\cup\{m_i\}\), and it is easy to check that \(m = m_i\) and \(N = M_{i+1}\) suffice. QED for lemma.

Finally, we take \(N_\infty = \{n_1, n_2, \dots\}\). For any \(s\in\binom{N_\infty}{<\omega}\), there is \(i\) such that \(s\subset \{n_1, \dots, n_{i-1}\}\). Note that \(N_i\) strongly accepts \(s\) and \(N_\infty\subset N_i\). Therefore \(N_\infty\) (strongly) accepts \(s\), that is \([s, N_\infty]\cap \mathcal{F}_1 \neq \emptyset\), and say \(t\in [s, N_\infty]\cap \mathcal{F}_1\). Because \(t\in\mathcal{F}_1\) and \(\mathcal{F} = \mathcal{F}_1 \sqcup \mathcal{F}_2\) is a Nash-Williams family, \(s\notin \mathcal{F}_2\). QED.

11 (this post is made with love)

Alternative to Beamer for Math Presentation

Although using blackboard and chalk is the best option for a math talk for various reasons, sometimes due to limit on the time, one has to make slides to save time on writing. The most common tools to create slides nowadays are LaTeX and Beamer.

When I was preparing for my talk at Vancouver for Connections in Discrete Mathematics in honor of the work of Ron Graham, as it is my first ever conference talk, I decided to ditch Beamer due to my lack of experience. Finally, I ended up using html+css+javascript to leverage my knowledge in web design.

The javascript framework I used is reveal.js. Though there are other options such as impress.js, reveal.js fits better for a math talk. One can easily create a text-based presentation with static images / charts. The framework also has incorporated with MathJax as an optional dependency, which can be added with a few lines of code. What I really like about reveal.js as well as impress.js is that they provide a smooth spatial transition between slides. However, one has to use other javascript library to draw and animate diagrams. For that, I chose raphael.js, a javascript library that uses SVG and VML for creating graphics so that users can easily, for example, create their own specific chart. The source code of the examples on the official website is really a good place to start.

To integrate reveal.js and raphael.js to achieve a step-by-step animation of a diagram, I hacked it by adding a dummy fragment element in my html document so that reveal.js can listen to the fragmentshown event and hence trigger raphael.js to animate the diagram. In cases where the diagrams are made of html elements, I used jQuery to control the animation. Here is my favorite animation in the slides generated by jQuery.

Untitled
How does mathematics progress?

However, one has to make more effort to reverse the animation made by raphael.js or jQuery if one wants to go backwards in slides. I did not implement any reverse animation since I did not plan to go back in slides at all.

In case there is no internet access during the presentation, one has to have copies of all external javascript libraries (sometimes also fonts), which, in my case, are MathJax, raphael.js and jQuery. In order to use MathJax offline, one need to configure reveal.js. Here is how my final html document looks like.

<!doctype html>
<html lang="en">

<head>
  <meta charset="utf-8">
  <title>A Bound on Turán Number for Cycles of Even Length</title>
  <meta name="description" content="A contributed talk at Connections in Discrete Mathematics">
  <meta name="author" content="Ziln Jiang">
  <link rel="stylesheet" href="css/reveal.css">
  <link rel="stylesheet" href="css/theme/solarized.css" id="theme">
  <link rel="stylesheet" href="css/custom.css"> <!-- your customized css stylesheet can go here -->
  <!--[if lt IE 9]>
  <script src="lib/js/html5shiv.js"></script>
  <![endif]-->
</head>

<body>
  <div class="reveal">
    <div class="slides">
      <section>
         ...
      </section>
    </div>
  </div>
  <script src="lib/js/head.min.js"></script>
  <script src="lib/js/jquery.min.js"></script> <!-- local jQuery library -->
  <script src="js/raphael-min.js"></script> <!-- local raphael.js -->
  <script src="js/reveal.js"></script>
  <script src="js/diagram-animation.js"></script> <!-- your additional animation can go here -->
  <script>
    Reveal.initialize({
      controls: false,
      slideNumber: true,
      progress: true,
      fragments: true,
      // Optional libraries used to extend on reveal.js
      dependencies: [
        { src: 'plugin/math/math.js', async: true } // to enable MathJax
      ],
      math: {
        mathjax: 'lib/js/MathJax/MathJax.js' // local MathJax
      }
    });
  </script>
</body>

</html>

Currently, my slides only work on Chrome correctly. There is another bug that I have not figured out yet. If I start afresh from the first slide, then my second diagram generated by Raphael is not rendered correctly. I got around it by refreshing the slide where the second diagram lives. This is still something annoying that I would like to resolve.

After all, I really like this alternative approach of making slides for math presentation because it enables me to implement whatever I imagine.

15 (this post is made with love)

十一年

数学领域里关于随机过程有两个容易混淆的概念,一个叫上鞅,一个叫下鞅。大致是说,上鞅随着时间的演化会越来越糟糕,而下鞅则相反,越变越美好。两年前,在读研究生课程的时候,教授课程的老师为了方便大家记忆,就告诉我们说:“人生是一个上鞅。”言下之意,人生是越来越糟糕的。

人生是越来越糟糕的,比如现在每次打球必须要做热身才敢上场,又比如已经记不起上一次《成长的足迹》具体写了什么,又比如不能在我们最尊爱的人的身边当他们一个一个离我们远去,又比如……

生活的大潮把我们不断地改变着,把曾经熟悉的面孔冲散在茫茫人海中,再给我们一个叫微信的东西,让我们在掌中寻找彼此。如果想要了解一个进华人的生活现状和人生轨迹,看看他或她的朋友圈里的更新可能就足够了吧。

既然如此,我想以下的文字不应该是关于现实中的我。既然是继续成长的足迹,那就不妨假设一下我们这伙人从进华毕业,升入同一所高中,进入同一所大学,直到今天所有的同学老师甚至同学的家长都还在我的生活中出现,我的一天会是怎样的呢?

为了让阅读这篇文章更加有乐趣,具体人物的姓名就不提了。如果其中一些桥段能引起你的共鸣,请毫不犹豫对号入座。

故事要开始了。

这是一个美国匹兹堡的初夏,知了还没有开始鸣叫。这已经是我在卡内基梅隆大学开始攻读博士学位以来的第四个夏天了。

我住在一个四室一厅的公寓里,三个室友还是以前在进华的三位室友,其中两位已经在当地找到了工作,另一位在攻读博士学位,不过是在另一所大学。整个公寓约定周五是早餐日,用来提醒大家即便再忙也要记得吃早餐。大家便在约定好的时间围坐在客厅餐桌周围,边吃边商量着周末是不是找一天通宵打八十分,有人开玩笑提醒说,这项古老的运动当年是在阳台上秘密进行,其余人纷纷表示赞同延续这个传统。

早餐完毕,我下楼和楼管打招呼,虽然现在大家都有手机和互联网了,但不知为何传达室里还是有一台投币电话。虽然已经好久没有人使用了,但据说投入硬币之后就能听到最思念的人的声音。对了,每次一元。公寓大厅入口放着一叠当地的报纸,一位初中同班在该报社工作,时不时还会找当年的同学采访,报道民生。

我走路来到学校,一路上,随身听里放着周杰伦的龙卷风。这首歌是初中时候第一次接触流行音乐时听的,从此一盘盘磁带,一张张 CD,陪伴着青春。我跟着哼唱,爱情来得太快就像龙卷风……

突然,走廊里出现了系主任,他是从历史系调过来的。我们互相打招呼,系主任不常询问大家的学业情况,但却密切关注每个学生的感情状况。不知道他是不是听到我刚才哼的曲子了,他和最后一次见面一样,质问我道:“你怎么回事?怎么还没有找女朋友?赶紧列一个单子把喜欢女孩的名字写出来!要主动点!”我勉强一笑,心里知道他迫不及待地希望能看到每个人都能早日成家立业。我边告退,边笑着并敷衍着:“马上列,马上列!”

走着走着,我经过一间教室。往里一瞥,班中原来那位少年大学生已经开始了他的教学生涯。他的学生中有几个知道他们的老师当年可是班中最调皮的学生之一呢?现在为人师表,会不会在看到班中调皮的学生时,看到那些年的自己呢?偶然间,想到他也还没有成家,心里暗暗松了一口气。

上午一晃而过,中午去学校食堂的路上,遇到一群在把网球当足球踢的本科生。我心想还是踢瓶盖更环保一些。又走不远,另外一群孩子拿着 iPhone 和 iPad 正在玩部落战争。这简直太逊了,初中班级里发明的拍手游戏变化多端、风靡全年级,游戏平衡性和竞技性岂是这些触屏上的游戏能比拟的。我边走边骄傲地想,这些都应该进入世界文化遗产名录。

饭后回到办公室,我打开电脑开始刷微博,人生百态在眼前展开。可惜今天的头条又不是汪峰,而是班中两位青梅竹马的一对结婚了。系主任要是知道了,肯定得拿这事情当正面典型。

关上微博,在办公室工作了几个小时后,学院里的研究生和教授开始纷纷回家,预备享受周末。英语里 TGIF 的意思是 Thank God It’s Friday (感谢上帝今天是周五),当地人一般都会去酒吧消遣,但我还是同几位当年的球友约定在学校的篮球场感谢上帝。我们今天约了和另外一组美籍华人打全场对抗,虽然没有什么人围观,但我们还是非常认真地对待。对方有几个球员的个人能力非常厉害,但我方毕竟一起磨练多年,不用看就知道队友的位置。突破,分球,倒到圈顶,三分球进了。这是我们常用的战术,而且变化很多。包夹,盗球,抢篮板,盖帽,后仰跳投,每个人都有自己的擅长。汗水挥洒在篮球场上,没有人记得比分。

打完球,大家一起吃晚餐,有另外几位同学也加入了进来。那些在金融或咨询行业工作的几个人总是姗姗来迟。有时会有急事接到电话:“喂?啊,上次那三百万美金的跨国合约……”剩下的人嘴上羡慕嫉妒着,但心里却为这些人在各个行业的成功由衷高兴着。一些在高科技行业工作的同学分享着新的创业机会和股市消息,一些人聚精会神地听着,就好像是考前在听老师圈考点。晚餐临近结束,那位家里有孩子的奶爸扭扭捏捏地说不能久留,要回家给孩子喂奶了。酒足饭饱后,大家各自回家。

我回到自己的公寓,仰面躺在床上,想起了当年初中住宿夜聊室友彻夜讲述《神雕侠侣》,想起上课吃橙子听 CD 纷纷被老师发现没收,想起笑容依旧挂在那一张张天真无邪的脸上,想起……

我注视着房顶的电风扇一圈一圈地摇着头,眼前开始渐渐朦胧,从窗户进入的夏日晚风像一张蚊帐开始笼罩着我……

虽然这一切的一切都是基于一个很大的不可能——如果那些人还依然陪伴着我们,但这些可能性或者说这些梦却似乎在另一个平行宇宙里影响着毕业之后的我们,成为我们这代人的基音之一。这些进华的人和进华的事常以回忆的方式回来提醒我、温暖我、鼓励我。

我为此感恩。

注:本文是为上海市民办进华中学建校二十周年校庆而作,将收录在《继续成长的足迹》一书中。

8 (this post is made with love)

A Short Proof for Hausdorff Moment Problem

Hausdorff moment problem asks for necessary and sufficient conditions that a given sequence \((m_n)\) with \(m_0=1\) be the sequence of moments of a random variable \(X\) supported on \([0,1]\), i.e., \(\operatorname{E}X^n=m_n\) for all \(n\).

In 1921, Hausdorff showed that \((m_n)\) is such a moment sequence if and only if the sequence is completely monotonic, i.e., its difference sequences satisfy the equation \((D^r m)_s \ge 0\) for all \(r, s \ge 0\). Here \(D\) is the difference operator on the space of real sequences \((a_n)\) given by \(D a = (a_{n} – a_{n+1})\).

The proof under the fold follows the outline given in (E18.5 – E18.6) Probability with Martingales by David Williams.

Proof of Necessity Suppose \((m_n)\) is the moment sequence of a random variable \(X\) supported on \([0,1]\). By induction, one can show that \((D^r m)_s = \operatorname{E}(1-X)^rX^s\). Clearly, as \(X\) is supported on \([0,1]\), the moment sequence is completely monotonic.

Proof of Sufficiency Suppose \((m_n)\) is a completely monotonic sequence with \(m_0 = 1\).

Define \(F_n(x) := \sum_{i \le nx}{n\choose i}(D^{n-i}m)_i\). Clearly, \(F_n\) is right-continuous and non-decreasing, and \(F_n(0^-) = 0\). To prove \(F_n(1) = 1\), one has to prove the identity $$\sum_{i}{n\choose i}(D^{n-i}m)_i = m_0.$$

Classical Trick Since the identity above is about vectors in the linear space (over the reals) spanned by \((m_n)\) and the linear space spanned by \((m_n)\) is isomorphic to the one spanned by \((\theta^n)\), the identity is equivalent to $$\sum_{i}{n\choose i}(D^{n-i}\theta)_i = \theta^0,$$ where \(\theta_n = \theta^n\). Now, we take advantage of the ring structure of \(\mathbb{R}[\theta]\). Notice that \((D^{r}\theta)_s = (1-\theta)^r\theta^s\). Using the binomial theorem, we obtain $$\sum_{i}{n\choose i}(D^{n-i}\theta)_i = \sum_{i}{n\choose i}(1-\theta)^{n-i}\theta^i = (1-\theta + \theta)^n = \theta^0.$$

Therefore \(F_n\) is a bona fide distribution function. Define \(m_{n, k} := \int_{[0,1]} x^kdF_n(x)\), i.e., \(m_{n,k}\) is the \(k\)th moment of \(F_n\). We now find an explicit formula for \(m_{n,k}\).

Noticing that \(F_n\) is constant, say \(c_{n,i}\), on \([\frac{i}{n}, \frac{i+1}{n})\), for all \(i=0, \dots, n-1\) and \(c_{n,i}\) is a linear combination of \(m_0, \dots, m_n\), we know that \(m_{n,k} = \sum_{i=0}^n a_{n,k,i}m_i\).

Just like what we did in proving the identity, we use the special case \(m_n = \theta^n\) to compute the coefficients \(a_i = a_{n,k,i}\), where \(0 \le \theta \le 1\). In this case, $$F_n(x) = \sum_{i \le nx}{n\choose i}(D^{n-i}\theta)_i = \sum_{i\le nx}{n\choose i}(1-\theta)^{n-i}\theta^i, m_{n,k} = \sum_{i=0}^n a_{i}\theta^i.$$

Now consider the situation in which a coin with probability \(\theta\) is tossed at times \(1,2,\dots\). The random variable \(H_k\) is \(1\) if the \(k\)th toss produces heads, \(0\) otherwise. Define \(A_n := (H_1 + \dots + H_n)/n\). It is immediate from the formula of \(F_n\) that \(F_n\) is the distribution function of \(A_n\), and so \(m_{n,k}\) is the \(k\)th moment of \(A_n\). However, one can calculate the \(k\)th moment of \(A_n\) explicitly. Let \(f\colon [k] \to [n]\) be chosen uniformly at random, \(Im_f\) be the cardinality of the image of \(f\) and denote by \(p_i = p_{n,k,i} := \operatorname{Pr}(Im_f = i)\). Using \(f, Im_f\) and \(p_i\), we obtain $$\operatorname{E}A_n^k = \operatorname{E}\left(\frac{H_1 + \dots + H_n}{n}\right)^k = \operatorname{E}H_{f(1)}\dots H_{f(k)} = \operatorname{E}\operatorname{E}[H_{f(1)}\dots H_{f(k)}\mid Im_f] = \operatorname{E}\theta^{Im_f} = \sum_{i=0}^n p_{i}\theta^i.$$ Therefore, for all \(\theta\in [0,1]\), we know that \(\sum_{i=0}^n a_i\theta^i = \sum_{i=0}^n p_i\theta^i\), and so \(a_i = p_i\) for all \( i=0,\dots, n\).

As both \((a_i)\) and \((p_i)\) do not depend on \(m_i\), \(a_i = p_i\) holds in general. Since \(p_k = p_{n, k, k} = \prod_{i=0}^{k-1}(1-i/n)\to 1\) as \(n\to\infty\)  and \(p_i = 0\) for all \(i > k\), we know that \(\lim_n m_{n,k}= m_k\).

Using the Helly–Bray Theorem, since \((F_n)\) is tight, there exists a distribution function \(F\) and a subsequence \((F_{k_n})\) such that \(F_{k_n}\) converges weakly to \(F\). The definition of weak convergence implies that $$\int_{[0,1]} x^k dF(x) = \lim_n \int_{[0,1]}x^k dF_{k_n}(x) = \lim_n m_{k_n,k} = m_k.$$ Therefore, the random variable \(X\) with distribution function \(F\) is supported on \([0,1]\) and its \(k\)th moment is \(m_k\). QED

There are other two classical moment problems: the Hamburger moment problem and the Stieltjes moment problem.

2 (this post is made with love)

欺诈猜数游戏(下)

上次的日志,先重复一下谜题:

欺诈猜数游戏在甲和乙之间进行,甲和乙都知道正整数 \(k\) 和 \(n\)。游戏开始时,甲先选定两个整数 \(x\) 和 \(N\),其中 \(1\leq x\leq N\)。甲告诉乙 \(N\) 的值,但对 \(x\) 守口如瓶。乙试图通过提问来获得与 \(x\) 相关的信息:每次提问,乙任选一个由若干正整数组成的集合\(S\)(可以重复使用之前提问中使用过的集合),问甲“\(x\)是否属于\(S\)?”。乙可以提任意数量的问题。每次提问之后,甲立刻回答是或否,甲可以说谎话,但在任意连续 \(k+1\) 次回答中至少有一次回答是真话。

在乙问完所有想问的问题之后,乙必须指出一个至多包含n个正整数的集合\(X\),若\(x\)属于\(X\),则乙获胜;否则甲获胜。证明:对所有充分大的整数\(k\),存在整数\(n\geq 1.99^k\),使得乙无法保证获胜。

为了解决第二个问题,需要从甲的角度考虑问题,每一次回答问题后,使得乙无法缩小 \(x\) 范围。

为此我们考虑贪心策略:甲每次在乙提出的集合和其补集中选择元素较多的那个集合。很明显这个策略有一个弱点:如果乙每次提问都问“\(x\) 是不是 \(1\) 呢?”那甲如果每次只顾眼前利益,应当回答“不是。”但经过 \(k+1\) 轮之后,甲就能轻松排除 \(1\),从而缩小 \(x\) 的范围。

于是甲的策略必须是一种折中的策略,既要顾及眼前的利益,又不能放弃长期的利益。我们设定 \(N=n+1\)。

于是甲在觉得到底要选择乙提出的集合或是其补集前,对 \(1\) 到 \(n+1\) 中每个数都进行打分。甲对 \(i\) 的打分是 \(a^{m_i}\),其中\(a = 1.999\) 而 \(m_i\) 满足 \(i\) 在最近连续 \(m_i\) 次选择的集合中都不出现。根据每个元素的打分,甲在 \(S\) 和 \(S^c\) 中选择会使得之后整个集合总分较低的那个集合。

为了让证明成立,设定 \(n = (2-a)a^{k+1} – 1\)。下面,我们通过归纳法证明每一次所有元素的总分不超过 \(a^{k+1}\)。根据打分规则,最开始总分是 \(n = (2-a)a^{k+1}-1 < a^{k+1}\),命题显然那成立。假设目前的总分是 \(y = \sum_{i=1}^{n+1} a^{m_i}\),乙给出集合 \(S\),如果甲选 \(S\),则总和变为 \(y_1 = \sum_{i\in S}1 + \sum_{i\notin S}a^{m_i+1}\),如果甲选 \(S^c\),则总和变为 \(y_2 = \sum_{i\notin S}1 + \sum_{i\in S}a^{m_i+1}\)。由于甲会选择使得总和变得更小的那个策略,于是他回答后总和至多为 \(\frac{1}{2}(y_1 + y_2) = \frac{1}{2}(ay+n+1)\)。由于 \(y < a^{k+1}\),总和小于 \(\frac{1}{2}(a\cdot a^{k+1}+(2-a)a^{k+1}) = a^{k+1}\)。命题成立!

如果 \(i\) 连续 \(k+1\) 次没有被甲选中,则其得分已经为 \(a^{k+1}\)。这不可能,因为总分总是小于 \(a^{k+1}\)。也就是说在这样的策略下乙无法缩小 \(x\) 的可能范围。证毕!

5 (this post is made with love)

An Upper Bound on Stirling Number of the Second Kind

We shall show an upper bound on the Stirling number of the second kind, a byproduct of a homework exercise of Probabilistic Combinatorics offered by Prof. Tom Bohman.

Definition A Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of \(n\) objects into \(k\) non-empty subsets and is denoted by \(S(n,k)\).

Proposition For all \(n, k\), we have $$S(n,k) \leq \frac{k^n}{k!}\left(1-(1-1/m)^k\right)^m.$$

Proof Consider a random bipartite graph with partite sets \(U:=[n], V:=[k]\). For each vertex \(u\in U\), it (independently) connects to exactly one of the vertices in \(V\) uniformly at random. Suppose \(X\) is the set of non-isolated vertices in \(V\). It is easy to see that $$\operatorname{Pr}\left(X=V\right) = \frac{\text{number of surjections from }U\text{ to }V}{k^n} = \frac{k!S(n,k)}{k^n}.$$

On the other hand,  we claim that for any \(\emptyset \neq A \subset [k]\) and \(i \in [k]\setminus A\), $$\operatorname{Pr}\left(i\in X \mid A\subset X\right) \leq \operatorname{Pr}\left(i\in X\right).$$ Note that the claim is equivalent to $$\operatorname{Pr}\left(A\subset X \mid i\notin X\right) \geq \operatorname{Pr}\left(A\subset X\right).$$ Consider the same random bipartite graph with \(V\) replaced by \(V’:=[k]\setminus \{i\}\) and let \(X’\) be the set of non-isolated vertices in \(V’\). The claim is justified since $$\operatorname{Pr}\left(A\subset X\mid i\notin X\right) = \operatorname{Pr}\left(A\subset X’\right) \geq \operatorname{Pr}\left(A\subset X\right).$$

Set \(A:=[i-1]\) in above for \(i = 2, \ldots, k\). Using the multiplication rule with telescoping the conditional probability, we obtain $$\begin{eqnarray}\operatorname{Pr}\left(X=V\right) &=& \operatorname{Pr}\left(1\in X\right)\operatorname{Pr}\left(2\in X \mid [1]\subset X\right)\ldots \operatorname{Pr}\left(k\in X\mid [k-1]\subset X\right)\\ & \leq & \operatorname{Pr}\left(1\in X\right)\operatorname{Pr}\left(2\in X\right)\ldots\operatorname{Pr}\left(k\in X\right) \\ & = & \left(1-(1-1/m)^k\right)^m.\end{eqnarray}$$ QED.

4 (this post is made with love)

A Probabilistic Proof of Isoperimetric Inequality

This note is based on Nicolas Garcia Trillos’ talk, Some Problems and Techniques in Geometric Probability, at Carnegie Mellon University on January 29, 2015.

In particular, we demonstrate a probabilistic proof of the isoperimetric inequality. The proof can also be found in Integral Geometry and Geometric Probability by Luis A. Santaló.

Theorem For a convex set with perimeter \(L\) and area \(A\), the isoperimetric inequality states that \(4\pi A\leq L^2\), and that equality holds if and only if the convex set is a disk. (Assume that the boundary is a closed convex curve of class \(C^1\).)

Proof Let \(P(s)\) parametrize the boundary by its arc length \(s\). Given \(s\) and \(\theta\). Suppose the line through \(P(s)\) whose angle to the tangent line equals \(\theta\) intersects the boundary at another point \(Q(s)\). Let \(\sigma(s, \theta)\) be the length of the chord between the two intersections \(P(s), Q(s)\). Consider the integral $$\int (\sigma_1\sin\theta_2 – \sigma_2\sin\theta_1)^2 \mathrm{d}s_1\mathrm{d}\theta_1\mathrm{d}s_2\mathrm{d}\theta_2,$$ where the integration extends over \(0 \leq s_1, s_2 \leq L\) and \(0 \leq \theta_1, \theta_2 \leq \pi\).

Random variables
Random variables

Expanding the square in the integrand, we obtain that the integral is equal to $$\pi L \int \sigma^2\mathrm{d}s\mathrm{d}\theta – 2\left(\int \sigma\sin\theta\mathrm{d}s\mathrm{d}\theta\right)^2.$$

On one hand, we have $$\int \sigma^2\mathrm{d}s\mathrm{d}\theta = \int_0^L\int_0^\pi \sigma^2\mathrm{d}\theta\mathrm{d}s = \int_0^L 2A\mathrm{d}s = 2LA.$$

Change variables
Change variables

On the other hand, let \(p\) be the distance from the chord to the origin and \(\phi\) the angle from the \(x\)-axis to the chord. Suppose the angle from the \(x\)-axis to the tangent line is \(\tau\). We have $$p = \langle x, y\rangle\cdot\langle \sin\phi, -\cos\phi \rangle = x\sin\phi – y\cos\phi.$$ Differentiating the latter, we get $$\mathrm{d}p = \sin\phi\mathrm{d}x – \cos\phi\mathrm{d}y + (x\cos\phi + y\sin\phi)\mathrm{d}\phi.$$ Moreover, we know that $$\mathrm{d}x = \cos\tau\mathrm{d}s, \mathrm{d}y = \sin\tau\mathrm{d}s.$$ Therefore $$\mathrm{d}p = \sin\phi\cos\tau\mathrm{d}s – \cos\phi\sin\tau\mathrm{d}s + + (x\cos\phi + y\sin\phi)\mathrm{d}\phi,$$ and so $$\mathrm{d}p\mathrm{d}\phi = \sin(\phi – \tau)\mathrm{d}s\mathrm{d}\phi.$$ Since \(\theta + \phi = \tau\) and \(\mathrm{d}\theta + \mathrm{d}\phi = \tau’\mathrm{d}s\), we have $$\mathrm{d}p\mathrm{d}\phi = -\sin\theta\mathrm{d}s\mathrm{d}\theta,$$ and so $$\int\sigma\sin\theta\mathrm{d}s\mathrm{d}\theta = \int_0^{2\pi}\int_{-\infty}^\infty \sigma\mathrm{d}p\mathrm{d}\theta = 2\pi A.$$

Since the integral is non-negative, we have that \(2\pi A(L^2 – 4\pi A)\geq 0\), and so \(4\pi A \leq L^2\). The equality is achieved if and only if \(\sigma / \sin\theta\) is a constant, in which case the boundary is a circle. QED.

Remark The proof is considered a probabilistic proof because the differential form \(\mathrm{d}p\mathrm{d}\theta\) is the measure (invariant under rigid motion) of a random line.

0 (be the first to like this)