Tuesday, May 15, 2007

Weight and Diets

This post is somewhat off point, but it has to do with why it is that some people don't ever seem to put on weight and others are in a constant battle to stay slim.

A NYT times article based on a new book by Gina Kolata suggests that we all have internal mechanisms that try to keep our body weight within a narrow range, and that this range is not the same across people. The way these mechanisms work is to slow down or speed up our metabolic rate depending on how much we eat. People who are naturally thin will rapidly lose weight if they put on pounds and vice a versa. Studies have shown that an individual's natural weight zone is genetically determined.

This doesn't really lead to an argument for abdicating responsibility for one's obesity --- but it does say that it's really much harder for some people to do anything about it. If we truly understood this it would affect the way we judge a person who seems more than a little bit on the heavier side. More importantly it would change the way many people judge themselves.

It is always a bit uncomfortable to talk about the fact that we all arrive with natural advantages and disadvantages but these days I see much more of it the popular science press. (The findings I just talked about are actually not recent but are only now finding their way into the NYT.)

For example, consider the more-or-less established view that men of south asian origin are much more likely than average to get heart attacks regardless of diet and where they live. Stories like this one abound. It suggests that any South Asian male who has waist bigger than 35 inches is almost certainly doomed.

Wednesday, May 9, 2007

Solving the Oddball Problem with N balls

In the last post we solved the odd ball problem for 12 balls. Today I want to present a solution for N balls. I do not know of another general solution, but when N can expressed as (3^n-3)/2, there are very nice solutions here, here and here.

First, label the N balls 1 through N. Then mark each ball with a + and a – sign. These signs stand for the various hypotheses. For example the + on ball 1 stands for the fact that ball 1 could be the odd ball and it could be heavier than the rest. As we go through our weighings we erase these marks . Obviously when a ball has no marks left it isn't the oddball. We call all eliminated balls, good balls. A ball that isn't good is a candidate ball.

Our goal will be to eliminate as many marks as we can in each weighing. The marks we erase after a weighing depend on the outcome of the weighing, i.e. L,R or E (following the conventions of the previous post). Recall that in a weighing we put some balls on the left pan, an equal number of balls on the right pan and the rest of the candidate balls "on the side".

How Marks are Erased: If the outcome is E, then balls we just weighed are all eliminated and the balls on the side are the only candidate balls. If the outcome is L then erase any – signs on the balls on the left pan and erase any + signs on the balls of the right pan. The balls "on the side" are all eliminated as well as any being weighed that have no marks left. Similarly, if the outcome is R then erase any + signs on the L pan etc.

Again, the trick to solving this problem is to focus on marks rather than balls. Let m[k] be the number of remaining marks at the beginning of the kth weighing. For example, m[1]=2N. Since there are only three possible outcomes in a weighing you can't hope to eliminate more 2/3 of the marks after a weighing. The way to do this is to ensure that regardless of whether the outcome of a weighing is L,R or E you will be left with very close to 1/3 of the marks you had before the weighing, i.e. m[k+1] is about m[k]/3. For example, to ensure that this happens when the outcome is E, you want about m[k]/3 of the marks to be in balls that are "on the side".

Of course m[k] may not be divisible by 3. But notice that if you've got K things you can always divide them into three piles so that two piles have the same number of things and the third one is off by at most one thing. For example, if you have 6 things, all the piles have 2 things; 7 things give piles of 2,2,3 and 8 things give piles 3,3,2. We'll call this dealing into 3 piles
and to avoid confusion later refer to this d3p(K)=(p,p,q) where 2p+q=K and abs(p-q)<= 1.

Another potential complication is that in the weighing process you may come to a situation where some balls have 2 marks on them and others have just 1 mark. That's something we will avoid. In the beginning all candidate balls will have two marks on them. But the first time a weighing has the outcome L or R, each candidate ball will have exactly one mark on it. (To see this reexamine the way we marks are erased.) This condition will persist until we find the odd ball. So our method boils down to provide how to do each weighing, W[k] when each candidate ball has 2 marks (we call these AllEven weighings) and when each candidate ball has one mark (we call these PostEven weighings). The nice thing about this way of describing the method is that we don't have to specify a complicated tree of what to do which would make explaining things virtually impossible!

