Ben 帮助我练习钢琴

我这一阵子右手食指很痛,连键盘都不太能够敲得了,更不用说弹琴了。自己正在学习的曲子,只能反复练习左手的和声,但是没有办法练习右手旋律,更不用说把两个部分和起来了。

只练习和声部分总是有些枯燥,但是自己也没有什么好办法。有趣的是这天晚上 Yetao 跑过来要帮助我弹右手部分,真是一个很棒的主意。后来Ben也跑过来帮忙,Ben右手的旋律弹的像模像样,和我配合在一起听上去很不错,特别是弹到自己从来没有合起来过的部分,旋律与和声第一次响起来的时候我真是有些感动。孩子们帮了我一个大忙,真好。

Citrus Leafminer

后院的橘子树经过我的精心照料,生长的郁郁葱葱,即使是在夏天,也发出了很多嫩绿的新叶,看得我很高兴。可是几周之前我吃惊的发现,大部分新长出来的叶子上都有了一种奇怪的图案,不知道是病毒还是细菌,很多新叶就这样扭曲、枯萎和脱落了,让我大为心痛。我还把受到侵害的叶子拿给太太看,她也是大吃一惊,不知道是何方邪恶生物,可以制造出这样可怕的犯罪场景。

看着越来越多的新叶受到侵害,我终于下定决心研究一下这到底是怎么回事。我把 “Orange Tree Disease” 放到Google图片里面搜索一下,结果很快就找到了很多讲述这个问题的网站,原来这是一种叫做 Citrus Leafminer 的小虫子,专门在橘子树的新叶子里面打洞,最后变成成虫飞走了。 令人感到欣慰的是,文章说这种小虫子造成的损害很小,绝大部分时候都不需要任何处理:因为它只能侵害新叶,老叶子比较坚固,不受影响,所以只有你的树是新栽种的情况下才需要操心,否则没有什么大不了的。文章建议不要使用杀虫剂,也不要剪去受损的树叶(因为这不是由细菌或者病毒引起,不会传染)。文章甚至建议为了避免这种害虫过度繁殖,应该避免夏天给橘子树上太多肥料,这样树就不会发出太多新叶而招致害虫。

文章的作者很达观,对于这种虫害基本上采用放任自流的观点。我看完文章以后也放心多了。 🙂

事实与观点

说来惭愧,虽然修炼了这么多年,但是听到别人对于自己的负面评价,还是难以淡定,特别是如果这些评价还是基于事实的话,那更是会让我长久挂怀,比如有人说我是一个“Self Worker”,暗示我没有领导力;还有人说我“就是太喜欢写程序”,暗示不能抓住项目重点,都是我常常想起来的例子。

最近渐渐意识到,对于别人的评价,还是要分清楚事实和观点。如果评价不是基于事实,那就根本没有必要理会。即使说的是事实,对方的观点你是否需要接受也是大可商榷的事情。我自己确实很喜欢写程序,写出来漂亮的程序自己也很高兴,这一点其实没有什么不好,没有人能够把所有的事情做到面面俱到,在自己喜欢而且擅长的事情上深钻是理所应当的,所以上面这个“就是太喜欢写程序”的评价事实正确,但是观点不一定就是正确的呀。 就像我最近有时候跟太太抱怨,太太就会笑眯眯的说,哎呀我就是这个样子,请你多多包涵啦,这种懂得自嘲的态度不是更健康吗?

围棋实战计算题目

我一直想要把自己围棋实战的某些局面提取出来作为死活题目来锻炼自己的计算能力,但是具体怎么做一直没有满意的方案。 以前用MultiGo 的 PDF 打印功能,然后拷贝到 Kindle 上看。一切都很好,就是两点:MultiGo 是个 Windows 程序,每次需要用Windows 电脑才能运行;MultiGo 的打印程序处理提子有些问题,打印出来的图形上被提掉的子还在那里,图像看上去有一些乱。最近我和老爷爷又下了很多棋,打算有空把关键局面仔细研究一下,把这些局面打印出来的念头就又冒了出来。不料这个简单的事情也遇到了很多小麻烦,除了上面提到的两个MultiGo的问题之外,还有很多小问题:

  • SGF2DG 倒是功能很强大,但是生成的PDF文件总是有一大块是留给注释的,跟我的要求不符合。实际用起来屏幕上空着一大块不好看。
  • 流行的 Sabaki 干脆就没有提供打印功能,而屏幕截图生成的PDF实际上是个图形, Kindle上显示效果很差。

