Deniz Yuret's Math Problems

This is a list of elementary problems I like for one reason or another from various branches of mathematics. I cited the people I heard the problems from, they are not necessarily the originators. The unsolved flag just means that the problem is yet unsolved by me. Send me a solution if you find one. You can send me any interesting problems you find by adding a comment to this post. Also check out my other math posts, especially probability twisters, unsolved elementary problems, and links to other math sites. Last update: April 16, 2022.

1. (Alkan) There are four cities at the corners of a unit square. You are tasked with connecting them to each other using roads so that one can get from any of the four cities to any other. What is the shortest length of road you can do this with? (Hint: the answer is less than 2 sqrt(2)).
2. (Kleinberg and Tardos) Alice and Bob have n numbers each for a total of 2n distinct numbers. Each can tell you the k'th smallest number they have but cannot see each other's numbers. What is the minimum number of queries you can ask to find the median of these 2n numbers?
3. (Quanta Magazine) Show that if Alice tosses a fair coin until she sees a head followed by a tail, and Bob tosses a coin until he sees two heads in a row, then on average, Alice will require four tosses while Bob will require six tosses.
4. (Cihan Baran) If we sample k times with replacement from the set {1, 2, ..., n} (all members picked with equal probability) what is the probability that at least one member will not be picked?
5. (Bertsekas and Tsitsiklis) Suppose that n people throw their hats in a box and then each picks one hat at random. (Each hat can be picked by only one person, and each assignment of hats to persons is equally likely.) What is the expected value of X, the number of people that get back their own hat?
6. (Paul Lockhart) Must there always be two people at a party who have the same number of friends there?
7. (Volkan Cirik) Consider a game played with an array of 2n random numbers. The first player can pick the number at either end of the array, the second player can pick from either end of the remaining numbers etc. The players take turns picking numbers from either end until no more numbers remain. Whoever has the highest total wins. Show that the first player can always win or draw.
8. (Ahmed Roman) Nathan and Abi are playing a game. Abi always goes first. The players take turns changing a positive integer to a smaller one and then passing the smaller number back to their opponent. On each move, a player may either subtract one from the integer or halve it, rounding down if necessary. Thus, from 28 the legal moves are to 27 or to 14; from 27, the legal moves are to 26 or to 13. The game ends when the integer reaches 0. The player who makes the last move wins. For example, if the starting integer is 15, Abi might move to 7, Nathan to 6, Abi to 3, Nathan to 2, Abi to 1, and now Nathan moves to 0 and wins. (However, in this sample game Abi could have played better!)
   1. Assuming both Nathan and Abi play according to the best possible strategy, who will win if the starting integer is 1000? 2000? Prove your answer.
   2. As you might expect, for some starting integers Abi will win and for others Nathan will win. If we pick a starting integer at random from all the integers from 1 to n inclusive, we can consider the probability of Nathan winning. This probability will fluctuate as n increases, but what is its limit as n tends to infinity? Prove your answer.
9. (Serdar Tasiran) We have an n boxes, k of them have a ball in them (k<=n), the others are empty. We start opening the boxes in a random order and stop when we find a ball. What is the expected number of boxes we will open?
10. (Ertem Esiner) Two mathematicians meet an old friend who has two kids and ask her what their ages are. The mother writes the sum of the two ages on a piece of paper and gives it to the first mathematician, and gives the product of the two ages to the second mathematician. The mathematicians think for a minute and claim the information is not sufficient. The woman says "think again". At that moment the mathematician with the product figures out the answer. How old are the two kids?
11. (Ertem Esiner) Five pirates are trying to divide up 1000 gold pieces among themselves. They decide to take turns making offers. An offer by a pirate is accepted if at least half of the other pirates agree to it. Otherwise the pirate making the offer is killed, and the next one makes an offer. Each pirate is greedy, but none wants to die. If you are the first pirate, what offer do you make?
12. (Drake) A professor announces that there will be surprise exam the following week, specifically that the students will not know what day the exam is going to take place. The students reason that the exam cannot take place on Friday, because by Thursday night they would know what day the exam is going to take place. If the exam cannot be on Friday it cannot be on Thursday either, because they would know by Wednesday night and so on. They finally decide the exam cannot take place and forget to study. The professor gives the exam on Wednesday to everybody's surprise. What went wrong?
13. (Mackay) Fred rolls an unbiased six-sided die once per second, noting the occasions when the outcome is a six.
    1. What is the mean number of rolls from one six to the next six?
    2. Between two rolls, the clock strikes one. What is the mean number of rolls until the next six?
    3. Now think back before the clock struck. What is the mean number of rolls, going back in time, until the most recent six?
    4. What is the mean number of rolls from the six before the clock struck to the next six?
    5. Is your first answer different from your last answer? Explain.