Both kinds of weighings take as a variable, k, the number the number of weighings. Also, the first weighing is always AllEven, so start the process by calling AllEven(1).

We denote O(W(k)) to be the outcome of weighing W(k) and it can take a value from L,R or E.

AllEven(k) All the candidate balls are marked with a + and a -

  1. If m[k]>2 then let d3p( m[k]) =(p,p,q). p can be either odd or even, but the q must always be even since m[k] is even.
    1. W(k) :
      1. If p is even put p/2 balls on each pan and the left over q/2 is on the side.
      2. If p is odd put p balls on the left pan, p good balls on the right pan and q/2 balls on the side (you always have p good balls to spare for this)
    2. If O(W(k))=E then increment k and go back 1
    3. If O(W(k)) = L/R then increment k and call PostEven(k)
  2. If m[k]=2 then W(k): Weigh the candidate ball against a good ball and then terminate.

PostEven(k): All the candidate balls are marked either + or – but not both.

  1. If m[k]>3 then
    1. If there are even number of balls marked + put an equal number of them in each pan. Otherwise put 1 + ball on the side and split the remaining + balls over the pans. Repeat for the balls marked -. Now there are equal number of + balls in the L and R pans, and an equal number of – balls in the L and R pans. There are 0,1 or 2 balls on the side. Suppose there are b balls on each of the pans and s balls on the side.
    2. While (b-s> 1.) [i.e. keep repeating this step until b-s<=1]
      1. Remove a ball from the L pan and a ball of the same sign from the R pan and put both balls on the side.
    3. W(k): Weigh the balls as they are in the pans. (Note: if dp3( m[k])= (p,p,q) then there are p balls in each pan.)
    4. Increment k and Go back to 1
  2. If m[k]<= 3 then it easy to terminate in one more weighing.

As an example, pick N=12. We start off by calling AllEven. Clearly h[1]=24. At the end of W(1), h[2]=8. If O(W(1))=E then we stay in AllEvens and W(2) will have 3 of the remaining candidate balls vs 3 good balls. W(3) is easy. If O(1)=L/R then we go to PostEven(2) etc. W(3) yields the oddball.

If N=(3^k -3)/2. Then h[1]= 3^k -3, h[2]=3^{k-1}-1,h[3]=3^{k-2}-1,….,h[k]=2 and therefore the oddball will identified in k weighings.

Also, if N= 3^k. Then h[1]=2*3^k, h[2]= 2*3^{k-1},…,h[k+1]=2, and therefore the oddball will identified in k+1 weighings.

For arbitrary N, notice that regardless of whether the kth weighing is AllEven or PostEven,: m[k+1]<=celing(m[k]/3). Note that ceiling(x) is the largest integer greater than equal to x.Thus each weighing eliminates the maximum number of hypotheses possible.

So to get to the bottom line: define h[k+1]= celing(h[k]/3), h[1]=2N. Then the min # of weighings required to identify the odd ball is the smallest K for which h[K]<=3.

Thursday, May 3, 2007

Toy Puzzle Solution

In my last post I posed the odd ball problem. In this post I'll solve it for 12 balls. This solution is almost identical to what is found in the excellent book by Mackay. In the next post, I'll show how to generalize the solution to more balls.

For 12 balls we start out with 24 possible hypotheses since each ball can be either heavy or light.

First, since all the balls look alike let's just number them 1 to 12 to tell them apart. Let's denote the hypothesis that ball 1 is heavier than the rest by 1+ and that it is lighter by 1-. Similarly denote 2+,2-, 3+,3- etc. Of course, only one of these 24 hypotheses can be correct. Our job is to find out which one in 3 weighings.

Let's call the three weighings W1, W2 and W3. Also, if we weigh balls 1,2,3 (in the left pan) against 4,5,6 (in the right pan), then we'll denote that weighing as 1,2,3#4,5,6. In general we can use this notation to describe any weighing. There are three possible outcomes of any weighing: the left pan is heavy, the right pan is heavy or the two pans are even. Let's just denote these outcomes as L, R and E respectively. We say O(W1)=L to denote that the outcome of weighing one is that left pan is heavier.