反复了好几次,最终终于形成了自己的方案:

  • 不使用 Kindle,就直接打印在纸上好了。
  • Sabaki 的显示很漂亮,就算是打印成灰度图也不错,就用它截图打印了。

打印出来一大本围棋题目,放在洗手间里,方便的时候拿着看看,比在网上跟人浪战快棋好多了,希望能够坚持下去吧。

排列组合的新思路

排列就是从一个Population 中有序的采样(Sample),组合就是从一个Population中 无序的采样。无论哪种采样,基本的排列组合公式 P_n^r{n \choose r} 都假定Population 中的每一个对象是可以区分的。但是对于Population 中存在不可区分对象的情况(比如 Sampling with Replacement),我们就需要新的思路。我自己对于这个关键的区别一直没有很深刻的理解,直到最近读 William Feller 老爷爷的概率书,才有了一些进展,下面来说一说。

假定一个长度为 n 的二进制字符串,其中有r (0 \le r \le n)个1的字符串有多少?

这个问题中,Population就是 0 和 1,但是它们可以重复出现在最终的采样中,因此简单的排列组合思路并不适用。解决这个问题有两种传统的思路:

  • 思路一:假定我们在这 n 个字符串中 挑选 r 个 1,然后剩下的全部是0,那么可供挑选的总共方案是:

(1)   \begin{equation*} {n \choose r} = \dfrac{n!}{r! \cdot (n-r)!} \end{equation*}

  • 思路二:假定所有的0和1都是可以区分的,那么所有总共可能的方案就是 n! 种,其中有 r 个1 和 n-r 个0。如果这r个1互相可以区分,那么它们总共有 r!的不同的排列方式,相应的对于这些可以区分的0我们也有 (n-r)!种不同的排列方式。现在这些0和1都变成不可区分的了,所以这些不同的排列方式就变成了一种,那么长度为 n 的二进制字符串,其中有r (0 \le r \le n)个1的字符串就有:

(2)   \begin{equation*} \dfrac{n!}{r! \cdot (n-r)!} = { n \choose r} \end{equation*}

这正好就是思路一中的组合数公式,因此两种思路的结果是一样的。 上面的第二种思路讲述起来要比第一种长很多,但是我反而觉得更容易理解,其主要原因是因为它和组合数的公式推导的思路本身就是一致的。组合基本问题:从 n 个可以互相区分的对象中,取出r个对象的不同组合(也就是不考虑这r个对象的顺序)有多少?很明显如果我们考虑这r个对象的顺序,不同的顺序代表不同的组合的话,那么我们一共有:

(3)   \begin{equation*} n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-r+1) \end{equation*}

种不同的方案,这是一个基本的排列问题。现在考虑 r 个不同的对象有多少种不同的排列方式,很明显这也是个基本的排列问题,答案是 r! 种。现在我们看到,如果相同的r个对象的不同排列方式只能算作同一种组合的话,那么 3 对于所有可能的组合就高估了 r! 倍,因此从 n 个可以互相区分的对象中,取出r个对象的不同组合(也就是不考虑这r个对象的顺序)就有:

(4)   \begin{equation*} \dfrac{n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-r+1)}{r!} = \dfrac{n!}{r! \cdot (n-r)!} = { n \choose r} \end{equation*}

沿着这个新思路,我们可以解决一些新的排列组合题目,下面是一些例子。

假定有n面不同的旗帜,要挂在 r 个旗杆上,一共有多少悬挂的方法?

很明显第一面旗帜有 r 种悬挂的方法,注意到有旗帜的那个旗杆现在如果我们要在上面再挂新的旗帜的话,有上面和下面两种选择,所以第二面旗帜有 r+1种悬挂的方法,以此类推,第三面旗帜有 r+2中悬挂的方法,而所有总共的悬挂方法有:

