Archive for the ‘Math’ Category.

3-Pile Nim as an Automaton

In my paper with Joshua Xiong, Nim Fractals, we produced a bijection between P-positions in the three-pile Nim and a three-branch Ulam-Warburton automaton. We also defined a parent-child relationship on games that is induced by this bijection. Namely, two consecutive P-positions in a longest optimal game of Nim are the ones that correspond to a parent-child pair in the automaton. A cell in the Ulam-Warburton automaton has exactly one parent. That means, if (a,b,c) is a Nim P-position, then exactly one of (a − 1,b − 1,c), (a − 1,b,c − 1), and (a,b − 1,c − 1) must be a P-position and a parent of (a,b,c). (See our paper for more details.)

Now I want to explicitly write out the rules of an automaton which will generate the Nim P-positions in 3D.

Let me restrict the evolution of the automaton to the non-negative octant. That is, we consider points (a,b,c) in 3D, where each coordinate is a non-negative integer. We define the neighbors of the point (a,b,c) to be the points that differ from (a,b,c) in two coordinates exactly by 1. So each point strictly inside the octant has 12 neighbors. (There are three ways to choose two coordinates, and after that four ways to choose plus or minus 1 in each of them.

There is a geometric interpretation to this notion of neighborhood. Let us correspond a unit cube to a point with integer coordinates. The center of the cube is located at the given point and the sides are parallel to the axes. Then two points are neighbors if and only if the corresponding cubes share one edge. Now it becomes more visual that a cube has 12 neighbors, as it has 12 edges.

Here is the rule of the automaton. Points never die. We start with the patriarch, (0,0,0), one point being alive. The non-alive point is born inside the non-negative octant if it has exactly 1 alive neighbor that is closer to the patriarch. In other words the point (a,b,c) is born if and only if exactly one out of three points (a − 1,b − 1,c), (a − 1,b,c − 1), and (a,b − 1,c − 1) is alive. It follows that the points that are born at the n-th step has a coordinate sum 2n.

Consider for example the starting growth. At the first step the points (0,1,1), (1,0,1) and (1,1,0) are born. At the next step the points (0,2,2) and (2,0,2) and (2,2,0) are born. while the (1,1,2) will never be born as starting from the second step it has at least two live neighbors: (0,1,1) and (1,0,1) that are closer to the patriarch.

Theorem. In the resulting automaton, the points that are born at step n are exactly the P-positions of Nim with the total of 2n tokens.

Proof. Only the points with an even total can be born. Now we proceed by induction on the total number of tokens. The base case is obvious. Suppose we proved that at step n exactly P-positions with 2n tokens are born. Consider a P-position of Nim: (a,b,c) such that a + b + c = 2n + 2. Remember, that bitwise XOR of a, b, and c is zero. Consider the 2-adic values of a, b, and c (aka the smallest powers of 2 dividing a, b, and c). There should be exactly two out of these three integers that have the smallest 2-adic value. Suppose these are a and b. Then (a − 1,b − 1,c) is a P-position, while (a − 1,b,c − 1) and (a,b − 1,a − 1) are not. That means by the inductive hypothesis (a,b,c) has exactly one alive neighbor. So the position (a,b,c) is born at time n + 1.

Now we need to proof that nothing else is born. For the sake of contradiction suppose that (a,b,c) is the earliest N-position to be born. That means it has a live neighbor that is a P-position closer to the patriarch. WLOG we can assume that this neighbor is (a − 1,b − 1,c).

If a − 1 and b − 1 are both even, then (a,b,c) is a P-position, which is a contradiction. Suppose a − 1 and b − 1 are both odd. Then their binary representations can’t have the same number of ones at the end. Otherwise, (a,b,c) is a P-position. That is a and b have different 2-adic values. Suppose a has a smaller 2-adic value, Then, for (a − 1,b − 1,c) to be a P-position a and c has to have the same 2-adic value. That means (a,b − 1,c − 1) is a P-position too. Now suppose a − 1 and b − 1 are of different parities. Without loss of generality suppose a − 1 is odd and b − 1 is even, then c is odd. Then (a − 1,b,c − 1) is a P-position too. Thus we can always find a second neighbor with the same number of tokens. That is, both neighbors are alive at the same time; and the N-position (a,b,c) is never born. □

One might wonder what happens if we relax the automaton rule by removing the constraint on the distance to the patriarch. Suppose a new point is born if it has exactly one neighbor alive. This will be a different automaton. Let us look at the starting growth, up to a permutation of coordinates. At step one, positions (0,1,1) are born. At the next step positions (0,2,2) are born. At the next step positions (0,1,3), (1,2,3) and (0,3,3) are born. We see that (0,1,3) is not a P-positions. What will happen later? Will this N-position mess up the future positions that are born? Actually, this automaton will still contain all the P-positions of Nim.

Theorem. In the new automaton, the points that are born at step n and have total of 2n tokens are exactly the P-positions of Nim with the total of 2n tokens.

Proof. Only the points with an even total can be born. Now we proceed by induction on the total number of tokens. The base case is obvious. The birth of the points that have total of 2n tokens and are born at step n depend only on the points with the total of 2n − 2 tokens that are born at step n − 1. By the inductive hypothesis, those are the P-positions with 2n − 2 tokens. So the points have total of 2n tokens and are born at step n match exactly the first automaton described above. To reiterate, N-positions with 2n tokens are born after P-positions with 2n tokens, so they do not influence the birth of P-positions with 2n + 2 tokens. □

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

The Longest Optimal Game of Nim

In the game of Nim you have several piles with tokens. Players take turns taking several tokens from one pile. The person who takes the last token wins.

The strategy of this game is well-known. You win if after your move the bitwise XOR of all the tokens in all the piles is 0. Such positions that you want to finish your move with are called P-positions.

I play this game with my students where the initial position has four piles with 1, 3, 5, and 7 tokens each. I invite my students to start the game, and I always win as this is a P-position. Very soon my students start complaining that I go second and want to switch with me. What should I do? My idea is to make the game last long (to have many turns before ending) to increase the chances of my students making a mistake. So what is the longest game of Nim given that it starts in a P-position?

Clearly you can’t play slower then taking one token at a time. The beauty of Nim is that such an optimal game starting from a P-position is always possible. I made this claim in several papers of mine, but I can’t find where this is proven. One of my papers (with Joshua Xiong) contains an indirect proof by building a bijection to the Ulam-Warburton automaton. But this claim is simple enough, so I want to present a direct proof here. Actually, I will prove a stronger statement.

Theorem. In an optimal game of Nim that starts at a P-position the first player can take one token at each turn so that the second player is forced to take one token too.

Proof. Consider a P-position in a game of Nim. Then find a pile with the lowest 2-adic value. That is the pile such that the power of two in its factorization is the smallest. Suppose this power is k. Notice that there should be at least two piles with this 2-adic value.

The first player should take a token from one of those piles. Then the bitwise heap-sum after the move is 2k+1−1. Then the Nim strategy requires the second player to take tokens from a pile such that its value decreases after bitwise XORing with 2k+1−1. All piles with the 2-adic value more than k will increase after xoring with 2k+1−1. That means the second player has to take tokens from another pile with 2-adic value k. Moreover, the second player is forced to take exactly one token to match the heap-sum. □

In the position (1,3,5,7) all numbers are odd, so I can take one token from any pile for my first move, then the correct move is to take one token from any other pile. My students do not know that; and I usually win even as the first player. Plus, there are four different ways I can start as the first player. This way my students do not get to try several different options with the same move I make. After I win several times as the first player, I convince my students that I win anyway and persuade them to go back to me being the second player. After that I relax and never lose. I am evil.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

The Reuleaux Tetrahedron

Why are manhole covers round? The manhole covers are round because the manholes are round. Duh! But the cute mathematical answer is that the round shapes are better than many other shapes because a round cover can’t fall into a round hole. If we assume that the hole is the same shape as the cover but slightly smaller, then it is true that circular covers can’t fall into their holes. But there are many other shapes with this property. They are called the shapes of constant width.

A circle and a Reuleaux triangle

Given the width, the shape with the largest area is not surprisingly a circle. The shape with the smallest area and a given constant width is a Reuleaux Triangle. Here is how to draw a Reuleaux triangle. Draw three points that are equidistant from each other at distance d. Then draw three circles of radius d with the centers at given points. The Reuleaux triangle is the intersection of these three circles.

Can we generalize this to 3d? What would be an analogue of a Reuleaux Triangle in 3d? Of course, it is a Reuleaux Tetrahedron: Take four points at the vertices of a regular tetrahedron; take a sphere at each vertex with the radius equal to the edge of the tetrahedron; intersect the four spheres.

Is this a shape of the constant width? Many people mistakenly think that this is the case. Indeed, if you squeeze the Reuleaux tetrahedron between two planes, one of which touches a vertex and another touches the opposite face of the curvy tetrahedron, then the distance between them is equal to d: the radius of the circle. This might give you the impression that this distance is always d. Not so. If you squeeze the Reuleaux tetrahedron between two planes that touch the opposite curvy edges, the distance between these planes will be slightly more than d. To create a shape of constant width you need to shave off the edges a bit.

Meissner Bodies

Theoretically you can shave the same amount off every edge to get to a surface of constant width. But this is not the cool way to do it. The cool way is to shave a bit more but only from one edge of the pair of opposite edges. You can get two different figures this way: one that has three shaved edges forming a triangle, and the other, where three shaved edges share a vertex. These two bodies are called Meissner bodies and they are conjectured to be shapes of the constant width with the smallest volume.

On the picture I have two copies of a pair of Meissner bodies. The two left ones have three edges that share a vertex shaved off. The very left shape gives a top view of this vertex and the solid next to it has its bottom with holes looking forward. The two shapes on the right show the second Meissner body in two different positions.

I recently discovered a TED-Ed video about manhole covers. It falsely claims that the Reuleaux tetrahedron has constant width. I wrote to TED-Ed, to the author, and posted a comment on the discussion page. There was no reaction. They either should remove the video or have an errata page for it. Knowingly keeping a video with an error that is being viewed by thousands of people is irresponsible.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

Really Big Numbers

Really Big NumbersI received a book Really Big Numbers by Richard Schwartz for review. I was supposed to write the review a long time ago, but I’ve been procrastinating. Usually, if I like a book, I write a review very fast. If I hate a book, I do not write a review at all. With this book I developed a love-hate relationship.

Let me start with love. I enjoyed reading the first 80 pages. The pictures are great, and some explanations are very well thought out. Plus, I haven’t thought much about really big numbers, so the book helped me understand them. I was impressed with how this book treats very difficult ideas with simple explanations and illuminating images. I was captivated by it.

Now to hate. I had two problems with this book: one pedagogical and the other mathematical.

The pedagogical issue. The beginning of the book is suitable for small children. Most of the book is suitable for advanced middle-schoolers who like mathematics. The last part is very advanced. Is it a good idea to show children a book that looks like a children’s book, but which soon becomes totally out of their reach? Richard Schwartz understands it and says many times that pieces of this book might be read several years apart. Several years? What child is ready to wait several years to finish a book? How would children feel about the book and about numbers when no matter how hard they try, they cannot understand the end of the book?

As a reviewer, I can’t recommend the full book for kids who are not ready to grasp the notion of the Ackermann function or arrow notation. Even if the child is capable of understanding these ideas, there are mathematical issues that would prevent me from recommending it.

The mathematical issue. Let me start by explaining the notion of plex. We call an n-plex a number that is equal to 10n. For example, 2-plex means 102 which is 100, and 10-plex means 1010. The fun part starts when we plex plexes. The number n-plexplex means 10 to the power n-plex which is 10(1010). We can continue plexing: n-plexplexplex means 10 to the power n-plexplex. When you are hunting for really big numbers, it is easier to write the number of plexes rather than writing plexes after plexes. Richard Schwartz introduces the following notation to help visualize the whole thing. He puts numbers in a square. Number n in a square means 1-plexed n times. For example, 2 inside a square means 1010. Ten inside a square is 1-plexplexplexplexplexplexplexplexplexplex.

We can start nesting squares. For example, 2 inside a square means 1-plex-plex or 1010. Let’s add a square around it: 2 inside two squares means 1010 inside a square, which equals 1 plexed 1010 times. To denote 10 nested in n squares Richard Schwartz uses the next symbol: n inside a pentagon. For example, 1 inside a pentagon is 10 inside a square. I wrote this number in the previous paragraph: it is 1-plexplexplexplexplexplexplexplexplexplex. Similarly, n inside a hexagon means 10 inside n nested pentagons. We can continue this forever: n inside a k-gon is 10 inside k nested (k-1)-gons.

What bothers me is why a square? Why not a triangle? If we adopt this scheme, what is the meaning of a number in a triangle? Let’s try to unravel this. Following Richard Schwartz’s notation we get that n inside a square is the same as 10 inside n nested triangles. What do we do n times with 10 to get to 1 plexed n times? 1-plexed n times is 10 plexed n-1 times. There is a disconnect in notation here. For example, 10 in two nested triangles should mean 2 inside a square that is 1010. 10 inside one triangle should mean 1 inside a square which is 10. This doesn’t make any sense.

I started googling around and discovered the Steinhaus–Moser notation. In this notation a number n in a triangle means nn. A number n in a square means the number n inside n nested triangles. A number n in a pentagon means the number n inside n nested squares. And so on. This makes total sense to me. If we move down the number of sides, we can say that the number n inside a 2-gon means n times n and the number n inside a 1-gon means n. This is perfect.

Schwartz changed the existing notation in two places. First he made everything about 10. This might not be such a bad idea except his 10 inside a square doesn’t equal 10 inside a square in Steinhaus–Moser notation. In Steinhaus–Moser notation 10 inside a square means 10 plexed 10 times. The author removed one of the plexes. He made 10 inside the square to mean 1 plexed 10 times, and as a result it stopped working.

Even though the first 83 pages are delightful and the pictures are terrific, the notation doesn’t work. What a pity.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

An Orthogonal Quadrangle

An Orthogonal Quadrangle

Consider a triangle with vertices A, B, and C. Let O be its orthocenter. Let’s connect O to the vertices. We get six lines: three sides of the triangle and three altitudes. These six lines are pair-wise orthogonal: AO ⊥ BC, BO ⊥ AC, and CO ⊥ AB.

It is easy to see that A is the orthocenter of the triangle OBC, and so on: each vertex is the orthocenter of the triangle formed by the other three. We say that these four points form an orthocentric system.

I heard a talk about this structure at the MOVES 2015 conference by Richard Guy. What I loved in his talk was his call to equality and against discrimination. The point O plays the same role as the other three points. It should be counted. Richard Guy suggested calling this system an orthogonal quadrangle. I am all for equality. This is not a triangle, this is a quadrangle!

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

The Ford Circles Game

What are the Ford circles? A picture is worth a thousand words, so here is a picture.

Ford Circles

We draw a circle for any rational number p/q between 0 and 1 inclusive. We assume that p/q is the representation of the number in the lowest terms. Then the center of the circle is located at (p/q,1/q) and the radius is 1/q. The number inside a circle is q.

Here’s the game. We start with any circle on the picture, except for the two largest circles corresponding to integers 0 and 1. In one move we can switch to a larger circle that touches our circle. The person who ends up at the two largest circles corresponding to integers 0 or 1 loses. Equivalently, the person who ends in the central circle marked “2” wins.

There are other ways to describe moves in this game in terms of rational numbers corresponding to circles, that is, the x-coordinates of their centers. Two circles corresponding to numbers p/q and r/s touch each other iff one of the following equivalent statements is true:

  • The cross-determinant of two numbers p/q and r/s that is defined as |ps-qr| equals to 1;
  • p/q and r/s are neighbors in some Farey sequence;
  • One of the numbers is the parent of the other in the Stern-Brocot tree.

Let me explain the last bullet. Given two rational numbers in their lowest terms a/b and c/d, we generate their mediant as: (a+c)/(b+d). We call the two numbers a/b and c/d the parents of the mediant (a+c)/(b+d). The Stern-Brocot tree starts with two parents 0/1 and 1/1. Then their mediant is inserted between them to create a row: 0/1, 1/2, and 1/1. Then all possible mediants of two consecutive numbers are inserted in a given row to get a new row. The process repeats ad infinitum. The famous theorem states that any rational number between 0 and 1 will appear in the process.

What I like about this game is a simple and beautiful description of P-positions (These are the positions you want to end your move at in order to win.) P-positions are numbers with even denominators in their lowest terms.

Ford Circles

In the picture above P-positions are blue, while other positions are red. All circles touched by blue are red. And if we look at the larger neighbors of every red circle, one of them is blue and one is red.

Let’s prove that the numbers with even denominators satisfy the conditions for P-positions. First, two circles corresponding to numbers with even denominators can’t touch each other. Indeed, the cross-determinant of two such fractions is divisible by 2. Second, each red circle has to touch one blue and one red circle with larger radii. Indeed, the circles with larger radii touching a given circle are exactly the parents of the circle. If the mediant has an odd denominator, then one of the parents must have an even denominator and the other an odd denominator.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

Weighted Mediants

Let us start with regular (non-weighted) mediants. Suppose we have two fractions a/b and c/d, the mediant of these two numbers is the wrong way a child might sum these two fractions: (a+c)/(b+d). There is nothing wrong with this childish way of summing, it is just not a sum of two numbers, but rather an operation the result of which is called a mediant. One must be careful: the result doesn’t depend on the initial numbers chosen, but on their representations. The way to deal with this is to assume that a/b, c/d, and (a+c)/(b+d) are in their lowest terms.

The numerical value of the mediant is always in between given numbers. This is probably why it is called a mediant.

Suppose you start with two rational numbers 0/1 and 1/1, and insert a mediant between them. If you continue doing it recursively, you can reach any rational number between 0 and 1. This is a well-known property of the mediants. For example, after three rounds of inserting mediants into the initial sequence (0/1, 1/1), we get the sequence: 0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1.

The mediants are easy to generalize if we assign weights to initial fractions. Suppose the first fraction has weight m and the second n, then their weighted mediant is (am+cn)/(bm+dn). The simplest generalization happens when the total weight, m+n is 3. In this case, given two rational numbers a/b and c/d, the left mediant is (2a+c)/(2b+d) and the right one is (a+2c)/(b+2d). Obviously the inequality property still holds. If a/b ≤ c/d, then a/b ≤ (2a+c)/(2b+d) ≤ (a+2c)/(b+2d) ≤ c/d.

James Propp suggested the following question for our PRIMES project. Suppose the starting numbers are 0/1 and 1/1. If we recursively insert two weighted mediants in order between two numbers we will get a lot of numbers. For example, after two rounds of inserting weighted mediants into the initial sequence (0/1, 1/1), we get the sequence: 0/1, 1/5, 2/7, 1/3, 4/9, 5/9, 2/3, 5/7, 4/5, 1/1. It is easy to see that new fractions must have an odd denominator. Thus unlike the standard case, not every fraction will appear. The question is: will every rational number between 0 and 1, which in reduced form has an odd denominator appear?

I started working on this project with Dhroova Aiylam when he was a high-school junior. We didn’t finish this project during the PRIMES program. But Dhroova finished another project I already wrote about: he analyzed the case of the standard mediants with any starting points. He showed that any rational number in between the starting points appears.

Dhroova became an undergraduate student at MIT and we decided to come back to the initial PRIMES project of weighted mediants. In our paper Stern-Brocot Trees from Weighted Mediants we prove that indeed every fraction with an odd denominator between 0 and 1 appears during the recursive procedure. We also analyzed what happens if we start with any two rational numbers.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

Two Fake Coins

You are given N coins such that two of them are fake and the other coins are genuine. Real coins weigh the same. Fake coins weigh the same and are lighter than real ones. You need to find both fake coins using a balance scale in the smallest number of weighings.

It is easy to estimate the number of weighings from below using information theory. Given N coins you will have N choose 2 different answers. The number of possible answers has to be not more than 3w, where w is the number of weighings. This generates a trivial information-theoretic bound (ITB) on the number of coins that can be processed in a given number of weighings.

Previous authors used computers to completely analyze small numbers of weighings: from 2 to 5.

My colleagues from Russia, Konstantin Knop and Oleg Polubasov, performed some fantastic programming accompanied with some subtle heuristic and found optimal solutions for up to 10 weighings. For 11 and 12 weighings, the program is not efficient enough to find the optimal solutions: it found some solutions. Surprisingly, for up to 10 weighings, the optimal solutions match the information-theoretic bound (ITB). The results are in the table below. The first row represents the number of weighings w. The second row is the largest number of coins N for which a solution is found. The last row is the information-theoretic bound (ITB) we explained above.

w 5 6 7 8 9 10 11 12
N 22 38 66 115 198 344 585 1026
ITB 22 38 66 115 198 344 595 1031

Their paper, Two counterfeit coins revisited, is available in Russian. Lucky for us, 70 of 73 pages are pseudo-code of solutions for which you do not need any Russian. You just need to understand the pseudo-code. Here is the explanation.

Each line begins with its number. After it they have the weighing in the format 1 10 v 4 5 meaning coins 1 and 10 are weighed versus coins 4 and 5. Each weighing is followed by a colon, after which they describe in order actions for three different outcomes of the weighing: equality, the first pan is lighter, and the second pan is lighter. Each action is one of the following:

  • => L means go to line L.
  • (a, b) means the fake coins are a and b.
  • – means this branch is impossible and there is no output.
  • => 23. sym indicates the symmetry of the weighing and its result, therefore the resulting go-to line, 23, is omitted as being equivalent to another line.
  • – . sym means the output is symmetric to another one.

The line numbers after => in line L are always 3L+1, 3L+2 and 3L+3. The sym symbol implies that line 3L+3 is omitted as a symmetric version of line 3L+2.

For example, here is their solution for 2 weighings and 4 coins in their pseudo-code. An empty line separates different weighings:

0. 1 v 2 : => 1, => 2, => 3. sym

1. 1 v 3 : – , (1, 2), (3, 4).
2. 3 v 4 : – , (1, 3), – . sym

Another solution for 3 weighings and 7 coins:

0. 1 2 v 3 4 : => 1, => 2, => 3. sym

1. 1 v 2 : => 4, => 5, => 6. sym
2. 1 v 2 : (1, 2), => 8, => 9. sym

4. 5 v 6 : (5, 6), (5, 7), – . sym
5. 3 v 4 : – , (1, 3), – . sym
8. 5 v 6 : (1, 7), (1, 5), – . sym

If you want to see an optimal solution for 10 weighings, look at the paper: the algorithm takes 36 pages.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

The Wythoff’s Game Evolution Graph

In my paper Nim Fractals written with Joshua Xiong we discovered an interesting graph structure on P-positions of impartial combinatorial games. P-positions are vertices of the graph and two vertices are connected if they are consecutive P-positions in an optimal longest game.

A longest game of Nim is played when exactly one token is removed in each turn. So in Nim two P-positions are connected if it is possible to get from one of them to the other by removing two tokens.

In the paper we discussed the evolution graph of Nim with three piles. The graph has the same structure as three branches of the Ulam-Warburton automaton.

The evolution graph of the 2-pile Nim

For completeness, I would like to describe the evolution graph of the 2-pile Nim. The P-positions in a 2-pile Nim are pairs (n,n), for any integer n. Two positions (n,n) and (m,m) are connected if and only if m and n differ by 1. The first picture represents this graph.

The Wythoff’s game is more interesting. There are two piles of tokens. In one move a player can take any number of tokens from one pile or the same number of tokens from both piles.

The P-positions (n,m) such that nm start as: (0,0), (1,2), (3,5), (4,7), (6,10) and so on. They can be enumerated using φ: the golden ratio. Namely, nk = ⌊kφ⌋ and mk = ⌊kφ2⌋ = nk + k, where k ≥ 0.

The evolution graph of the Wythoff's game

In a longest Wythoff’s game the difference between the coordinates decreases by 1. That is, it takes a maximum of 2k steps to end an optimal game starting from position (nk,mk). The picture shows the evolution graph.

The interesting part of the picture is the crossover between two “lines”. From positions with large coordinates like (6,10) with a difference of 4 you can get to only one position with a difference of 3: (4,7) and not (7,4). But from position (3,5) with a difference of 2 you can get to both positions with a difference of 1: (1,2) and (2,1).

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

The Advantage of a Window

I already wrote about the sliding-window variation of the Secretary Problem. In this variation, after interviewing a candidate for the job, you can pick him or any out of w − 1 candidates directly before him. In this case we say that we have a sliding window of size w. The strategy is to skip the first s candidates, then pick the person who is better than anyone else at the very last moment. I suggested this project to RSI and it was picked up by Abijith Krishnan and his mentor Shan-Yuan Ho. They did a good job that resulted in a paper posted at the arXiv.

In the paper they found a recursive formula for the probability of winning. The formula is very complicated and not explicit. They do not discuss the most interesting question for me: what is the advantage of a sliding window? How much better the probability of winning with the window as opposed to the classical case without the window?

Let us start with a window of size 2, and n applicants. We compare two problems with the same stopping point. Consider the moment after the stopping point when we see a candidate who is better than everyone else before. Suppose this happens in position b. Then in the classic problem we chose this candidate. What is the advantage of a window? When will we be better off with the window? We will be better if the candidate at index b is not the best, and the window allows us to actually reach the best. This depends on where the best secretary is, and what happens in between.

If the best secretary is the next, in position b + 1, then the window gives us an advantage. The probability of that is 1/n. Suppose the best candidate is the one after next, in position b + 2. The window gives us an advantage only if the person in position b + 1 is better than the person in position b. What is the probability of that? It is less than 1/2. From a random person the probability of the next one being better is 1/2. But the person in position b is not random, he is better than random, so the probability of getting a person who is even better decreases and is not more than 1/2. That means the sliding window wins in this case with probability not more than 1/2n.

Similarly, if the best candidate is in position b + k, then the sliding window allows us to win if every candidate between b and b + k is better than the previous one. The probability of the candidate being better at every step is not more than 1/2. That means, the total probability of getting to the candidate in position b + k is 1/2k-1. So our chances to win when the best candidate is at position b + k are not more than 1/2k-1n. Summing everything up we get an advantage that is at least 1/n and not more than 2/n.

The probability of winning in the classical case is very close to 1/e. Therefore, the probability of winning in the sliding window case, given that the size of the window is 2, is also close to 1/e.

Let us do the same for a window of any small size w. Suppose the best secretary is in the same window as the stopping candidate and after him, that is, the best candidate is among the next w − 1 people. The probability of this is (w − 1)/n. In this case the sliding window always leads to the best person and gives an advantage over the classical case. When else does the sliding window help? Let us divide the rest of the applicants into chunks of size w − 1. Suppose the best applicant is in the chunk number k. For the sliding window to allow us to get to him, the best candidate in every chunk has to be better than the best one in the previous chunk. The probability of that is not more than 1/2k-1. The probability that we get to this winner is not more that (w-1)/2k-1n. Summing it all up we get that the advantage of the window of size w is between (w − 1)/n and 2(w − 1)/n.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail