Blog Archives

wire matching problem

Here’s an interesting and, shall I say, practical problem brought up at group meeting today: If you have say, n identical looking wires strung across a long distance between point A and point B, and your job is to label all wires with just an ohm-meter (to measure continuity, i.e. short circuit or open circuit), how many trips between A and B does it take?

Indeed, the only way to use an ohm-meter for this purpose is by tying wires together. Clearly the number of trips shouldn’t be larger than \(\log n\) or so, simply by tying various halves of the set of wires at one end and going to the other end to measure. But there are other kinds of coding that do better.
(Read the article)

double log convergence

Here is a problem on complexity, or alternatively, convergence.

If an integer \(n\) is reduced by the largest square less than it each time until it is terminated at zero, show that the number of steps taken is at most order \(\log \log n\).

More precisely, let \(f(n) = n – {\left\lfloor{\sqrt{n}}\right\rfloor}^2\) and \(g(n)=k\) be the minimum number of steps until \(f^k(n)=0\). Prove that there exists some fixed \(A\) such that \(g(n)< A \log \log n\) for all \(n\ge 3\).
(Read the article)

biometric authentication

Now that I have gotten seriously addicted to Tablet PC (the faux paper templates in Windows Journal alone were enough to get me hooked), I’ve been pondering about some limitations of the platform. One is authentication. One of things you are not happy to do with a mouse — which the pen is, sort of — is inputting random strings that have become of modern-day passwords.

So I understood the point of the fingerprint reader option on this build. Swipe and you can bypass having to type passwords in tablet mode when the keyboard is hidden. But I didn’t get the option, and I believe there are other alternatives.

There are many modes of biometric authentication, fingerprint, face recognition, handwriting, voice, etc., and getting nearly perfect reliability in each case is a difficult problem when used alone. State of the art is just not good enough. But combined into a multifactored authentication protocol, it may just work. Here is something that should work today with existing hardware:

Look into the webcam, solve a quick reflexive cognition problem, and provide a handwriting sample.

That should do the trick for a quick keyboard-less authentication. Why hasn’t anybody written software to do this?

uniform by three

Here is a problem recently described to me. Apparently there is a more elegant solution (which may give more insight), but I don’t see it yet.

The problem: \(X, Y, Z\) are independent random variables uniformly distributed over [0,1]. What is the distribution of \((XY)^Z\)?
(Read the article)

Polya’s urn, martingale, CLT

A problem described here

what do you expect to happen if you had 2 urns with a ball in each one…. and you placed balls in them…. choosing an urn with a probability proportional to the number of balls in each urn…..

intuitively, you’d expect a rich getting richer kind of thing….. or those with more balls getting even ballsier…. [see extreme sports.... those ppl are crazy... and get crazier] but the amazing thing is that you get a uniform distribution….. it’s not even a distribution that peaks at the two ends where there’s 1 ball and n-1 balls in the other….

Well, it’s not that counter-intuitive. Certainly, if you begin with exactly 1 ball in each urn, you end up with a uniform distribution on all outcomes, but the uniformity is kind of an artifact. In fact, the proportion of total balls in one designated urn is a martingale process, which means the proportion of balls at any number of times steps later is expected to be the same as the starting proportion. So, if you do not start with an equal number of balls in the two urns, there is no way that the long-run outcome will be uniformly distributed across the possibilities because that would give a mean proportion value of 1/2.

Furthermore, this means that indeed there is a rich getting richer “kind of thing” going on, if you deviate from equal proportion by chance. This is a weak effect that happens when the balls are few, but it doesn’t mean that the half-half case is somehow a counter-intuitive stable system. The paths that deviate early will indeed tend to go to the rails. It’s just that there are so many central paths that you aren’t likely to deviate proportionally unless it happens early.

What’s more interesting is that there are so many central paths. If you began with 2 and 2 balls, or 10 and 10 balls, you don’t get uniform outcomes, but a centrally peaked distribution around equal proportions. Indeed, if the number of balls is large, then addition of balls to urns one at a time doesn’t even move the drawing probabilities given by existing balls, and so it is reasonable to expect something like the central limit theorem to kick in.

So this is a case of deviation instability fighting with central tendencies of large numbers. To see this, keep the total number of balls the same, and move balls from the urn not chosen to the urn chosen, instead of adding balls to the urn chosen (and hence remove the latter cause from the “fight”), then it will clearly go to the rails.

another combinatorial puzzle (allocation)

Well, the original problem was X-rated, so let me recast it.

Three surgeons (A, B, C) participate in an operation involving three patients (a, b, c). For simplicity, each surgeon operates with just one hand, and operates just once on each patient. There are a bunch of sterile surgical gloves that stop contamination from one side to the other. What’s the minimum number of gloves needed to ensure that no body part ever comes into contact with another, even indirectly? Note, surgeons do not want to contaminate each other either.

Clearly, the upper bound is 9, for the 9 pairings. The lower bound is 3, for the 3 patients, or alternatively the 3 surgeons. Is the answer something in between?
(Read the article)

Today I became suspicious of Seagate products (part 1)

This is part of the hard disk recovery documentation.

Part 1.


Today I became suspicious of Seagate products (and my fortune in general)

Windows XP was running, and programs were being used. The disk was probably being accessed for memory cache. I noticed the drive making repetitive noises, spinning down and then spinning up, and the machine became unusable. I power-cycled the machine, and it was “NTOSKRNL.EXE is missing or corrupt.” Bad news.
(Read the article)

Dom sovetov

Note: This is an anti-causal post, because the writing existed before this blog thing here.

Well, well, well, so Konigsberg of East Prussia became Kalinigrad of the USSR after World War II. Konigsberg was famous for the 7 bridges problem often assoicated with Euler, of course.

According to Wikipedia,

In the Soviet part of the region (note: i.e. former East Prussia) a policy of eliminating all remnants of German history was pursued. In 1967 this resulted in the demolition of the remains of Königsberg Castle by order of Leonid Brezhnev to make way on the site for the new “House of Soviets”.

In other words, Brezhnev dynamited this

Konigsberg Castle

http://upload.wikimedia.org/wikipedia/commons/thumb/b/ba/K%C3%B6nigsberg_Castle.jpg/440px-K%C3%B6nigsberg_Castle.jpg

To make room for this

House of Soviets (Dom Sovetov)

http://upload.wikimedia.org/wikipedia/commons/thumb/0/09/Dom_sovetov.jpg/436px-Dom_sovetov.jpg

Was the architect of the House of Soviets a robot, who modeled the building after its own face? Dom sovetov indeed. Har har.

« Previous Page