Volatile Yard 挥洒自如 Write anything I want to write...

在这帖子里我分析了《欺诈游戏》漫画里出现的某个机率。最近我朋友看这漫画时问了我另一问题：第24话里出现的6%。我研究了一下，这问题也蛮有趣的。先说明一下：

• 以下的分析涉及到一点大学程度的数学，但高中程度的数学知识就应可读懂。
• 我在高中用中文学数学，上了大学却用英文，所以不太懂得运用某些专有名词。为避免張冠李戴用错专有名词，我以英文作分析。

This is a mathematical problem from a Japanese manga Liar Game.

问题 Problem

The game involves two players (S and F) and consists of several rounds. Each round is essentially a Bernoulli trial with probability p of success. Player S scores a point if the trial is success, otherwise Player F scores a point. The game ends when one player wins by first obtaining N points.

1. Find out the probability P that Player S will win the game, in terms of p and N.
2. Verify the claim in the comic that, if N=10 and p=1/3, Player S stands for a chance of only P≅6% to win the game.

解答 Solution

I don't like to eat meats since I was a kid as I really don't like their taste, while my family members are ok with them. I vomited a few times trying to take meats. Wonder if this is fated? I recall an interesting incident many years ago that might probably tell.

One day, my family went to buy satay to eat together at home. We hardly had satay at home in my hometown, and this is in fact the only time I also ate together as I can remember. (I just enjoy chewing the satay but not really its taste. Odd huh?) Something interesting then happened. Well, you normally will not find any bone from satay, unless the hawker had missed it accidentally. Now the incident:

We bought 20 satay sticks altogether. I took 4 sticks to eat, and I found real 'genuine' chicken bones (later examined by my family members too) in 3 out of that 4 sticks! While they didn't find any bone in other sticks! I swear that I did not choose them purposely as I didn't see the bones before I eat them. I treat it as a sign that I was fated to be discouraged from taking meats, ha... So now the mathematical questions:

• There are 20 satay sticks, and bones are found in 3 of them. What is the probability that, when you choose 4 of them randomly, you picked up the 3 sticks with bone?
• Given the same scenario, what is the probability if you choose only 3 of them randomly but happened to picked up all the 3 sticks with bone? (I might have picked those 3 too if I only choose 3 of them. Unfortunately this cannot be verified now.)

Check below for the solution. Think first if you can!

一直都喜欢看甲斐谷忍的《欺诈游戏》，每个游戏及计谋都设计得精采且严谨合理。在最近的第70话里，看到了一个数学概率问题，但作者没展示其算法就说其概率是约62%了。这其中的算法其实不太重要，毕竟故事里的计谋都设计得蛮有深度，而许多角色都是数学高手，这点小算法也真不太值得一提了。但我忍不住想验证这数字，并想想如何速算这概率。

先说明，算出这概率只需涉及高中程度的数学。没兴趣者请快离开，別留下无聊的留言！真有兴趣者，还可看看我对另一游戏的分析，并涉及到较深一点点的概率分析。

问题是这样的（应该无剧透吧！）：以上的12张扑克牌中有三张A。现从其任意抽出三张牌。请问抽中至少一张A牌的概率是多少？故事中的高手如何算得这么快?

你动了脑筋吗？ ☺ 我的分析如下。

Puzzle

I got a 'mathematical dream' last night, which involves an original mathematical puzzle. In the dream, I was in a book fair looking for some inexpensive second-hand books. Then, I saw a thick book with a title like "Adfferv...", well, which should not be a proper English word. The book covers a lot of things, and is written like "Sophie's World". The main character in the book somehow met a wise person, who taught him or her some good knowledge in literatures, physics, mathematics, etc. I browsed the book and saw a page with an eye-catching mathematical puzzle. It looked something like this:

The question is: "These people need to pay the money. But how much?" I somehow figured out the answer, and verified it with that listed at the back of the book. Are you able to figure it out? Read on for the solution.

Notes:

• From left to right: A half-burnt candle on a table; A fire hydrant [en.wikipedia.org] (also known as a fire plug or a johnny bump); Several people;
• Disclaimer: Don't try too hard! While the puzzle and the answer do make sense, they are not really rigorous and can be controversial. After all, all these things including the 'correct' answer are just from my dream!
• Hint: Trying to think in English may help here.

We normally need to learn some important trigonometric identities in high-school. For the identities among the trigonometric functions, some are 'manageable' and are not difficult to memorize. E.g.,

• Reciprocal Identities (E.g., $\sin \alpha = \frac{1}{\csc \alpha}$)
• Pythagorean Identities (E.g., $\sin^2 \alpha + \cos^2 \alpha = 1$)
• Quotient Identities (E.g., $\tan \alpha = \frac{\sin \alpha}{\cos \alpha}$)

But some are not easily to memorize. In particular, I used to get confused with the following identities:

• Sum-Difference Formulas
• Sum-to-Product Formulas
• Product-to-Sum Formulas