Now to the solution! Most people will struggle with various combinations of balls until they have either given up or stumbled on an answer. That's no fun! We are going to pick our weighings based on a very simple strategy:

Try to pick each weighing in such a way that it is equally likely for the outcome to be L, R or E.

Why this strategy? That's for the next post, but think about this way for now: You don't learn from expected outcomes but from unexpected ones. Anyway, this strategy will give us the solution to the oddball problem in three weighings:

The only weighing that results in equally likely outcomes is when you weigh four balls against four other balls. So we chooseW1= 1,2,3,4#5,6,7,8 . Clearly if O(W1)= E then the oddball is one of 9,10,11,12 and the probability of that is 4/12=1/3. That leaves 2/3 which is divided equally between the outcomes L and R. So this weighing matches our strategy since the probability of each outcome is 1/3. Now depending on what happens in W1:

  1. O(W1)=E: Then the oddball is one of 9,10,11,12, i.e. there are only 8 remaining hypotheses (see how we eliminated 2/3 of the hypotheses?).

    Now for W2 we have to shoot for the same thing, i.e. make the outcomes L,R,and E as close to being equally likely as we can. Since the number of hypotheses is not a multiple of 3 we won't be able to get the outcomes to exactly equal but we can come close. There are several ways to do this --here's one:

W2: 9,10,11#1,2,3. Notice that we already know that 1,2,3 are not oddballs. So the probability of outcomes L,R and E are 3/8,3/8 and 1/4 respectively.

If O(W2) =E then the oddball is ball 12. All we have to do in weighing 3 is to just weigh ball 12 against any other ball, e.g. W3=12#1. If the outcome is L, then 12 is heavy and if the outcome is R then ball 12 is light.
If O(W2)= L then we know that the oddball is heavy and the remaining hypotheses are just 9+,10+,11+. Now the third weighing is easy. For example,W3= 9#10 will work. If L then 9 is the oddball, if R then 10 is oddball and if E then 11 is the oddball.
If O(W2) =R then this case is almost identical to the previous case except that the oddball is lighter.

  1. O(W1)=L: We are left with the hypotheses: 1+,2+,3+4+,5-,6-,7-,8-. Now for the second weighing we want the outcomes to be as equally likely as possible. How about::
    W2=1,2,5#3,4,6? The probabilities of the outcomes L, R and E are 3/8,3/8 and 1/4 respectively which is as close to being equiprobable as you can get. Now if O(W2)=E then 7- or 8- are true. W(3)=7#8 will do the job. And if O(W2)= L we are left with 1+,2+ and 6-. Then W(3)= 12 for the third weighing identifies the oddball.
  2. O(W1)=R: This case is very similar to case 2 and can be completed the same way.

The cool thing about this solution is that it all comes from a very simple strategy. But why does it work? Next time I'll talk about this and the solution to the oddball problem with N balls.

Friday, March 16, 2007

"Toy" Puzzle #1

Wow, it's been a long time since I said anything here. Just have been too busy and I can't bring myself to post filler material. Hopefully the next few posts will be interesting.

Some people love to solve mathematical brainteasers, but most consider it a silly waste of time. There is something really inefficient (and even dumb) about allocating so much time and toil on these mental boondoggles! Yet sometimes brainteasers can serve as "toy" versions of much more important problems. Since they have a small number of variables, you can "play" with these problems and subsequently make headway on more involved ones. Most great scientists have used toy problems that somehow captured the essence of a bigger problem to make significant discoveries. In this post I will look at such an "impractical" problem and show that it can actually instruct. This is an old teaser but I actually have a twist to the solution that I think is new. I'll present that in my next post. Today all I will do is pose the problem and give some hints.