(5)   \begin{equation*} r \cdot (r+1) \cdot (r+2) \cdot ... \cdot (r+n-1) \end{equation*}

现在假定这 n 面旗帜都是一样的(比方说都是普通的红旗),那么考虑到n 个不同的旗帜一共有 n! 种排列方法,现在这些旗帜都变成一样的了,所以上式的估计就比实际高出了 n! 倍,因此当这 n 面旗帜都是一样的时候总共的悬挂方法就有:

(6)   \begin{equation*} \dfrac{r \cdot (r+1) \cdot (r+2) \cdot ... \cdot (r+n-1)}{n!} \end{equation*}

顺便提一句,帖子 组合数学中的分配问题(二):不能区分的对象和可以区分的组中问到的 18 个相同的文件夹在4个不同的人之间分配,每个人接收到的文件夹数量不做限制的话,就可以利用上式计算:

(7)   \begin{equation*} \dfrac{4 \times 5 \times 6 \times ... \times 21}{18!} = 1330 \end{equation*}

最后,如果我们有两种旗帜:p面红旗和q面蓝旗,很明显我们有p+q=n,那么把它们挂到r 个旗杆上的方法,按照上面的思路很容易就得到了:

(8)   \begin{equation*} \dfrac{r \cdot (r+1) \cdot (r+2) \cdot ... \cdot (r+n-1)}{p! \cdot q!} \end{equation*}

William Feller 老爷爷的思路还真是很强大。

从电子灭蚊灯到刺激消费和拉动经济

家里有一个电子灭蚊灯,花了 $60 在 Amazon 上买的。挂在后院里,一到夏天晚上,总是啪啪作响,替我们消灭了很多小蚊虫。Ben 第一次看见这个东西消灭小虫子的时候吓坏了,一下子躲到妈妈的怀里。后来过来很久我问起他这件事情,他还是记忆犹新,跟我讲小飞虫的眼睛一下子变得通红,整个身子都着了火,还发出啪啪的声音和冒出烟味,What the hack! 孩子的眼里看世界还真是不一样。 🙂

前两天Yetao过生日,很多小朋友到家里来玩,结果有个小朋友把灭蚊灯一下子从架子上撞下来掉到地上摔得七零八落,盖子都掉了。我有点心疼,毕竟买一个新的还是挺贵的,但是我试着装了几次都没有装好。正好今天下午没有什么事情,我就拿来工具仔细研究,看看这个东西是不是还能修好。一来二去,结果还真的修好了,插上电源灯就又发出蓝莹莹的光,让我很高兴。废物利用的感觉真是好。

想起上学的时候和宿舍同学有过一次讨论,他跟我讲需求是经济发展的动力,只有大家不停的更新换代,生产过程和经济循环才能持续,所以节俭不是一个好的习惯,应该全力消费才对,总而言之,就是要刺激消费,拉动经济。我当时对他的这套理论大吃一惊,因为从穷苦日子过来,总觉得节俭是一项巨大的美德,从来没有想过还可以从这个角度考虑问题。这么多年我常常回想起那一番讨论,现在也渐渐明白其中的漏洞所在:根本上来讲,地球是有限的,人类的生产生活已经给环境制造了巨大的压力,消费总有一个上限;通过刺激人的欲望来增加经济的总量,恐怕从人与自然和谐相处以及可持续发展的角度来讲,长远来看很难说是一件好事。 从这一点上来讲,我花点时间修好了摔坏的灭蚊灯,而不是简单的把它扔进垃圾筐然后买一个新的,也算是践行了自己的信念吧。

家里有两个男孩的概率是多大?

这道概率的题目我以前在知乎上看见人讨论过,当时的背景是量子力学中概率问题。最近又在 William Feller 老爷爷的书中看到了这道题目。经典的概率已经很难了,量子力学中的概率就更是违反直觉。但是无论如何,我还是反对很多人故弄玄虚,把本来很清楚的问题搞得越来越糊涂,相比之下,老爷爷的书讲得很清楚。下面讲一讲这道问题和我的理解。