14. (Deniz) You have two independent random variables between 0 and 1. How do you decide which one is more likely to be larger than the other?
15. (Deniz) You have two arbitrary random variables between 0 and 1. How do you decide if they are independent or not looking at their joint pdf density plot?
16. (Dennis Eriksson) Find all solutions to the diophantine equation: 1+2+3+...+n=m^2, where n and m are positive integers.
17. (Feyz) You have a deck of n cards numbered from 1 to n. dealt and shuffled randomly. What is the probability that none of the i-th card is on the i-th position?
18. (Sonny) Prove that there is a natural number n, for which 2^n starts with the numbers 3141592, i.e., show that there is a number of the form 3141592.... which is a power of 2 (in base 10 representation).
19. (Alkan) Let n, k be integers greater than 1.
    1. Show that 1/1 + 1/2 + 1/3 +...+ 1/n cannot be an integer.
    2. Show that 1/k + 1/(k+1) + ... + 1/(k+n) cannot be an integer.
20. (Will,Minsky) These problems have something in common:
    1. A monk leaves to ascend to the temple on top of a mountain at 9am and arrives at 5pm. The next day he leaves the temple at 9am and arrives back at the foot of the mountain at 5pm. Prove that there is a point in time where he was at the same location on the path at the same time.
    2. Prove that on a 2D earth, there exists a diameter such that the temperature at the endpoints is equal.
    3. Prove that on a 3D earth, there exists a diameter such that the temperature and humidity of the endpoints are equal.
    4. Does every convex closed curve in the plane contain all four vertices of some square?