Why is it so? I analyzed them and made the following observations:

• The former formulas can be easily derived from the definitions of the trigonometric functions, normally involve only one angle, can obtain them by 'intuition' with the help of a right triangle, or some rather straightforward methods.
• The latter formulas involve two angles and there's a barrier to obtain the 'intuition' of manipulating them.

In particular, all the latter formulas can in fact be derived easily once you have $\sin (\alpha \pm \beta) = \sin \alpha \cos \beta \pm \cos \alpha \sin \beta$. Unfortunately, the identity makes some sense but not much. (Proving this is in fact tedious although not difficult.) I have not found any existing trick for helping us in memorizing them. Deriving all of them from this formula is feasible but not practical.

To solve the problem, I analyzed their patterns and 'invented' my own way. I came out with the following diagram:

    +   -
S  SC  CS
C  CC -SS
-> 2 /2 /2
<- /2

With this I have been able to memorize those formulas with ease. I can't guarantee that this method helps you, because the diagram can be as confusing as the formulas themselves! If you have a better way, please share! Read on if you are interested in my method.

1. Introductions

This is a rough guide on how to build or implement your own ephemeris program or library routines. There are some existing programs (and some of them are free) to do such a job. However, there are a few advantages if you build your own one.

• It's your thing. You have complete control of the licensing and the copyright of the program. You can also improve the programs anyhow you like.
• Good way to learn Spherical Astronomy. Of course, you need to like mathematics and astronomy. If you have no interest in these subjects at all, it's better to use an existing program or libraries routines for your purpose.
• Extend it for many other purposes. Since you are familiar with your program, you can easily extend it for many purposes such as (a) calculating the phase of the Moon; (b) predicting eclipses; (c) building your birth charts for many different traditions of astrology; (d) creating calendars (such as the Chinese calendar) that are based on astronomical events; (e) many other things.

While these sound interesting, you have to note that building your very own ephemeris is not for the faint of heart! If you are not familiar with spherical astronomy, be ready to learn a lot of concepts and technical terms related to the subject. As for implementation, expect to write

• a few hundred lines just for very basic set of features and low-precision calculations;
• a few thousand lines for more features and satisfactory accuracy;
• a few ten thousands lines for more complete features and high-precision calculations.

There are some easier ways to tackle this problem. For example, you can interpolate the positions of the planets from some existing ephemerides (such as DE405, DE406). Such an approach is definitely feasible and realistic. But here we focus more on performing the calculations "from scratch" which is useful in many cases. E.g., to calculate just the rough rising and setting time of the sun for a few centuries, it's better to stick to a simpler and less space-consuming low-precision calculation rather than to make use of the gigantic ephemerides.

Let's start.

2. Knowledge Required

Before starting your implementation, there are many concepts you need to understand and study. Here's a list of some important ones.

Mathematical Software Library Routines. In particular, you need to dial with a lot of trigonometric and logarithm calculations. Be very familiar with these to avoid making stupid mistakes. For example, a trigonometric function generally expect an angle expressed in radians, so don't use an angle expressed in degrees directly.

Concepts in Spherical Astronomy. You need to know a lot of thing specific to this subject. Knowing some popular concepts in astronomy like the big bang or the dark energy won't help you here, as we are dealing with locations here! Below is a list of some common concepts just to give you an idea what to expect. Note that the list is NOT exhaustive! The higher precision you want to calculate and implement, the more and the deeper of these concepts you need to understand.

• Time Tracking. TT/TDT (Terrestrial Time); ET (Ephemeris Time); ST (Sidereal Time); UTC (Coordinated Universal Time); UT (Universal Time); Delta-T; Julian day; Julian ephemeris day; Gregorian calendar; etc.
• Coordinate Systems. Horizontal coordinates (altitude, azimuth); Equatorial coordinates (right ascension, declination, equinox, solstice, hour-angle, transit, meridian); Ecliptic coordinates (longitude, latitude, obliquity); Galactic coordinates; Heliocentric; Geocentric; Topocentric; etc.
• Reference Frames. ICRF (International Celestial Reference Frame); FK5 (Fundamental Katalog 5); epoch; mean equator and equinox, etc.
• Orbital Elements. Perihelion; Aphelion; Perigee; Apogee; Eccentricity; Kepler's equation; Mean longitude; Mean anomaly; True anomaly; Equation of the center; etc.
• Miscellaneous. Astronomical Unit; Radius Vector; Aberration; Precession; Nutation; Parallax; Refraction; Twilight; Conjunction; Opposition; True/Geometric position; Mean position; Apparent position; etc.

Mathematics. To understand some basic calculations, you need only high-school mathematics. Be ready to deal with a lot of trigonometric functions and analytical geometry. But to deal with very high precision calculations, you may need to know more on calculus and astrophysics.

Where can you learn these concepts? Look for some good books or Internet resources related to this subject. I myself have learned a lot from [PDS] and various Internet resources. To learn spherical astronomy seriously, you can start with [WMS].