考虑所有有两个孩子的家庭,假定我们已经知道家里至少有一个男孩,那么这个家里有两个男孩的概率是多大?

如果每个孩子是男是女的概率相等,那么两个孩子的家庭一共有以下四种可能的基本情况:

  • 男孩,男孩
  • 男孩,女孩
  • 女孩,男孩
  • 女孩,女孩

这四种基本情况的概率是相等的,都是 0.25,也就是说家里有两个男孩的概率是0.25。现在我们给出了条件:家里至少有一个男孩。这个条件过滤掉了两个女孩这种基本情况,只剩下三种基本情况,因此家里有两个男孩的概率变为\dfrac{1}{3}。用概率论的术语来描述的话,两个孩子都是男孩这个事件(A)的概率是:

(1)   \begin{equation*} P(A) = 0.25 \end{equation*}

家里至少有一个男孩这句话给出了一个条件(Hypothesis,H),这个条件(或者假设)发生的概率是:

(2)   \begin{equation*} P(H) = 0.75 \end{equation*}

题目所问的问题实际上就是一个条件概率:在家里至少有一个男孩这个条件(H)之下,家里有两个男孩的这个事件(A)发生的概率是多少?这个概率可以用条件概率公式表达如下:

(3)   \begin{equation*} P(A|H) = \dfrac{P(AH)}{P(H)} \end{equation*}

顺便说一下,对于条件概率公式,我觉得下面的表达方式更自然一些:

(4)   \begin{equation*} P(AH) = P(H) \cdot P(A|H) \end{equation*}

我个人常常把它读作:事件A和H同时发生的概率,就是事件H发生的概率 乘以 当事件H发生时事件A将会发生的条件概率。这样的表达式也很容易拓展到多个事件的情况,比如下面:

(5)   \begin{equation*} P(ABC) = P(C) \cdot P(B|C) \cdot P(A|BC) \end{equation*}

现在回到我们的条件概率公式 (3)。 P(H) 我们已经知道是 0.75,但是 P(AH) 是多少呢?考虑事件 AH的具体含义,它表示“两个孩子都是男孩”而且“至少有一个男孩”这两个事件的交集(即同时发生)。参考上面枚举所有情况,很明显这种事件在所有四个事件中只发生了一次,因此 P(AH) = 0.25。把这个数据代入上式,我们就可以计算得出在家里至少有一个男孩这个条件(H)之下,家里有两个男孩的这个事件(A)发生的概率是:

(6)   \begin{equation*} P(A|H) = \dfrac{P(AH)}{P(H)} = \dfrac{0.25}{0.75} = \dfrac{1}{3} \end{equation*}

和我们直觉推理的结果一致。

下面有意思的事情来了,前面的问题可以被改写为下面的形式:假定你有一个朋友,你知道她有两个小孩,其中有一个是男孩。你可以猜测她的家里两个孩子都是男孩的概率是\dfrac{1}{3},这个结果正如我们前面分析的一样。下面假定有一天,你在公园散步 ,遇到你的这位朋友带着一位男孩也在散步,而这个男孩正是你这位朋友的小孩。现在我们要问一个新问题,你这位朋友家里两个孩子都是男孩的概率是多少?

这个新问题可以按照下面的简单思路来回答:你没有看见的那个孩子是男是女的概率是相等的,都是0.5,如果那个没有看见的孩子是男孩,你的朋友就有两个男孩,如果那个没有看见的孩子是女孩,你的朋友就有一男一女。所以对于这个新问题,你这位朋友家里两个孩子都是男孩的概率是0.5。

很明显,这个新问题的答案和我们原来问题的答案不一样,一个是0.5,一个是\dfrac{1}{3}。为什么会是这样子呢?会不会是某一个答案搞错了?我们原来已经知道朋友家里有一个男孩,现在我们只是实际看到了这个男孩。难道看一眼这个男孩确认一下我们已经知道的事实就会导致概率的变化吗?