The Oddball Problem: You are given n identical looking balls. n-1 of them weigh the same, but one of them is either heavier or lighter than the others (you don't know which). Given a two pan weighing machine what is the minimum number of weighings you need to do to be sure that you have identified that odd ball? You can only use the weighing pan as follows: put some balls in the left pan, some in the right pan and observe one of three possible outcomes: either the left pan is heavy or the right pan is heavy, or they are even.


Since you don't know if the odd ball is heavier or lighter things get a bit tricky. This problem is often posed with 12 balls. Here's a problem worth working on:

Show that for 12 balls you can always identify the oddball in 3 weighings!

A few hints: Every time you do a weighing, you want to learn something new, i.e. you want to gain information that allows you to eliminate as many possibilities as possible. Initially, there are 2*12=24 different possibilities since each of the 12 balls can be the odd ball and an odd ball could be heavier or lighter. But you have to plan your weighings carefully! Think of each weighing as an experiment with an uncertain outcome. Suppose you start out by weighing ball 1 against ball 2. If the pan is heavy either to left or the right that's great news since you now know that the oddball is either ball 1 or 2. But it is far more likely that the pans will come up even. In fact this chance is 5/6. Under this predictable outcome we just eliminate 2 of the 12 balls from consideration, i.e. only 4 out of a possible 24 hypotheses. The way the problem is stated we've got to be sure we can nail the oddball after 3 weighing so you can't count on getting lucky. This tells us that the strategy for getting to 3 weighings has to be a bit more clever.

The next post will have a simple solution for the n ball problem....

Tuesday, February 13, 2007

Two Awesome Books

It's been a few days since I did my first post --- getting into the habit of being more regular is going to be difficult!

Actually, I was rereading two highly original, excellent books, that are both strangely enough, out of print ! (Note, however, that used copies are available easily online or from libraries.) They are both trying to deal with the problem of how people deal with information, and I think that they share the underlying goal of shedding some light on how to increase grokrate. One of them, Information Anxiety by Richard Saul Wurman is a "how to" book, and the other, Silicon Dreams by Robert Lucky is a "how come" book. Both are written for a general audience, although Silicon Dreams has a few equations here and there.

Both authors are successful practitoners. Wurman is the creator and designer of the ACCESS travel books, and so brings this designer perspective to the problem. He has a seemingly endless number of interesting things to say about how information should be organized and communicated in order to be quickly groked. Lucky is an engineer (he invented something important called adaptive equalizers and is a Bell Labs veteran), and spent his intellectually formative years studying information theory. So his focus is almost exclusively on how to define and measure the amount of information in something. He talks about the fact that while multimedia takes thousands of times more bits to send than text (even when it is efficiently compressed), it does not appear to contain that much more meaningful information. He also hypothesizes that our grokrate (although obviously he does not call it that) is roughly 50b/s, a pitifully small number!

If you have any interest in understanding how people absorb information and what limits the rate at which it can be done, I strongly recommend that you check these books out. Even though they are ten years old, they are quite amazingly current.

Tuesday, February 6, 2007

Grokrate

I finally have a blog. My hope is when I am in between things I will actually post something instead of playing minesweeper or doing something equally inane. Maybe some of these posts will actually make sense and be of interest to others.

So what is "grokrate"? It's a word I made up so let me explain. When you stare at something complicated, after a while it may actually start making sense. This deeper understanding, in which the information gets internalized into your thinking is the grokking of that information. The term grok comes from the Robert A. Heinlein novel Stranger in a Strange Land, and it is pretty commonly used among geeks.

The grokrate is simply the rate at which you grok. Sometimes our grokrate is phenomenally high. For example, when you are crossing a busy street your brain assesses the speed and positions of a variety of different objects, and then has you walk (run) across safely. Action heros and NBA basketball players are forever impressing us with their grokrates as they successfully improvise in seemingly impossible situations .

However, that kind of information is different from information on the web.
When you want to buy a new car, plan a trip or understand more about climate change, you are more-or-less certain to be in for a very long period of meandering through various websites. Even if you do find everything you need, it's hard to synthesize it. The grokrate is typically very very low. This turns most people into information grazers -- they'd rather flit from one amusing story to the next and ignore the "hard" information synthesis required to really grok stuff. Or they rely on someone else to tell them what to think...

So what can you do to increase your grokrate? I'm interested in figuring out effective ways to do that.