Proof that the diff-in-diff (wrt sample size) of the expectation of a first-order statistic is positive (Stigler 1961)

Question

I'm trying to prove a claim made in Stigler (1961), "The Economics of Information." This claim has to do with showing that the marginal benefit of making an additional search (e.g., searching an additional store for a lower price) is decreasing in the number of searches.

Let $F$ be the distribution of prices $p$. Then, the expected value of the minimum price after $n$ searches is $$ E(n) \equiv n \int_0^\infty p (1-F)^{n-1} F' \mathrm d p. $$ In the paper, the claim is that $$ [E(n+2) - E(n+1)] - [E(n+1) - E(n)] > 0. $$

I have found a related question here. However, this linked question considers the max of arbitrary $n_1 < n_2 < n_3$. Here, I'm considered only with the statement as it appears in Stigler's article. Does anybody know how to prove this?

Notes:

• I'm note sure if "convex" is the right term here. The linked question and its answer raise some doubts that it is convex in the strict sense of the word. I suppose what I'm after is just the differences in the differences (a weaker condition that convexity?).

Answer 1

Well, you cannot take the derivative of $E(n)$ with respect to $n$, because $n$ is an integer variable.

More generally, you want to prove a property with respect to $n$. The problem you have is that the corresponding domain is not a convex set: say, for $n$ and $n+1$, $0<\lambda <1$, the value $\lambda n + (1-\lambda) (n+1) = n+1-\lambda$ does not belong to the domain since it is not an integer. But if the domain of the function, with respect to the variable you are interested in, is not a convex set, the concept of convexity/concavity is not even defined (perhaps in higher mathematics they have some more nuanced concept to accommodate that).

To determine whether the inequality you want holds, a brute-force algebraic approach is to examine its sign directly: we have

$$[E(n+2) - E(n+1)] - [E(n+1) - E(n)] =\\= (n+2) \int_0^\infty p (1-F)^{n+2-1} F' \mathrm d p \\- 2 (n+1) \int_0^\infty p (1-F)^{n+1-1} F' \mathrm d p\\ +n \int_0^\infty p (1-F)^{n-1} F' \mathrm d p$$

$$= \int_0^\infty p (1-F)^{n-1} F'\cdot\Big[(n+2)(1-F)^2 - 2(n+1)(1-F)+n\Big] \mathrm d p $$

Doing the algebra

$$(n+2)(1-F)^2 - 2(n+1)(1-F)+n \\= n(1-F)^2 + 2(1-F)^2 - 2n(1-F) - 2(1-F) +n \\ = n\Big[(1-F)^2 - 2(1-F) +1\Big] - 2(1-F)F \\ = n [(1-F) -1]^2 - 2(1-F)F = nF^2 - 2(1-F)F = F\Big[nF-2+2F\Big]\\ =F\cdot \Big[(n+2)F-2\big]$$

So we have arrived at

$$[E(n+2) - E(n+1)] - [E(n+1) - E(n)] = \int_0^\infty p (1-F)^n F'\cdot\Big[(n+2)F-2\Big] \mathrm d p$$

Breaking up and manipulating,

$$[E(n+2) - E(n+1)] - [E(n+1) - E(n)] = \\=(n+2)\int_0^\infty p (1-F)^{n+1} F' \mathrm d p \\- \left(\frac{2}{n+1}\right)(n+1)\int_0^\infty p (1-F)^n F'\mathrm d p$$

$$\implies [E(n+2) - E(n+1)] - [E(n+1) - E(n)] = E(n+2)-\frac{2}{n+1}E(n+1)$$

Simplifying $E(n+2)$ from both sides we get

$$-2E(n+1) + E(n) = -\frac{2}{n+1}E(n+1)$$

$$\implies E(n) = \frac {2n}{n+1}E(n+1)$$

and by induction

$$\implies E(n+1) = \frac {2(n+1)}{n+2}E(n+2) \implies E(n+2) = \frac {n+2}{2(n+1)}E(n+1)$$

Therefore

$$[E(n+2) - E(n+1)] - [E(n+1) - E(n)] = $$ $$= \left(\frac {n+2}{2(n+1)} -1\right)E(n+1) - \left( 1- \frac {2n}{n+1}\right)E(n+1) $$ $$= \left(\frac {n+2}{2(n+1)} -1 - 1+ \frac {2n}{n+1}\right)E(n+1)$$

$$=\frac {n+2 - 4(n+1) + 4n}{2(n+1)}E(n+1) = \frac {n-2}{2(n+1)}E(n+1)$$

So $n=1$ is not a search, for $n=2$ we have equality, and for $n\geq 3$ the inequality holds.

Answer 2

This is my attempt. As I noted in the question (see the linked question as well), I have my doubts.

We want to show that \begin{align} [E(n+2) - E(n+1)] - [E(n+1) - E(n)] &> 0 \tag{1}\\ E[n+2] + E[n] &> 2 E[n+1] \notag \\ \frac 1 2 E[n+2] + \frac 1 2 E[n] &> E[1/2 (n+2) + 1/2 n] = E[n+1]. \notag \end{align} Since $$ E(n) \equiv n \int_0^\infty p (1-F)^{n-1} F' \mathrm d p, $$ we see that $E$ is a function from $\mathbb R$ to $\mathbb R$. However, in the context of search, we restrict its domain to positive integers. However, if we show that the unrestricted function $E[n]$ is convex in $n$, it's easy to see that equation (1) is true by Jensen's inequality.

We can see that \begin{align*} \frac{\mathrm d^2}{\mathrm d n^2} E[n] &= 2 \int_0^\infty p F' (1-F)^{n-1} \ln(1-F) \mathrm d p + \int_0^\infty p F' (1-F)^{n-1} [\ln(1-F)]^2 \mathrm d p \\ &= \int_0^\infty p F' (1-F)^{n-1} \ln(1-F)(2 + n \ln(1-F)) \mathrm d p. \end{align*} Now, for sufficiently large $n$, this is positive. Therefore, $E[n]$ is convex in $n$ and we are done.