Friends in high density places

Last August, I found the map below.  2% of the Australian population lives in the yellow area and the remaining 98% lives in the white area.

Like Australia, Canada is geographically large, but sparsely populated.  Canada's population density is a little higher, though not by much.  On average, there are 3.56 people per square kilometre in Canada compared to Australia's 3.06.  Also, like Australia, our population is centred around a small number of urban areas.  The three most populous metropolitan areas, Toronto, Montreal, and Vancouver, alone make up more than a third of our population, the top 10 more than a half, and the top 100 nearly 80% (mind you, most of the cities in that top 100 list have less than 100,000 people, and some, such as Timmins and Cape Breton are quite large in area).  (Population data culled from various Wikipedia pages).

So I wondered what a similar map for Canada would look like.

Unfortunately, there doesn't seem to be much information out there about how the map was created.  Within each of the yellow and white areas, we see other borders drawn in.  I'm assuming that these represent some national subdivisions, perhaps municipal boundaries or census regions.  So whoever made the map made a choice of which regions to colour yellow and which regions to colour white.

There are many choices that would split the population between 2% and 98%, though.  For example, to construct a region containing 98% of the population, like the one coloured white here, one could start with the sparsely populated inland regions and add increasingly denser regions until 98% is reached.  The result would not be very interesting.  Australia's population is roughly 23.5 million.  2% of that is 470,000, only a bit smaller than the population of Tasmania, the country's smallest province, and roughly 10% of the population of Sydney's, the country's largest city.

So we could create a map where all of Australia other than some parts of Tasmania are coloured white, or where all but a few urban specks of Sydney are coloured white.  In the latter case, the yellow parts would probably so small that it would be difficult or impossible to see them.  The map would hardly be different from a plain map of Australia.  What makes the existing map interesting, though, is how small the area containing 98% of the population is.

To make the map as interesting as possible, then, we would want the white part to be as small as possible.  As I said above, however, there is no information about how the map was created.  Is the white region as small as it could be, based on the subdivisions used, or is there something other choice that would lead to an even smaller region?  Did the creator simply pick the $m$ sparsest or least populous subdivisions, or was something more sophisticated used?

I found it through Twisted Sifter, which refers back to a Reddit thread.  This thread links to an image hosted on imgur, which I embedded above.  After that the trail goes cold.  One of comments from the original poster suggest that he or she is the one who created it, but there is no follow up, and the user's online profile doesn't offer any direction either.

Without knowing, then, we'd have to come up with our own method.  One simple method is to rank the subdivisions by population, and choose the first $m$ that give 98% of the population.  Another would be to rank by area, and choose the first $m$ that give 98% of the population.  A third option would be to rank by density and choose the first $m$ that give 98% percent of the population.  None of these are guaranteed to give the smallest area that includes 98% percent of the population (or, equivalently, the largest area that includes 2% of the population).

Another less obvious way to solve the problem is through a mathematical technique known as linear programming.  We create a function that gives us the area if a certain set of subdivisions is chosen, then we try to maximize the area under the condition that the percentage of the population that lives in the chosen set of regions is less than or equal to 2%. Ideally, we'd be able to insist that the population is equal to 2%, but this might not be possible.  For our purposes that shouldn't be a problem, though, since a smaller number than 2% would only further illustrate the sparseness.

Now let's write this in mathematical notation.  Suppose that ${\bf c}$ is a vector where entry $i$ of ${\bf c}$ is the area of subdivision $i$.  Let $A$ be a row matrix where column $i$ of the only row of $A$ is the percentage of the population in subdivision $i$.  Let ${\bf x}$ be a vector of variables where entry $i$ of ${\bf x}$ is the variable $x_i$.  If $x_i=1$ when subdivision $i$ is chosen and $0$ otherwise, then $f({\bf x})$ gives the total area for that choice of subdivisions and $A{\bf x}$ is the corresponding percentage of the population.  Then we want the following

• maximize $f({\bf x})={\bf c}\cdot {\bf x}$ such that
• $A{\bf x}\leq 0.02(=2\%)$ and
• $x_i$ is 0 or 1 for each $i$

This is not exactly an linear programming problem.  The third condition makes it a binary integer programming problem, because each $x_i$ can be one of only two integer values, 0 or 1.  To make it a linear programming problem we replace the third condition with the following

• $x_i\geq 0$ for each $i$.

 This could allow for the possibility that a region is partially included.  That is, only a certain percentage of a region's population counts towards the total percentage.  That means that we also want $x_i\leq 1$, since we can't include more than 100% of a region's population.  In that case, the problem is

• maximize $f({\bf x})={\bf c}\cdot {\bf x}$ such that
• $A{\bf x}\leq 0.02$ and
• $0\leq x_i\leq 1$ for each $i$.

As stated, this is not a linear programming problem.  However, we can easily turn it into one.  Suppose that there are $n$ subdivisions in total.  Let $B$ be the $(n+1)\times n$ matrix whose first row is $A$ and whose remaining $n$ rows is the $n\times n$ identity matrix.  Let ${\bf b}$ be the vector with $n+1$ components whose first entry is $0.02$ and whose remaining entries are all 1.  Then we can rewrite the above as

