This is a problem via fakalin.

You have 10 pieces of string, each with two ends. You randomly pick two ends of string (possibly from the same string, possibly from different ones) and tie them together, creating either a longer piece of string or a loop. You keep doing this until you run out of free ends.

What is the expected number of loops you end up with?

(Read the article)

Comments(0)

The Roland line of “SuperNATURAL” digital pianos claims to produce a more natural sound by combining the two primary methods of synthesizing instruments, namely: acoustic modeling of real instruments, and recording samples from them. The two methods are different enough that, even if both converge to the true output as more sophistication is put to bear, they are rather difficult to merge together.

The history of synthesized instruments has ping-ponged between the two methods. First there was FM synthesis, which used analog function generation based on the simplest physical models of standing waves (harmonics, etc.). This allowed distinguishing between major instrument groups but sounded decidedly fake. Then people recorded acoustic instruments and looped/interpolated between samples — much better, but storage constraints placed limits on what could be processed; and there was never any dynamism. Then it was back to physical modeling, this time using waveguides to determine how various inputs like bowing on strings or blowing into pipes dynamically affect output sound (I think it started at CCRMA). This gave really good expressivity — but again sounded fake. And so back to wave-samples. For the last 15 years or so, especially with the cheapening of storage, it appears that the dumbest, brute-force method of using a large enough number of samples and ad-hoc adjustments to their decay and reverb characteristics became dominant. For ensemble instruments with little individual personality, it was actually superb. The trouble was always with instruments in solo.
(Read the article)

Comments(0)

When one is presented with some subject on which there are several viewpoints, and exhorted to look at things “dialectically,” one might ask what this means.

Wikipedia says of classical dialectic that the point is to generate either a refutation of one viewpoint or a synthesis — to reach a better conclusion. But it doesn’t say what form the better conclusion is in. Similarly, it says of Hegelian dialectic that the point is to reach a synthesis by combining the common points of a thesis and an antithesis.

These models of truth-finding appear to be rather limited. Besides the fact that in some sense they are specialized to dual or opposing viewpoints numbering two (or even if we extend it, a finite number), they are restricted to finding truth only in the intersection or union or some other simple-minded method of synthesis. I argue for a more general way to model truth-finding. This is inspired by engineering, as usual.
(Read the article)

Comments(0)

Where to Live to Avoid a Natural Disaster
Weather disasters and quakes: who’s most at risk? The analysis below, by Sperling’s Best Places, a publisher of city rankings, is an attempt to assess a combination of those risks in 379 American metro areas … and take(s) into account the relative infrequency of quakes, compared with weather events and floods.

I don’t know what exact metric they used here but it seems to be more or less expected value of “disaster points” accumulated during a unit period, for the lack of a better description. Here is the problem with these expected value based metrics, trying to summarize very different distributions: the variance matters! One catastrophic disaster isn’t quite the same as several smaller disasters costing the same number of disaster points. Yet “maximizing” survival using this map, humanity moves to the West Coast then becomes extinct in the next big earthquake. Even imposing a convex utility function on the distribution isn’t entirely satisfying. When it comes to decision making, tail risk is in a different bucket than central risk. Somehow an important aspect of the decision making process isn’t captured by “soft” metrics.
(Read the article)

Comments(0)

Consumer broadband modems and routers typically cannot deal with a large number of connections from multiple users, and the cheap firmware has no settings to restrict the bandwidth of each user. This is when you resort to the physical layer to help you out.

Solution: Restrict wifi to the really slow 802.11b, maybe even slower, and let the physical layer radio contention fake the effects of fair bandwidth control. Works like a charm, no more dropped connections.

Comments(0)

The latest problem from fakalin. Took some wrong turns and hints to solve it…

Given a polynomial \(f: \mathbb{Z}\to \mathbb{Z}\) with positive integer coefficients, how many evaluations of \(f\) does it take to obtain the polynomial?

(An \(f: \mathbb{R}\to \mathbb{R}\) polynomial with real coefficients would take the number of degrees plus 1 to specify, which, if it held in this case, would render the answer unbounded. But the correct answer in this case is surprisingly small.)
(Read the article)

Comments(0)

The classic coupon collector’s problem asks for the number of samples it takes to collect all coupon types from a sequence of coupons in which each of the \(k\) types of coupons has an unlimited number of copies.

Here is a different kind of problem: if there are limited copies of each of the \(k\) coupon types (say, \(d\) copies), how many samples does it take to collect \(t\) coupon types?

(Read the article)

Comments(0)

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)

Comments(0)

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.

Comments(0)

It is said that 8 perfect shuffles of a standard deck of 52 cards results in an unshuffled deck. Why is that? Is it true only for 52 cards? What kind of shuffle is implied by this statement? Yesterday, we (high school math buddies) made pretty good sense of it.
(Read the article)

Comments(2)