Progress

It is fair to say, I think, that over the last 40 years or so there has been little progress in the quality of life of the average person in the West, and quite possibly there has been a deterioration. (The only indicator in which there has been steady progress, I think, is longevity.¹)

Progressive ideology generally asserts that there is a wide variety of elements of conceivable and feasible policy and technology that would significantly improve average quality of life. It may be further assumed that the pursuit of any of those elements or any combination of those elements can be expected to be fruitful. To some extent this assumption – what may be termed the “parallel progress assumption” – seems to be implicit in much of present-day progressive activism: the agenda is usually very eclectic and often somewhat vague on specifics. While this is partly a tactic that is aimed at maintaining wide appeal, there is also the implication that as long as general principles are agreed to, laying out a detailed workplan is not necessary since progress can be made on any of many items quite independently of each other. While I accept the progressive assumption (i.e., that progress is possible) it appears to me that the parallel progress assumption is incorrect.

Deviations from the mean of a sum of independent, non-identically-distributed Bernoulli variables, continued

Continuing the investigation initiated here, and applying the same notation.

Proposition 2:

For every l, l >= ES, P(S ≥ l) is maximized when q₁ = ··· = q_n-mz = q = ES / (n – m_z), and q_{n – mz} + 1 = ··· = q_n = 0, for some m_z.

That is, in the terminology of Proposition 1, for all non-trivial cases, m_o = 0, and thus the probability of deviation is maximized by some Bernoulli variable (rather than a shifted Bernoulli variable).

Deviations from the mean of a sum of independent, non-identically-distributed Bernoulli variables

Let B_i, i = 1, …, n be independent Bernoulli variables with parameters q_i, i = 1, …, n, respectively. Let S be their sum. For convenience, assume q₁ ≥ q₂ ≥ ··· ≥ q_n. I wish to bound tightly from above the probability that S is greater or equal to some l, having the bound depend solely on ES = q₁ + ··· + q_n.

Clearly, if l ≤ ES, then the tightest bound is 1. This is attained by setting q₁ = ··· = q_l = 1.

This example shows that while the variance of S is maximized by setting q_i = ES / n, i = 1, ···, n, at least for some values, l, P(S ≥ l) is maximized by having the B_i not identically distributed.

Proposition 1:

For every l, P(S ≥ l) is maximized when q₁ = ··· = q_mo = 1, q_mo+1 = ··· = q_n-mz = q, and q_n-mz+1 = ··· = q_n = 0, for some m_o and m_z, and for q = (ES – m_o) / (n – m_o – m_z).

Proof:

Assume that 1 > q_i > q_j > 0. Let S’ = S – B_i – B_j. Then

P(S ≥ l) = P(S’ ≥ l) + p₁ (q_i + q_j – q_i q_j) + p₂ q_i q_j,

where p₁ = P(S’ = l – 1) and p₂ = P(S’ = l – 2). Thus, keeping q_i + q_j fixed, but varying the proportion between them, P(S ≥ l) is a linear function of q_i q_j. Unless p₁ = p₂, P(S ≥ l) will be increased by varying q_i and q_j – with a maximum either when they are equal or when one of them is zero or one.

Therefore, P(S ≥ l) cannot be at a maximum if there exist 1 > q_i > q_j > 0, unless p₁ = p₂. But in that case, the same probability can be achieved by setting the parameter of B_i to be q’_i = 0 (if q_i + q_j < 1) or q’_i = 1 (otherwise), and the parameter of B_j to be q’_j = q_i + q_j – q’_i. Therefore, in that case, there would exist a set of parameters, q’₁, …, q’_n, that would achieve that same probability but with fewer parameters that are not equal to zero or one. Thus, in the set of parameter settings maximizing P(S ≥ l), there exists a solution – namely the one which maximizes the number of parameters with extreme values (zeros and ones) – in which there is only one non-extreme value. ¤

The next step is to investigate which specific parameter setting correspond to various combinations of l and ES.

Terrorism

The pursuit of the definition of “terrorism” has proven to be a formidable task that is personally useful for some. The standard dictionary definition,

the use of violence and threats to intimidate or coerce, especially for political purposes,

clearly conflicts with accepted usage, for if it were believed then any military activity, or even police activity, would constitute a terrorist activity. Other definitions come closer to the intended meaning:

Terrorism is defined as political violence in an asymmetrical conflict that is designed to induce terror and psychic fear (sometimes indiscriminate) through the violent victimization and destruction of noncombatant targets (sometimes iconic symbols). [Attributed by Wikipedia to Carsten Bockstette.]

Obviously, military activity would often fall within those terms if it were not for the “asymmetrical” condition. Such activity, when considered legitimate by the speaker, is never referred to as “terrorism”.