• maximize $f({\bf x})={\bf c}\cdot {\bf x}$ such that
• $B{\bf x}\leq {\bf b}$ and
• $x_i\geq 0$ for each $i$.

This is now a linear programming problem.  Unfortunately, the solution to the linear programming problem is not what we want, although it has the upside of being easier to solve.  In general, solving a binary integer programming problem is not easy.  So we may be able to solve the linear programming problem and use that to get a good solution to our problem (for example, by rounding), even though it might not be the optimal one.  Note that if we restricted to integer solutions, then we get the binary integer programming problem back.  There are some special cases where integer linear problems are easy to solve.  Perhaps this is one.  (Who knows? Maybe one of the three simple methods I gave above will turn out to be the optimal solution, though I'm sceptical any of them would be.)

Seeing a version of this map for Canada would be most interesting to me, because that's where I'm from and because of the geographical similarities.  But maps of this sort could be interesting for other countries, or cities, provinces or states, continents, or even the whole inhabitable world.  And of course, we need not insist on a split between 2% and 98%.  Perhaps a 50/50 split would be interesting.  Maybe there is some other interesting percentage, such as a percentage $X$ for which $X$ percent of the population lives on $100-X$ of the land (if that number even exists).

If the binary integer programming problem could be solved, it would be a simple (though possibly tedious) matter of collecting the required geographic data and plugging it into some map making software.

Update: After finishing this post, I emailed a colleague of mine who has much more experience in linear programming than me to ask him if he had any insights.  He told me that this is a knapsack problem.  I had heard of this problem before, but only informally, so I didn't clue in that it was a special case of integer linear programming.  Oddly, neither the linear programming nor the integer linear programming Wikipedia pages refer to the knapsack problem, nor does the knapsack page refer to either of the other two.

In any case, this is sort of good news, but only good in the sense of "maybe less bad."  The general binary linear programming problem is NP-hard, whereas the knapsack problem is NP-complete.  NP-hard problems are at least as hard to solve as NP-complete problems.  The reason it's only "maybe less bad" is that there is not currently known whether or not there are efficient algorithms for solving NP-complete problems.  According to the Wiki page on the knapsack problem, though, there are efficient algorithms for finding approximate solutions.  Maybe these would be good enough.  Indeed, our eyes may not be able to discern between the optimal solution and an approximate one.  In that case, I guess it's more or less good news.

Notes:

• For more on linear programming, see here and here or, better yet, pick up a book, such as this one, which was what I first learned about linear programming from.
• I don't currently have the resources at my disposal to do any of the above, but the population density below from Statistics Canada probably gives a rough idea of what the result would be.
  
  

Teaching Math with PowerPoint - a post mortem

I taught a second year linear algebra course in the fall term of the 2013 - 2014 school year.  The first few lectures were review of the prerequisite course.  My normal teaching practice consists almost exclusively of writing on the board when I'm not directly interacting with students.  But I figured that since my students had learned the material already, they didn't need to take notes and I could run through it a little faster than if they were seeing it for the first time.

So I put all of the review notes on PDF Slides (not actually PowerPoint, despite what I wrote in the title), using the Beamer package for LaTeX.  The first week went fairly well, so instead of switching back to my usual practice at the end of the review stage, I decided to to continue using slides.  I didn't intend on using them for the rest of the term, but in the end, that's what I did.

Overall, it was well received by the students.  Direct feedback was positive, and I received no complaints on course evaluations.  One complaint that could have been levelled at me is that the slides were not always perfect.  Sometimes there were typos, for example.  Perhaps the students were content with the corrected versions that I later posted on the course website.

Student performance was consistent with other courses I've taught.  A couple of students, but one was a student who was also doing poorly in other classes, and there were extenuating circumstances to explain the other student's failure. 

It would be irresponsible to draw conclusions about the effectiveness of the practice at this stage, mind you.  It was the first and only time I've taught this course and the first time I've used slides to this extent.  Nevertheless, it went well enough that I plan on doing it again in the upcoming year.

Although the course was far more heavily oriented towards slides than any other time I taught, I still did rely heavily on the blackboard.  I believe it's better to work out examples with the students, so I would only write the examples on the slides, and work out the solutions on the blackboard (often putting the final answer on the slides too, though not always).  

I also made heavy use of Beamer's "pause" command.   That way, I could present the text of a given slide gradually, one line at a time or even one word at a time if I wanted to, rather than all at once.  To some extent, this mimics writing on the board, where the content is revealed chalk stroke by chalk stroke.  I think this makes it easier to absorb.  Rather than trying to take in a whole slide's worth of information, only one line needs to be comprehended at time.  I also think it helps to keep the pace of the lecture from getting too fast, an easy temptation to give into with slides (or overheads, in the olden days).

Switching back and forth between the blackboard and the screen was a bit frustrating at times, since it seems that most classrooms equipped with projectors (which is most classrooms, if not all, these days) are not designed to mix the two methods. 

I taught in three different classrooms for the class.  Each room had a different layout with different upsides and downsides.

One of the classrooms had the projector screen covering up one panel of the chalkboard.  This was okay as long as I could fit everything in the other panel.  Occasionally, I needed both, which meant rolling up the screen and turning off the projector, then, when I'm done with the other panel, pulling the screen down and waiting for the projector to turn back on.  None of these are onerous tasks, but they interrupt the flow of the lecture and use up time.

The other two classrooms had their screen covering the middle of the blackboard, with the edges of the boards still exposed to write on.  In one room, the exposed edges were quite large, about the size of the uncovered panel in the other classroom.  In the other, however, they were fairly narrow.  The annoyance in both cases was that if an example took up more than one board, I had to finish it on the other side where it was hard to see what I had written on the first side because the screen was in the way.

Another issue I had is the fact that screen real-estate is quite limited.  Some things could not be fit onto a single slide.  Something on one slide might refer to something on another slide.  On a blackboard, one can use two different panels for the different things, but there is only one screen.

The other problem I ran into was malfunctioning technology.  In one room, the projector bulb burnt out.  In another, I could not access the network to log in to the computer.  Fortunately, computer services was quick to replace the bulb in the former case, and there was another open classroom with a working projector in the latter case.


If I had my way, each room would be equipped with two, or even three, projector screens, one for the current slide, and the other(s) for showing preceding slides or calling up older results or examples.  There would also be a chalkboard with at least two panels to write on, even when all screens are in use.  Of course, this wouldn't be feasible in all but the largest classrooms, and even if it were, it could end up being the classroom version of The Homer.  I'd settle for an effort on the part of classroom designers to consider that someone might want to use both blackboard and projector at the same time.

Despite the space taken up by the above complaints, they were all fairly minor in the grand scheme of the course.  They don't add up to enough to discourage me from doing it again, looking for places to improve, and maybe thinking about trying it for other courses.

Competition and the Logistic Distribution

In my recent post on the other bell curves, I wondered if there was some familiar processes underlying the logistic distribution that would parallel coin-flipping for the normal distribution.  I noted there that logistic distribution works better for the ELO rating system than the normal distribution did.

I also noted that the curve that describes the logistic distribution arises from population growth models that account for competition for resources.  The ELO rating system is also used in the context of competition, but for games.  I wondered whether there was something to this.  Was it a mere linguistic coincidence, or was there a deeper connection?

Well, I still don't have a complete answer, but I can see at least one connection between the two scenarios.  In both cases, there is competition for a finite resource.  For the population growth model it is food supply, and for games, it is wins. 

The parallel is not exact, however.  In particular, the logistic model is used to describe the size of a population, but for a game, the logistic distribution is only used to compute the probable outcomes within a set of competitors, not the number of competitors. So the connection is not complete.

When to set office hours

This past term, I was assisting as a tutor for one section of a math course (I am teaching this course in the present term).  The students in the class wanted to have some extra tutorial time.  One of the students collected information about when everyone was available.  It turned out that there was no common period where all interested students could come, so there ended up being no extra tutorial.

This was between the professor and the students.  I didn't find out about it until after the fact.  I assume from the conversation, though, that there was going to be at most one extra tutorial, because the proposal was nixed once it was revealed that there was no common period.

But suppose that the professor was willing to offer a number of tutorials limited only by what periods where either he or I would have been available to lead one (assuming that the tutorials would be held during the day).  Then it may still be possible to find a way to accommodate everyone.  In fact, it's pretty easy to tell whether or not it is.

We already have a list of which periods students are available.  Since at least one of the available tutors (in this case, me and the professor) must be at the tutorial, we can strike from that list all periods where none are available.  If everyone is available in at least one of the remaining periods, then all students can be accommodated.  Otherwise it's not.

One way to do this is simply hold tutorials in each of those remaining periods.  However, professors have many responsibilities besides teaching ("publish or perish" and all that), so it's desirable to use the fewest tutorial periods possible.  So how can we do that?

It turns out that this is an application of a well studied problem in combinatorics, known as the set cover problem.  Suppose we are given a collection of sets, say $S_1,S_2,\ldots, S_k$.  Let $U=\cup_{i=1}^k S_i.$  Suppose that $I$ is a subset of $\{1,2,\ldots,k\}$ and $U=\cup_{i\in I}S_i$.  Then $I$ is called a {\em set cover} of $U$.  The set cover problem is to minimize the size of $I$.

Now, suppose that the periods are numbered $1,2,\ldots, k$.  For each $i$, let $S_i$ be the set of students who are available during period $i$.  Then the we can find the fewest tutorial periods needed by finding the smallest set cover of $U$.

Unfortunately, the set cover problem is NP-complete.  The formal definition of what this means takes a fair bit of work to explain, so I won't get into it here (if you're interested, follow the link to the topic in the Wikipedia article on the set cover problem).  In practical terms, though, it means that there is no currently known way to find the smallest set cover efficiently (and there probably won't ever be).  Perhaps the number of students and number of periods is small enough that it is still manageable by computer, or there is some approximation algorithm that will give a near-optimal solution.

Variable x, Ex-variable.

Is the variable $x$ still a variable once a value has been assigned to it?  Because then, $x$ is fixed at the assigned value and can no longer vary, and that which cannot vary is not variable.