Tag Archives: Grad School

contradiction injunction

Posted on by

I came across the following in Royden’s Real Analysis:

All students are enjoined in the strongest possible terms to eschew proofs by contradiction!  There are two reasons for this prohibition : First, such proofs are very often fallacious, the contradiction on the final page arising from an erroneous deduction on an earlier page… Second, even when correct, such a proof gives little insight into the connection between A and B, whereas both the direct proof and the proof by contraposition construct a chain of argument connecting A with B.  One reason that mistakes are so much more likely in proofs by contradiction than in direct proofs or proofs by contraposition is that in a direct proof (assuming the hypothesis is not always false) all deductions from the hypothesis are true in those cases where the hypothesis holds, and similarly for proofs by contraposition (if the conclusion is not always true), the deductions from the negation of the conclusion are true in those cases where the conclusion is false.  Either way, one is dealing with true statements, and one’s intuition and knowledge about what is true help to keep one from making erroneous statements.  In proofs by contradiction, however, you are (assuming the theorem is true) in the unreal world where any statement can be derived, and so the falsity of a statement is no indication of an erroneous deduction.

This impassioned attack reminds me of Ionesco’s The Lesson or Stoppard’s Jumpers.  It’s tempting to psychoanalyze Royden and say that he must have an irrational fear of an unreal “make-believe” world or an overwhelming need to have certainty and truth.  But that’s just silly, isn’t it?

a paper a day : neuron polarity

Posted on by

I’ll keep ’em shorter from now on I think.

A probabilistic model for the establishment of neuron polarity
Kostya Khamin and Raya Khamin
J. Math Biol. 42, 26-40 (2001)

This paper seeks to answer a puzzling question in neuron developent — why does only one neurite (site on the neuron) out of many on a neuron grow into an axon? The answer they have lies in a particular kind of inhomogenous Markov chain or random walk that has also been called a “balls-in-bins process with feedback.” This kind of model has also been used in analyzing competitive scenarios in other fields as well as preferential attachment models for networks. They model neurites as bins and the length as the number of balls in a bin.

The basic model is this: suppose we have k bins which contain balls. Let a(t) be a length k vector whose entries are the number of balls in the bins at time t, and let f(n) be function that we will call the value of having n balls. At each time, a ball is added to one of the bins at random. The probability that
bin j is chosen is:

That is, the probability is equal to the value of bin j over the sum of the values of all the bins.

In this paper they look at value functions of the form

and show that there are three regimes of behavior:

  • Critical regime (p = 1) : all bins grow linearly with time, but there is one winner.
  • Ballistic growth (p > 1) : after a certain time, only one neurite grows. Another way of viewing this is all but finitely many balls will end up in one bin.
  • Subcritical + winner (1/2 < p < 1) : In this case the ratio of the number of balls in any two bins tends to one. So they all grow linearly, but if b(t) = a(t) – t/k is the fluctuation around the linear growth, then

    That is, the flucations are on the order of f(n). The bin with the largest c_j will always be leading.

  • Subcritical (0 < p <= 1/2) : In this case there is no leader. That is, for each bin there exists an infinite sequence of times for which that bin is the leader. The flucations, appropriately normalized, tend to be Gaussian. That is, some sort of central limit behavior kicks in.

In order to prove these cool and weird results, they embed the arrival process of balls in each bin into a sum of exponential random variables whose rate changes over time (according to how many balls are in the bin). That is, if a bin has r balls, the rate of the next term in the sum is f(r). The bin whose exponential random variable is smallest gets the next ball — the min operation on exponential random variables gives the probability ratio above. That is, the probability that the smallest exponential random variable was the j-th one is exactly that probability above. Thus the probability distribution for the number of balls is identical for the discrete-time model as well as the continuous time embedding. Once they have the embedding it’s a bunch of other tricks to get the results in nice form.

A more recent paper by Oliveira has a nice extension of these arguments for more general f(n) by approximating the embedding with Brownian Motion. As it turns out, the critical thing to check is the summability and square summability of 1/f(n).

gossip and geographic routing

Posted on by

Having opening night for a play at the same time as a conference paper deadline is somewhat killer, but everything seems to have turned out well:

Geographic Gossip : Efficient Aggregation for Sensor Networks
A.G. Dimakis, A.D. Sarwate, and M.J. Wainwright

Gossip algorithms for aggregation have recently received significant attention for sensor network applications because of their simplicity and robustness in noisy and uncertain environments. However, gossip algorithms can waste significant energy by essentially passing around redundant information multiple times. Specifically, for realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is caused by slow mixing times of random walks on those graphs. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing a simple resampling method, we can demonstrate substantial gains over previously proposed gossip protocols. In particular, for random geometric graphs, our algorithm computes the true average to accuracy $1/n^a$ using $O(n^{1.5}\sqrt{\log n})$ radio transmissions, which reduces the energy consumption by a $\sqrt{\frac{n}{\log n}}$ factor over standard gossip algorithms.

call numbers

Posted on by

The Library of Congress prefix for the Bible is “BS.” So BS75.xxx is the Bible in Latin, and so on. Although it probably stands for “Biblical Studies” or something, it still made me giggle when I was in the Graduate Theological Union library today.

but where will I read?

Posted on by

The Morrison Reading Room is closed during intersession, 8/14-8/29. Reading outside is fun and all, but that place can’t be beat for a chapter of a novel and a 30 minute nap in the middle of the day. Lately I’ve been struck by terrible midday lethargy and I can’t get myself to focus on work, so I sometimes trundle down there for a change of scene. Now I’ll just have to drink more coffee.