Short story – The Adventures of Sunlight, an unsung girl

Formal analysis

Keynes is rather dismissive of what he calls ‘“mathematical” economics’. The following passage is from chapter 21 of The General Theory:

The object of our analysis is, not to provide a machine, or method of blind manipulation, which will furnish an infallible answer, but to provide ourselves with an organised and orderly method of thinking out particular problems; and, after we have reached a provisional conclusion by isolating the complicating factors one by one, we then have to go back on ourselves and allow, as well as we can, for the probable interactions of the factors amongst themselves. This is the nature of economic thinking. Any other way of applying our formal principles of thought (without which, however, we shall be lost in the wood) will lead us into error. It is a great fault of symbolic pseudo-mathematical methods of formalising a system of economic analysis, such as we shall set down in section vi of this chapter, that they expressly assume strict independence between the factors involved and lose all their cogency and authority if this hypothesis is disallowed; whereas, in ordinary discourse, where we are not blindly manipulating but know all the time what we are doing and what the words mean, we can keep “at the back of our heads” the necessary reserves and qualifications and the adjustments which we shall have to make later on, in a way in which we cannot keep complicated partial differentials “at the back” of several pages of algebra which assume that they all vanish. Too large a proportion of recent “mathematical” economics are mere concoctions, as imprecise as the initial assumptions they rest on, which allow the author to lose sight of the complexities and interdependencies of the real world in a maze of pretentious and unhelpful symbols.

There is much truth in the above, I think, and it is truth that applies not only to “economic thinking” but to any kind of thinking that relies on formalization. Statistical analysis is plagued with this kind of problems. Keynes does lay too much stress on the matter of interaction between factors. The problem with formal methods is not particularly with neglecting various effects – it is that they simply are false in various ways (neglecting various effects is only one of the sources of falsehoods). Informal methods have the same problem, of course – and in addition have problems associated with informality.

A short mathematical description of Keynes’s general theory

Party affiliation and general outlook 1991-2011

The proportions of Americans who are politically affiliated with one of the two major parties has been very stable over the last 20 years, at about 60% with a slight downward trend (+ marks and thick trend line in the chart below). Over the same period, the general outlook of the public has fluctuated wildly, with those who say the country is “going in the right direction” reaching over 50% at one point and falling 5 years later to 20% (circles and thin trend line). The public mood seems to be optimistic immediately following presidential elections (vertical dashed lines), and pessimistic immediately before them.

Data source: New York Times/CBS poll, April 15-20, 2011.

Sliding window statistics calculation complexity

The following C++ code takes a sequence of n elements, a₁, a₂, …, a_n, and outputs a sequence of n – k + 1 elements. The i-th output element is a maximal element in the subsequence a_i, a_{i + 1}, …, a_{i + k – 1}. The runtime complexity of the code is O(n).

template <typename T>
void insert(std::list< std::pair<T,unsigned int> > &l, T v)
{
    unsigned int sp = 0;
    while (!l.empty() && l.back().first < v)
    {
        sp++;
        l.pop_back();
    }
    l.push_back(std::pair<T,unsigned int>(v,sp));
}

template <typename T>
void advance(std::list< std::pair<T,unsigned int> > &l)
{
    if (l.front().second > 0)
        l.front().second--;
    else
        l.pop_front();
}

template <typename T>
void max_in_window(T const *in, T *out, size_t n, size_t k)
{
    std::list< std::pair<T,unsigned int> > l;
    unsigned int i;
    for (i = 0; i < k - 1 && i < n; i++)
        insert(l,in[i]);

    for (; i < n; i++)
    {
        insert(l,in[i]);
        out[0] = l.front().first;
        out++;
        advance(l);
    }
}

Interestingly, an algorithm for the median in a sliding window will have runtime of at least O(n log k), since such an algorithm can be used to sort O(n / k) sequences of length O(k) each:

Let a₁, a₂, …, a_n be a sequence of numbers in a known interval, say (0, 1). Create a sequence of length 3n – 2 by padding the sequence with a prefix of (n – 1) 0‘s and a suffix of (n – 1) 1‘s. Now execute the sliding window median algorithm with the padded sequence as input, and with k = 2n – 1.

The i-th output element will be the median of a sequence that is made of the entire sequence a₁, a₂, …, a_n, n – i zeros, and i – 1 ones. That median is a_(i), the i-th smallest elements of the sequence a₁, a₂, …, a_n. Thus, the output of the algorithm will be the sorted sequence a₍₁₎, a₍₂₎, …, a_(n).

Introduction to, and some problems in, Probability and Statistics