上面的问题确实很令人迷惑,这也突出体现了概率论这门学科的众多违反直觉之处。实际上,这个新问题和我们前面讨论的问题确实是不同的问题,就像著名的 Monty Hall Problem 一样,某些被呈现的事件实际上被Over Represented。

原来的问题可以看做采样基本对象是家庭:在所有有两个孩子的家庭中,我们把至少有一个男孩的家庭抽取出来排成一队,队列中的每一个项目都是一个家庭;现在我们从这个队列中随机抽取一个家庭,那么抽到有两个男孩的家庭的概率是 \dfrac{1}{3}

而新问题采样的基本对象是男孩:对于所有的有两个孩子的家庭,把所有的男孩都排成一队,队列中的每一个项目都是一个男孩;下来我们从队伍中随机抽取一个男孩,问他来自于两个男孩的家庭的概率是多少。这种情况下他来自于有两个男孩的家庭的概率是0.5。这是因为两个男孩的家庭男孩比其他家庭要多,所以在这个队列中抽到来自两个男孩家庭的男孩的概率也要比其他家庭大。不易察觉的是,对于两个女孩的家庭,由于这些家庭根本没有办法参与到这个队列中来,如果我们加上限制条件,参加队列的家庭是那些至少有一个男孩的家庭(Hypothesis, H),那么抽到来自两个男孩家庭的男孩的概率依然是0.5。这个过程参见下面的图片。


现在我们言归正传,那么前面那个朋友家庭有两个男孩的概率到底是0.5 还是\dfrac{1}{3} 呢?对于这个问题,我的回答是概率只能应用于统计,而不能应用于个体,所以这个问题没有意义呀。 🙁

字母表(Alphabet)的长度为m,单词(Word)的长度为n,字母表中的每一个字母都用到的单词有多少?

字母表(Alphabet)的长度为m,单词(Word)的长度为n,字母表中的每一个字母都用到的单词有多少?这个问题又是一个可以通过递归分析来解决的组合数学题目。

我们先假定这样的单词总数是 X(n, m)。当字母表的长度为m,单词的长度为n的时候,所有可能的单词总数是:

(1)   \begin{equation*} m^n \end{equation*}

在上面这么多单词中,只含有一个字母的单词总数是:

(2)   \begin{equation*} m \end{equation*}

只含有两个字母,并且这两个字母都用到了的单词总数是多少呢?首先从m个字母中选取两个字母的组合数目是:

(3)   \begin{equation*} C_{m}^2 \end{equation*}

而这两个字母组成的长度为 n ,而且这两个字母都用到了的单词,按照我们上面的递归定义则是 X(n, 2)。因为每个组合中的字母都不一样,而每个单词用到了所有的字母,所以所有这些组合代表的字母表形成的单词互相既不重复,又涵盖了所有长度为n而且用到了两个不同字母的单词。综上所述,所有两字母而且这两个字母都被用到的单词总数是:

(4)   \begin{equation*} C_{m}^2 \cdot X(n, 2) \end{equation*}

以此类推,所有三个字母而且这三个字母都被用到的单词总数是:

(5)   \begin{equation*} C_{m}^3 \cdot X(n, 3) \end{equation*}

这样可以一直推到 m-1。另外我们注意到在单词表只有一个字母的情况下,用到这个字母的长度为 n 的单词为 1,也就是 X(n, 1) = 1。那么我们把上面讨论过的只含有一个字母的单词总数可以表示为:

(6)   \begin{equation*} m = C_{m}^1 \cdot X(n, 1) \end{equation*}

我们从所有可能的 m^n 的单词中去除掉那些只有一个字母的单词、二个字母而且每个字母都被用到的单词、三个字母而且每个字母都被用到的单词、…、一直到m-1 个字母而且每个字母都被用到的单词,就得到了 m 个字母都被用到的单词,也就是:

(7)   \begin{equation*} \begin{split} X(n, m) &= m^n \\ &- C_{m}^1 \cdot X(n, 1) \\ &- C_{m}^2 \cdot X(n, 2) \\ &- ... \\ &- C_{m}^{m-1} \cdot X(n, m-1) \end{split} \end{equation*}

上面就是 X(n, m) 的一个递归定义,具体的实现在这里