3. Guides for the Algorithms

3.1. Notes on Accuracy

Decide carefully the level of precision you need based on the purpose of your implementation. If you just want to use it to draw a simple sundial, then low-precision calculations are sufficient. But if you want to launch a rocket to the Moon or to visit your ET friends many light years away, then stick to the best algorithms known to human beings.

You may wonder, why don't we just go straight to the 'exact'/'perfect'-precision implementation? With such an implementation, we can then extend it anyhow we like. It's true, but there are some pragmatic issues. First, the state-of-the-art theories generally involve a lot of tedious calculations. E.g., ELP2000-82B is one of the best theories for calculating the position of the Moon. To calculate the position of the Moon in any given instant, you need to perform over 30 thousand trigonometric calculations. So... Second, storing such information takes space. You may not want to include such data especially for a portable device. Third, implementing the best solutions involves much more efforts in implementation and testing.

We will briefly mention the kind of applications you can do for calculations with different levels of precision. An interesting trade-off on the precision is to implement some calculations with different levels of precisions. Use only the one you need for your applications. E.g., to predict solar eclipse, you can first estimate the date and time a solar eclipse may occur by using low-precision (but faster) calculations. Then, use high-precision (but slower) algorithms to calculate the exact times related to the eclipse.

Last but not least, you need to know the maximum error introduced by each algorithm. With this, you can tell when the algorithm fails. For example, if an algorithm tells you that a new Moon starts from 11.59pm tonight, but its precision is low and may incur up to 10 minutes of maximum error in time, then you can't tell whether a new Moon starts today or tomorrow. Such a case may not affect you if you want to observe other stars on a new Moon night, but it can be extremely important if you want to calculate an astronomical lunar calendar. To resolve such a case, you need to resort to high-precision calculations.

3.2. Low-Precision Algorithms

To find out the rough locations of the planets at night, to design a normal sundial, to include a cute moon phase indicator in your PDA, to design a compass based on the sun and moon positions, or to know the rough rising and setting time of the sun and the moon, low-precision calculations are sufficient.

There are a few good places to learn such calculations. The book [PDS] covers a lot of useful concepts and low-precision algorithms. The following websites contain good resources too: Approximate astronomical positions, How to compute planetary positions.

With this level of precession, you normally don't need to distinguish between the TT (Terrestrial Time) and UTC (Coordinated Universal Time), among the various reference frames, and you need only simple linear interpolation.

3.3. High-Precision Algorithms

To calculate an accurate birth chart for the modern western astrology or chinese astrology, to calculate lunar and solar eclipses with satisfactory results, or to calculate a calendar that is based on astronomical events, you may need high-precision algorithms. In particular, knowing the maximum possible error that can incur could be critical for some applications.

A good book that includes such algorithms is [JM]. The book introduces various important concepts. The calculations of the planet positions are based on an bridged version of the VSOP87 theory, which is one of the best planetary theories we have. While the calculations of the moon position is based on an abridged version of the famous ELP 2000/82 lunar solution.

You need to distinguish among the time systems here. Don't get confused between TT and UTC. You need to implement the routines to convert between them. A proper interpolation may be necessary to obtain good conversion results. You also need to distinguish among the true, mean, and apparent positions. Be careful to deal with nutation, precession, aberration, parallax, refraction, etc.; and convert among the different reference frames properly.

3.4. "Platinum" Algorithms

If the calculations above don't suit your purpose because you want to design a bullet-proof astrological birth chart, to calculate astronomical calendars, to predict eclipses to an accuracy in the order of milliseconds, or to navigate your spacecraft to another galaxy, then you need to study more and implement very high-precision algorithms.

You can find a lot of great resources from the wonderful Internet. Some useful web sites are listed here.

• JPL Solar System Dynamics. A lot of great information including very high-precision ephemerides (DE405/DE406, probably the most precise ephemerides on Earth!), an online HORIZONS ephemeride system, etc.
• Institut de mecanique celeste et de calcul des ephemerides. Ephemeris generator, resources on the complete VSOP87 and ELP 2000-82B theories.
• International Earth Rotation & Reference Systems Service. Stuffs related to the Earth rotation such as the Precession-Nutation Model, Delta-T, announcements of leap seconds, etc.
• International Terrestrial Reference Frame.

There are more things you need to take care of. A cubic spline interpolation for Delta-T (= TT - UT1) would be great. You may also want to learn more about astrodynamics and numerical integration.

4. References

[JM] Jean Meeus. Astronomical Algorithms. 2nd Edition. December 1998. ISBN 0-943-39661-1.
[PDS] Peter Duffett-Smith. Practical Astronomy with Your Calculator. Third Edition. March 1989. ISBN 0-521-33699-7.
[WMS] W. M. Smart. Textbook on Spherical Astronomy. 6th Edition (Revised by G.M. Green). 1977. ISBN 0-521-21516-1/0-521-29180-1.
Also take a look at the links I've bookmarked under the Astronomy category on this site.