21. (Ben) Two nice algorithm questions: Given a shuffled array of numbers from 1 to 10,000, find the three that are missing in one pass. Given an array of positive and negative integers, find the subarray with the highest sum in linear time.
22. (Winston) Four people want to pass a bridge dark at night. They can walk the bridge in 1, 2, 9, and 10 minutes respectively. The bridge can carry at most two people at a time. There is a single flash-light, and they need the flash-light to walk on the bridge. What is the shortest time for all four to pass across? (This was apparently a popular Microsoft interview question).
23. (Beril) You have a glass of tea and a glass of milk. You take a spoonfull of milk, mix it with the tea. Then you take a spoonfull of this mixture and mix it with the milk. Is there more milk in the tea or more tea in the milk at the end?
24. (Mine) Construct a square from: (a) Three identical squares, (b) Any two squares, (c) A rectangle. (d) Divide a square into any given two squares with the same total area. (e) Divide a circle into 6, 7, 8, and 10 equal pie-slices.
25. (IMO practice) m+n people are standing on a movie line. m people have 5 dollar bills, n people have 10 dollar bills. The movie is 5 dollars. The cashier opens with no money. It will close if it does not have enough change to give one person. How many possible lines are there that will get through without closing the cashier? Note: (Deniz, Mar 10, 1998) I just discovered that this problem is equivalent to finding the number of full binary trees with m leaves when n=m-1. A full binary tree is a tree where each node has 0 or 2 children. The number of binary trees is equivalent to the number of shift-reduce sequences that parse them. For such a sequence to be valid the number of shifts need to always be ahead of the number of reduces, which turns this into our movie problem. The binary tree problem can also be solved using a generating function and the relation b[n] = sum[k=1..n-1](b[k] b[n-k]). The movie problem can be solved by using random walks and the reflection principle. The two solutions seem to give different answers but they turn out to be equivalent. This constitutes an indirect proof of the following combinatorial identity: (2n-1)!! = 2n!/(n! 2^n). Everything is related to everything else in math :-)
26. (Oguz) Find a function f on real numbers such that f(f(x)) = -x.
27. (Boris) You meet many women in your life. After meeting each one, you decide how good she is and whether you want to marry her. If you decide to marry her, you lose your chance with future candidates. If you decide to move on, you lose your chance with her. Assuming you will meet at most n women, find the optimum strategy for marrying the best bride. (The Azeri mathematician Gussein-Zade is apparently the first one to solve this problem.)
28. (Alkan) A small rectangle is cut out of a large rectangle. Find a line that divides the remaining figure into two equal areas using an unmarked ruler.
29. (IMO) Let A be a set of ten two-digit integers. Prove that one can always find two subsets of A with the same sum.
30. (IMO) 17 people correspond with each other. Each pair discusses one of three possible topics. Prove that there are three people that discuss the same topic with each other.
31. (Alkan) Five couples meet in a party. Everyone starts shaking hands with everyone else except their partners. At some point the host stops them and asks how many handshakes each had. Everyone gives a different number. How many hands did the host's wife shake?
32. (IMO-75/4) When 4444 ⁴⁴⁴⁴ is written in decimal notation, the sum of its digits is A. Let B be the sum of the digits of A. Find the sum of the digits of B. (A and B are written in decimal notation.)
33. (Murat Fadiloglu) What is the probability of two randomly selected integers being mutually prime?
34. (Alkan) An old lady buys a plane ticket to visit her son. She goes to the airport and people let her board first. Since she can't read her seat number, she sits on a random seat. Rest of the passengers sit on their own seats, unless it is occupied in which case they randomly choose one of the emtpy seats. What is the probability that the last passenger will sit on his own seat?
35. (Alkan) sqrt(1 + 2*sqrt(1 + 3*sqrt(1 + 4*sqrt(1 + 5*sqrt(1 + ... ))...) = ?
36. (Rota) Given a sequence of (n ² + 1) distinct integers, show that it is possible to find a sequence of (n+1) entries which is increasing or decreasing.
37. (Minkowsky) Consider a two dimensional lattice with grid points unit distance apart. Show that a convex shape that is symmetric around a grid point has to include at least three grid points if its area is 4.
38. (Science Museum, unsolved) Which rectangles can be divided into unequal squares?
39. (Alkan) Consider permutations of an array which contains n copies of each integer from 1 to n. Two permutations are defined as orthogonal if their corresponding elements form distinct pairs. What is the maximum number of permutations such that any two are orthogonal? For example, here is a possible set of mutually orthogonal permutations for n=3: {111222333, 123123123, 123231312, 123312231}.
40. (Ian) My new favorite algorithm: Find an algorithm that discovers if a linked list has a cycle in it using bounded memory.
41. (Uttrash) You are in prison and they give you n red balls, n green balls and two boxes. You are to place the balls in the two boxes in any way you like. The next day they will pick a ball from one of the boxes, and if it is green you will be set free. How do you arrange the balls?
42. (Will) You randomly throw k balls into n bins. What is the expected number of occupied bins.
43. (Will) You randomly throw k points on the unit interval. What is the expected length of the longest segment.
44. (Michael, unsolved) You distribute 100 balls to 10 buckets. What is the expected value of the number of balls in the bucket with most balls.
45. (Lon) Draw 2 circles, 1 completely inside the other (but not necessarily concentric.) What is the probablility that a line intersecting the outer circle also intersects the inner circle. Now, do the same with rectangles.
46. (Thurston and Conway) An angel is stuck on an infinite sheet of graph paper, he can hop from square to adjacent square. Everytime the angel hops, the devil can knock out any square, so the angel can't ever go there. Can the devil trap the angel? What if the graph paper is a positive quadrant (i.e. is bounded on two sides).
47. This is not really math, but here are my two favorite algorithms: (1) Find an algorithm for perfect shuffling of an array. (2) Find an algorithm that will pick a perfectly random element from a list in one pass without knowing the size of the list beforehand.
48. (Alkan) Given two points find the point midway between them using only a compass (no ruler).
49. (Alkan) You are sitting at point [0,0] and looking towards right into a tunnel bounded by y=1/x and y=-1/x curves. The walls of the tunnel are reflecting. Prove that if you send a light beam into the tunnel in any direction other than straight to the right, the beam will be reflected back towards left.
50. (Deniz) Let x be a random variable which can take positive integer values. P(x)=1/2^x. We draw n random elements from this distribution. What is the probability that the n+1st element will be different from the first n?
51. (Alkan) Let A be the set of all rectangles that have one integer side. Prove that any rectangle constructed by concatenating rectangles from A will also be a member of A.
52. (Neal) Take a randomly shuffled deck. Open the cards one by one. At one point stop and predict that the next card is red. Is there a strategy that has more than 1/2 chance.
53. Pick two random points in the unit line segment. What is the expected distance between them?
54. Pick two random points in the unit circle. What is the expected distance between them?
55. (Umit) Suspend a rope from two points on the ceiling. What shape does it take?
56. (Bernoulli brothers) A ball is rolling from point A to a lower point B. What is the ideal curve for the path between A and B that minimize the travel time?
57. (Alkan) There are 100 light poles with switches on a street. In the beginning all lights are off. One person goes through pole number 1, 2, 3, ... and flips the switches. Then he goes back and goes through 2, 4, 6, ... and flips the switches. Then he goes back and goes through 3, 6, 9, ... and flips the switches. So at n'th round he flips the multiples of n. Which lights are on after 100 rounds?
58. (Deniz) There is a set A of n0 elements, and we randomly pick a subset B of n1 elements. We know that r0 of the elements in A were red. We are interested in finding out the number of red elements in B, r1. To find out we start picking random elements from B. We pick n2 elements, and r2 of them turn out to be red. Now what is the best estimate for r1?
59. (Minsky) I bring you three flipped cups and tell you there is gold under one of them. Furthermore, each cup has a number giving the probability that the gold is under that one. You immediately go to the one with highest probability. I tell you that you have amnesia and I may have tried this on you a million times. What is your best strategy?
60. (Minsky) An ant leaves a repeated binary pattern behind as it walks through the desert. What is the length of the shortest pattern that would let you distinguish which way the ant was going?
61. (Feyzu) Two points are chosen at random on a line AB, each point being chosen according to the uniform distribution on AB, and the choices being made independently of each other. The line AB may now be regarded as divided into three parts. What is the probability that they may be made into a triangle?
62. (IMO practice) The entries for a competition is locked in a safe. There are 11 judges. We would like them to be able to open the safe when more than half get together. How many locks / keys do we need?
63. (IMO practice) Given three parallel lines, show that an equilateral triangle can always be constructed with a vertex on each line.
64. (IMO-72/6) Given four distinct parallel planes, prove that there exists a regular tetrahedron with a vertex on each plane.
65. (Umit) A method for two people to share a pie fairly is to let one cut the other one pick. Generalize this method to n people.
66. You are making a random walk on an n-dimensional grid. What is the probability that you will ever return to the origin? (Hint: It is 1 for 1-D and 2-D! It is 0.3405 for 3-D).
67. (Ivanie) A rabbit hopping up the stairs can hop either one or two steps at a time. How many different ways can it climb n steps?
68. Show that if you cut off two opposite corner squares of a chess board, you cannot cover the rest with dominoes.
69. Show that n squares with total area less than 1/2 can always be fit into a unit square (non-overlapping).
70. Show that n squares with total area greater than 3 can always cover the surface of the unit square (non-overlapping).
71. You color all points of a plain with three colors. Show that I can always find two points of the same color that are a given distance apart.
72. You color all points on an equilateral triangle with two colors. I try to find a right triangle with its vertices on the edges of your triangle and all vertices having the same color. Can you find a coloring that prevents this?
73. How many 1's are there in the digits of numbers from 1 to 1 million? (one minute time limit).
74. (Michael) There is a piece of candy on every node of a binary tree. Find the shortest path through the binary tree that lets you collect all of the candies.
75. (Ihsan) Two men, x distance apart, start walking toward each other with speed v. At that instant a fly starts flying from one men's nose to the other with 2v speed. The fly keeps flying back and forth between the two noses until the guys meet. How much distance has the fly flown when they meet? (There is an easy way and a hard way to solve this).
76. (Ihsan) A coin is flipped until the first head appears. If you get a head in n flips you win $2ⁿ. How much are you willing to pay to play this game?
77. (Bilim ve Teknik) You need to paint the area under the curve 1/x. How can you do it with a finite amount of paint?

Full post...

A simple explanation of Variational Autoencoders

The goal of VAE is to model your data \(X\) coming from a complicated distribution \(P(X)\) using a latent (unobserved, hypothesized) variable \(Z\): \[ P(x) = \int P(x|z) P(z) dz \] This identity is true for any distribution \(P\) and any value \(x\). VAE takes \(P(Z)\) to be the multivariate standard normal. Note that this identity can also be written as an expectation: \[ P(x) = E_{z\sim P(Z)}[P(x|z)] \] and can be approximated by sampling \(z_n\) from \(P(Z)\): \[ P(x) \approx \frac{1}{N} \sum_{z_n\sim P(Z)} P(x|z_n) \] However for high dimensional spaces (images, text) typically modeled by VAE, this would be a poor approximation because for a given \(x\) value, \(P(x|z)\) would be close to 0 almost everywhere. Randomly sampling from \(P(Z)\) would be unlikely to hit regions of \(Z\) space where \(P(x|z)\) is high. Say we had a distribution \(Q(Z|X)\) which is more likely to give us \(z\) values where \(P(x|z)\) is high. We could rewrite our former identity as: \[ P(x) = \int P(x|z) P(z) Q(z|x) / Q(z|x) dz \] Note that this identity can also be expressed as an expectation: \[ P(x) = E_{z\sim Q(Z|x)}[P(x|z) P(z) / Q(z|x)] \] and can be approximated by sampling \(z_n\) from \(Q(Z|x)\) (this is called importance sampling and would converge faster because \(Q\) gives us better \(z\) values): \[ P(x) \approx \frac{1}{N} \sum_{z_n\sim Q(Z|x)} P(x|z_n) P(z_n) / Q(z_n|x) \] To train a VAE model we pick some parametric functions \(P_\theta(X|Z)\) (i.e. decoder, likelihood, generative network) and \(Q_\phi(Z|X)\) (i.e. encoder, posterior, inference network) and fiddle with their parameters to maximize the likelihood of the training data \( D=\{x_1,\ldots,x_M\} \). Actually, instead of likelihood \(P(D) = \prod P(x_m)\) we use log likelihood: \(\log P(D) = \sum\log P(x)\) because it nicely decomposes as a sum over each example. We now have to figure out how to approximate \(\log P(X)\). \[ \log P(x) = \log E_{z\sim Q(Z|x)}[P(x|z) P(z) / Q(z|x)] \] Jensen's inequality tells us that log of an expectation is greater than or equal to the expectation of the log: \[ \log P(x) \geq E_{z\sim Q(Z|x)}\log[P(x|z) P(z) / Q(z|x)] \] The RHS of this inequality is what is known in the business as ELBO (evidence lower bound), more typically written as: \[ \log P(x) \geq E_{z\sim Q(Z|x)}[\log P(x|z)] - D_{KL}[Q(Z|x)\,\|\,P(Z)] \] This standard expression tells us more directly what to compute but obscures the intuition that ELBO is just the expected log of an importance sampling term.

To see the exact difference between the two sides of this inequality we can use the integral version: \[ \begin{align} \log & P(x) - \int \log[P(x|z) P(z) / Q(z|x)] Q(z|x) dz \\ = & \int [\log P(x) - \log P(x|z) - \log P(z) + \log Q(z|x)] Q(z|x) dz \\ = & \int [\log Q(z|x) - \log P(z|x)] Q(z|x) dz \\ = & D_{KL}[Q(Z|x)\,\|\,P(Z|x)] \end{align} \] This allows us to write an exact equation, indicating the error of our approximation is given by the KL divergence between \(Q(Z|x)\) and \(P(Z|x)\): \[ \begin{align} \log & P(x) - D_{KL}[Q(Z|x)\,\|\,P(Z|x)] = \\ & E_{z\sim Q(Z|x)}[\log P(x|z)] - D_{KL}[Q(Z|x)\,\|\,P(Z)] \end{align} \]

Reference: Tutorial on Variational Autoencoders by Carl Doersch (https://arxiv.org/abs/1606.05908)
Full post...

What is wrong with p-values?

Earlier this year, editors of the journal Basic and Applied Social Psychology announced that the journal would no longer publish papers containing p-values. The latest American Psychological Association Publication Manual states that researchers should "wherever possible, base discussion and interpretation of results on point and interval estimates," i.e. not p-values. FDA has been encouraging Bayesian analysis. What is wrong with p-values?

What is a p-value? In the classical statistical procedure known as "significance testing", we have a default hypothesis, usually called the null hypothesis and denoted by H0, and we wish to determine whether or not to reject H0 based on some observations X. We choose a statistic S=f(X) (a scalar function of X) that summarizes our data. The p-value is the probability of observing a value at least as extreme as S under H0. We reject H0 if the p-value is below some specified small threshold like α=0.05 and we say something like "H0 is rejected at 0.05 significance level." This threshold or significance level (α) upper bounds the probability of false rejection, i.e. rejecting H0 when it is correct.

Example: We toss a coin 1000 times and observe 532 heads, 468 tails. Is this a fair coin? In this example the null hypothesis H0 is that the coin is fair, observation X is the sequence of heads and tails, and the statistic S is the number of heads. The p-value, or probability of S ∉ [469,531] under H0, can be calculated as: \[ 1 - \sum_{k=469}^{531} {1000 \choose k} \left(\frac{1}{2}\right)^{1000} = 0.04629 \] We can reject the null hypothesis at 0.05 significance level and decide the coin is biased. But should we?

Objection 1: (MacKay 2003, pp.63) What we would actually like to know is the probability of H0 given that we observed 532 heads. Unfortunately the p-value 0.04629 is not that probability (although this is a common confusion). We can't calculate a probability for H0 unless we specify some alternatives. Come to think of it, how can we reject a hypothesis if we don't look at what the alternatives are? What if the alternatives are worse? So let's specify a "biased coin" alternative (H1) which assumes that the head probability of the coin (θ) is distributed uniformly between 0 and 1 (other ways of specifying H1 are possible and do not effect the conclusion). We have: \[ P(S=532 \mid H_0) = {1000 \choose 532} \left(\frac{1}{2}\right)^{1000} = 0.003256 \] \[ P(S=532 \mid H_1) = \int_0^1 {1000 \choose 532} \theta^{532} (1-\theta)^{468} d\theta = 0.001 \] So H0 makes our data 3.2 times more likely than H1! And here the p-value almost made us think the data was 1:20 in favor of the "biased" hypothesis.

Objection 2: (Berger 1982, pp.13) Well, now that we understand p-value is not the probability of H0, does it tell us anything useful? According to the definition it limits the false rejection rate, i.e. if we always use significance tests with a p-value threshold α=0.01, we can be assured of incorrectly rejecting only 1% of correct hypotheses in the long run. So does that mean when I reject a null hypothesis I am only mistaken 1% of the time? Of course not! P(reject|correct) is 1%, P(correct|reject) can be anything! Here is an example:

	X=1	X=2
H0	.01	.99
H1	.01001	.98999

The table gives the probabilities the two hypotheses H0 and H1 assign to different outcomes X=1 or X=2. Say we observe X=1. We reject H0 at α=0.01 significance level. But there is very little evidence against H0, the likelihood ratio P(X|H1)/P(X|H0) is very close to 1, so the chance of being in error is about 1/2 (assuming H0 and H1 are a-priori equally likely). Thus α=0.01 is providing a very misleading and false sense of security when rejection actually occurs.

Objection 3: (Murphy 2013, pp.213) Consider two experiments. In the first one we toss a coin 1000 times and observe 474 tails. Using T=474 as our statistic the one sided p-value is P(T≤474|H0): \[ \sum_{k=0}^{474} {1000 \choose k} \left(\frac{1}{2}\right)^{1000} = 0.05337 \] So at a significance level of α=0.05 we do not reject the null hypothesis of an unbiased coin.

In the second experiment we toss the coin until we observe 474 tails, and it happens to take us 1000 trials. Different intention, same data. This time N=1000 is the natural test statistic and the one sided p-value is P(N≥1000|H0): \[ \sum_{n=1000}^\infty {n-1 \choose 473} \left(\frac{1}{2}\right)^n = 0.04994 \] Suddenly we are below the magical α=0.05 threshold and we can reject the null hypothesis. The observed data, thus the likelihoods of any hypotheses for this data have not changed. The p-value is based not just on what actually happened, but what could have happened. This is clearly absurd.

Objection 4: (Cumming 2012) If we base the fate of our hypotheses on p-values computed from experiments, at the very least we should expect the p-values (thus our critical decisions) to change very little when we replicate the experiments. Unfortunately p-values do not even give us stability, as this wonderful video "Dance of the p values" by Geoff Cumming illustrates:

Conclusion: (Jaynes 2003, pp.524) expressed the absurdity of significance testing best:

In order to argue for an hypothesis H1 that some effect exists, one does it indirectly: invent a "null hypothesis" H0 that denies any such effect, then argue against H0 in a way that makes no reference to H1 at all (that is, using only probabilities conditional on H0). To see how far this procedure takes us from elementary logic, suppose we decide that the effect exists; that is, we reject H0. Surely, we must also reject probabilities conditional on H0; but then what was the logical justification for the decision? Orthodox logic saws off its own limb.
Harold Jeffreys (1939, p. 316) expressed his astonishment at such limb-sawing reasoning by looking at a different side of it: "An hypothesis that may be true is rejected because it has failed to predict observable results that have not occurred. This seems a remarkable procedure. On the face of it, the evidence might more reasonably be taken as evidence for the hypothesis, not against it."

Full post...

Vi Hart

For more from my 7 year old daughter's new favorite educator Vi Hart check out Khan Academy, YouTube, other videos, Wikipedia, or her blog.
Full post...

Probabilistic Programming

The probabilistic programming language Church brings together two of my favorite subjects: Scheme and Probability. I highly recommend this tutorial to graduate students interested in machine learning and statistical inference. The tutorial explains probabilistic inference through programming starting from simple generative models with biased coins and dice leading up to hierarchical, non-parametric, recursive and nested models. Even at the undergraduate level, I have long thought probability and statistics should be taught in an integrated manner instead of their current almost independent treatment. One roadblock is that even the simplest statistical inference (e.g. three tosses of a coin with an unknown (uniformly distributed) weight results in H, H, T; what is the fourth toss?) requires some calculus at the undergraduate level. Using a programming language like Church may allow an instructor to introduce basic concepts without students getting confused about the details of integration.
Full post...

Probability twisters

Of all the math problems I collect, these are my favorites. They do not require anything more than elementary math, but they do seem to trigger a software bug in most people's brains. Choose between several different arguments that lead to different answers for each problem. (Updated Nov 2010: two siblings problem)

1. (Two siblings) If you pick a random family with two kids and calculate the probability of both being girls the obvious answer would be 1/4 (assuming girls and boys being equally likely). However simple variations of this problem easily lead to some confusion:
   • Variation 1: If you ask the family whether they have at least one girl, and they say yes, the two girl probability is 1/3.
     
   • Variation 2: If you see one of their kids on the street and notice that she is a girl, the two girl probability is 1/2.
     
   You can verify these answers by imagining the sample space of all (say four million) two-child families and assuming equal numbers of boy-boy, boy-girl, girl-boy, and girl-girl families (say one million each). What is tricky to understand is why these two variations have different answers when it seems like they give you the exact same information. Here are some more variations:
   
   • Variation 3: If you learn that the older sibling is a girl, the two girl probability is 1/2.
     
   • Variation 4: If you learn that the family has one girl named Florida, the two girl probability is approximately 1/2.
     
   • Variation 5: If you learn that the family has one girl born on a Wednesday, the two girl probability is 13/27.
     


2. (Umit - Monty Hall Problem) You are a participant on the game show "Let's Make a Deal." Monty Hall shows you three closed doors. He tells you that two of the closed doors have a goat behind them and that one of the doors has a new car behind it. You pick one door, but before you open it, Monty opens one of the two remaining doors and shows that it hides a goat. He then offers you a chance to switch doors with the remaining closed door. Is it to your advantage to do so?
   
   • Argument 1: It does not matter. The probability of finding the car in the remaining two doors was equal in the beginning, and they are still equal now. The fact that you put your hand on one of them cannot increase or decrease its probability of having the car under it.
     
   • Argument 2: If we repeated this experiment a million times, you would get the the car only one third of the time by sticking to your first door. People who consistently switch would win the other two thirds. Therefore you should switch.
     
   • Argument 3: Think about what you would do if there were a thousand doors, rather than three, and Monty Hall opened 998 doors with goats behind them.
     
   • Bibliography: http://math.rice.edu/~pcmi/mathlinks/montyurl.html
     
   
   
3. (Encyclopedia of Bridge) You are South with three small of a suit, and dummy has QJ9. You desperately need a trick from this suit. You lead low to the Queen, and East wins with the King. When you get a second chance, you lead low to the J9 and West plays low. Should you play the Jack or the 9?
   
   • Argument 1: If either opponent has A10, it does not matter. If East has the Ace and West the 10, you want to play the 9. If it is the other way around, you want to play the Jack. Both sides are equally likely to have the Ace so it does not matter what you play.
     
   • Argument 2: You should play the Jack because East has the Ace only 1/3 of the time. If East had AK, he would play the King to the first trick only half the time. If he had K10, he would always play the King. Since we know he played the King, it is twice as likely that he has the K10 and not AK.
     
   • Note: Note the similarity with the Monty Hall problem.
     
   
   
4. (Memduh - Two envelope problem) I offer you a pick between two envelopes with money. One envelope has twice as much money as the other. You pick one, and out comes 10 dollars. Now I give you a chance to switch. Would you like to switch? How much are you willing to pay to switch?
   
   • Argument 1: Of course you switch. The expected amount of money in the other envelope is 0.5x5 + 0.5x20 = 12.5 dollars. In fact you are willing to pay up to 2.5 dollars to switch.
     
   • Argument 2: What if I asked you the question before you opened the envelope and saw the 10 dollars? Using the same reasoning, you can assume there is A dollars in the envelope and compute 0.5x(A/2) + 0.5x(2A) = 1.25A for the expected money in the other envelope. So you would switch. Just before you open your new envelope, I ask you whether you would like to switch again? What would your answer be?
     
   • Note: In fact if I can find two people that believe in Argument 1, I can build a money machine. Just keep giving them two envelopes with 5 and 10 dollars and charge for switching... :^) (Of course I charge them whatever comes out of the first envelope for playing the game, so that it is a zero sum game.)
     
   • Bibliography: http://www.u.arizona.edu/~chalmers/papers/envelope.html
   
   
5. (Neal) I pick two real numbers. You look at one of them. Can you find a strategy that lets you guess whether you are looking at the larger or smaller number with more than 1/2 success rate.
   
   • Argument 1: Obviously you cannot find such a strategy.
     
   • Argument 2: Take a probability distribution that is non-zero over all the real numbers (standard normal for example). Draw a random number from this distribution and respond assuming that the hidden number is equal to your random number. There are three cases: (i) Your random number will be smaller than both my numbers, in which case you have 50% chance of winning. (ii) Your random number will be larger than both my numbers, in which case you have 50% chance of winning. (iii) Your random number will be between my two numbers, in which case you have 100% chance of winning. The average is greater than 50%.
     
   • Note: Using a similar argument one can show that you could in fact make a profit in the two envelope problem by employing a mixed strategy.
     
   
   
6. (Alkan) You draw a random line that cuts a circle with unit radius. What is the probability that the chord will be longer than sqrt(3)?
   
   • Argument 1: Consider the distance between the midpoint of the chord and the center of the circle. If this distance is less than 1/2 the chord will be longer than sqrt(3). Therefore the answer is 1/2.
     
   • Argument 2: Draw a tangent at one of the points the line intersects the circle. Consider the angle between this tangent and the chord. If this angle is between 60 and 120 degrees, the chord will be longer than sqrt(3). Therefore the answer is 1/3.
     
   • Argument 3: Consider the midpoint of the chord. If this midpoint is within a concentric circle with half the radius, the chord will be longer than sqrt(3). The area of a circle with half the radius is 1/4th of the original. Therefore the answer is 1/4.

Full post...

Beta distribution

[Math_] Neat fact about the Beta distribution: starting with a uniform prior, after observing k/n successes, the CDF for parameter p (the probability of success in a single trial), i.e. the probability that p is smaller than a certain value x, is equal to the probability that we get k+1 or more successes out of n+1 trials using that x!
Full post... Related link

A different representation for integers

[Math_] The fundamental theorem of arithmetic states that every positive integer has a unique factorization into primes. Instead of the usual decimal notation where each position represents a multiple of powers of ten, we can represent each integer with a "primal" notation where each position is the power of a prime number. Here is what I mean:

2: (1)
3: (1 0)
4: (2)
5: (1 0 0)
6: (1 1)
7: (1 0 0 0)
8: (3)
9: (2 0)
10: (1 0 1)
11: (1 0 0 0 0)
12: (1 2)

The right-most position is power of two's, next to it is power of three's and so on. The intuition one gets from such a representation is remarkable. Let's prove a simple bound related to the prime number theorem (i.e. how many primes are there less than a given number?)

Let p(n) be the number of primes less than n where 2^k <= n < 2^(k+1). Now consider all the numbers smaller than n. Their primal representations are all distinct, can have at most p(n) elements, and none of the elements can be greater than k. This gives us the inequality:

k^p > n
p lg(k) > lg(n)
p > lg(n) / lg(lg(n))

Not a very tight bound, but could be used as an alternative to Euclid's proof of the infinity of the number of primes :)

One thing about our primal representation is bothering me. Namely the elements themselves are integers, but we are denoting them with regular decimal digits instead of the primal representation! The primal representation for 1 should be (). Zero is more of a problem. Let's keep it as 0 for now and see what we get:

1: ()
2: (())
3: (() 0)
4: ((()))
5: (() 0 0)
6: (() ())
7: (() 0 0 0)
8: ((() 0))
9: ((()) 0)
10: (() 0 ())
11: (() 0 0 0 0)
12: (() (()))

Much better. This representation gives us a one-to-one mapping between all integers and a certain subset of binary trees or s-expressions for those of you familiar with lisp jargon. Unfortunately not all possible binary trees or s-expressions with 0 are meaningful (for example (0)). There must be an even more elegant mapping, but I couldn't think of one so far!


Full post...

Math Links

[Math_] Links to websites with interesting math problems.

www.cut-the-knot.org

Interactive math miscellany and puzzles. Definitely the best.

rec.puzzles

The rec.puzzles newsgroup has an archive and an FAQ page
which contain a wealth of information about many interesting problems.

sci.math

This is the FAQ page for the sci.math newsgroup which
is another place you can search for answers.

Shack's math problems

This is a similar page that contains
interesting math problems.

IMO

This is the
Canadian site for International Mathematical Olympiad which is a
yearly competition for high school students.

Chance

This is a course developed at Dartmouth aiming to make students more informed, critical readers of current news stories that use probability and statistics.

Geopuzzles

This is a database of geometry problems.

Heard on the Street

This is a collection of questions asked in Wall Street job interviews.

Full post...

Unsolved Problems

These are the 24 problems from the wonderful book "Old and new unsolved problems in plane geometry and number theory" by Victor Klee and Stan Wagon, MAA, 1991. Some problems are too cryptic to understand without the book. I'll type more explanations some day...

Plane Geometry

Is each reflecting polygonal region illuminable?
(Imagine a room in a 2-D universe. If the walls form a polygonal shape
and they reflect light, can you always illuminate the whole room with
a single light source?)

A point P inside a closed convex curve C is called equichordal if every chord of C drawn through point P has the same length. Is there a curve with two equichordal points?
(Marek Rychlik kindly informed me of his solution to this problem.  His homepage has references for the published work.)

When congruent disks are pushed closer together, can the area of their union increase?

If a convex body C contains a translate of each plane set of unit diameter, how small can C's area be?

What is the smallest number f(n) such that any set of f(n) points (non-collinear) always contains the vertices of some convex n-gon?

If n points are not collinear, must one of them lie on at least n/3 connecting lines?

Is there a polygon that tiles the plane but cannot do so periodically?

What is the minimum number of colors for painting the plane so that no two points at unit distance receive the same color?

Can a circle be decomposed into finitely many sets that can be rearranged to form a square?

Does the plane contain a dense rational set?

Does every simple closed curve in the plane contain all four vertices of some square?

Does each nonseparating plane continuum have the fixed-point property?

Number Theory

Do there exist positive integers x, y, and z and an integer n>=3 such that x^n + y^n = z^n?
(Too late for this one :^) Wiles got it in 1993.  Check out http://www.best.com/~cgd/home/flt/flt01.htm for the proof.

Does there exist a box with integer sides such that the three face diagonals and the main diagonal all have integer lengths?

Does the greedy algorithm always succeed in expressing a fraction with odd denominator as a sum of unit fractions with odd denominator?

Is there an odd perfect number? Are there infinitely many even perfect numbers?
(A perfect number is one whose factors add up to itself, e.g. 6, 28)

Do the nontrivial zeros of the Riemann zeta function all have real part 1/2?

Is there a polynomial-time algorithm for obtaining a number's prime factorization?

Is every positive integer eventually taken to the value 1 by the 3n+1 function?
(3n+1 function is defined as f(n) = n/2 (if n even); 3n+1 (if n odd))

Is there an algorithm to decide whether a polynomial with integer coefficients has a rational root?

Interesting Real Numbers

Are the digits in the decimal expansion of pi devoid of any pattern?

Are pi and e algebraically independent? Is their ratio rational?

If an irrational number is real-time computable, is it necessarily transcendental? Is sqrt(2) real-time computable?
(A number is real-time computable if the amount of time spent computing its digits is linear in the number of digits.)

Is 1 + 1/2^5 + 1/3^5 + ... irrational?

Full post... Related link

Bijective Representations of Trees Using Cons Pairs

[Hacking_ Math_] --DRAFT-- Different ways of representing trees with list structure: We need to distinguish two things: the branching factor of the tree (binary vs variable), and whether internal nodes have any content. We are interested in one-to-one and onto (bijective) representations, any arbitrary list structure should correspond to a unique tree and vice versa.

1. Binary tree, no internal content: trivial representation with the cons pairs. A tree is a pair of two elements. An element is either an atom or another tree.
2. Variable branch, no internal content: simple representation given in the 6.001 tree lecture. A tree is a list of children. A list is a null terminated chain of cons pairs. A child is either an atom or another tree.
3. Binary tree, internal content: typical C representation would use a struct of three elements: left, right, and content. One possibility with cons pairs is to define a node as two pairs: (cons content (cons left right)). (is this bijective?)
4. Variable branch, internal content: SGF defines a format based on DFS walking (pre-order?) of the tree. Here is an EBNF definition:

GameTree = "(" Sequence { GameTree } ")"
Sequence = Node { Node }
Node = ";" { Property }

{...} represents 0 or more repetition. So a tree is a list of nodes followed by a list of trees. Each node is an atom.

A 1-branch tree gives simply a linked list. In terms of cons pairs: there are two types of pairs: node pairs have atom cars and tree pairs have pair cars. The car of a node pair is its content, the cdr may point to any type of pair or nil. The car of a tree pair is a node pair and its cdr is a tree pair or nil. There are never two open parens in a row so this is obviously not bijective.


Full post... Related link

Are seven primitive lisp operators all necessary?

[Hacking_ Math_] --DRAFT-- Paul Graham talks about the seven primitives of LISP.

Full post... Related link

A two envelopes puzzle

[Math_] Here is a version of the problem from Bertsekas and Tsitsiklis: "You are handed two envelopes, and you know that each contains a positive integer dollar amount and that the two amounts are different. You select at random one of the two envelopes and after looking at the amount inside, you may switch the envelopes if you wish. Is there a strategy that will increase above 1/2 the probability of ending up with the envelope with the larger amount?"

This is not to be confused with the related and much more popular two envelopes paradox. I first heard this problem in a different form where the two numbers did not have to be positive or integers.

I think it is instructive to look at the different variants of this problem where the two numbers come from: a finite interval, a half open interval, and a circular structure like hours or angles.


Full post... Related link