from math import factorial

# combination
def C(n,m):
  return factorial(n) / (factorial(m) * factorial(n-m))


# Cache table for X, see below.
X_cache = {}

# A vocabulary of size 'm', a sample of size 'n' with replacement,
# How many possible results with all the 'm' items in it.
def X(n, m):
  if (n, m) in X_cache:
    return X_cache[(n, m)]

  if m == 1:
    result = 1
  elif n < m:
    result = 0
  else:
    # Start with total.
    result = int(m ** n)

    for i in range(1, m):
      # Pick a sub-vocabulary with 'i' items, calculate how many
      # samples can be made by using all of them, remove it from total. 
      result = result - C(m, i) * X (n, i)

  X_cache[(n, m)] = result
  return result


def CallX(n, m):
  result = X(n, m)
  print(f'n={n}, m={m}: {int(result)}')

CallX(25, 5)
print(f'Total: {5**25}')
print(X(25, 5) / 5**25)

在William Feller 的老爷爷原题中,字母表中有5个字母,单词的长度是25,问所有字母的出现的概率是多大,按照上面的公式计算我们有:

(8)   \begin{equation*} \dfrac{X(25, 5)}{5^{25}} = \dfrac{292402196893290112}{298023223876953125} = 98.1 \% \end{equation*}

而当字母表中有3个字母,单词的长度是3的时候,所有字母都出现的概率则是:

(9)   \begin{equation*} \dfrac{X(3, 3)}{3^3} = \dfrac{6}{27} = 22.2 \% \end{equation*}

看来单词一变长,基本上所有的字母也就都包括了。 🙂

An informal (picture based) proof of De Morgan’s laws

很多组合数学的问题正向考虑比较困难,反向考虑就容易很多。这种时候,Morgan 定律就排上了用场,下面是该定律的形象化的证明和一个具体应用的例子。

假定有两个集合 A 和 B,Morgan 定律把它们的交集通过补集和并集操作表示如下:

(1)   \begin{equation*} A \bigcap B = \sim ((\sim A)  \bigcup (\sim B)) \end{equation*}

这个定律一个形象化的证明如下:

下面是 Morgan 定律具体应用的例子,假定我们有一个 k 位的数字,每一位上可以是0-9这10个数字,那么既有0又有1的数字一共有多少?

所有总共可能的数字是 (World):

(2)   \begin{equation*} 10^k \end{equation*}

其中没有0的数字 (定义为集合 \sim A) :

(3)   \begin{equation*} 9^k \end{equation*}

其中没有1的数字 (定义为集合 \sim B) :

(4)   \begin{equation*} 9^k \end{equation*}

所有有0的数字(定义为集合A):

(5)   \begin{equation*} 10^k - 9^k \end{equation*}

所有有1的数字(定义为集合B):

(6)   \begin{equation*} 10^k - 9^k \end{equation*}

那么根据 Morgan 定律,又有0又有1的数字就是:

(7)   \begin{equation*} A \bigcap B = \sim ((\sim A)  \bigcup (\sim B)) \end{equation*}

我们已经知道 (\sim A) = 9^k , (\sim B) = 9^k ,关键是 (\sim A)  \bigcup (\sim B) 如何计算,可以看出,既没有0也没有1的数字是:

(8)   \begin{equation*} (\sim A)  \bigcap (\sim B) = 8^k \end{equation*}

所以我们有:

(9)   \begin{equation*} (\sim A)  \bigcup (\sim B) = (\sim A) + (\sim B) - (\sim A)  \bigcap (\sim B) = 9^k + 9^k - 8^k \end{equation*}

最后对于又有0又有1的数字就是:

(10)   \begin{equation*} A \bigcap B = \sim ((\sim A)  \bigcup (\sim B)) = 10^k - (9^k + 9^k - 8^k) \end{equation*}

对于 k=2 的情况,又有0又有1的数字只有两个:0110,按照上面的公式算一下:

(11)   \begin{equation*} 10^2 - (9^2 + 9^2 - 8^2) = 2 \end{equation*}

Feller 老爷爷后面的东西还是很靠谱呀。 🙂