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

<p>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&lt;\lambda &lt;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).</p>

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

<p>$$[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$$</p>

<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 $$</p>

<p>Doing the algebra</p>

<p>$$(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]$$</p>

<p>So we have arrived at</p>

<p>$$[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$$</p>

<p>Breaking up and manipulating,</p>

<p>$$[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$$</p>

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

<p>Simplifying $E(n+2)$ from both sides we get</p>

<p>$$-2E(n+1) + E(n) = -\frac{2}{n+1}E(n+1)$$</p>

<p>$$\implies E(n) = \frac {2n}{n+1}E(n+1)$$</p>

<p>and by induction</p>

<p>$$\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)$$</p>

<p>Therefore</p>

<p>$$[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)$$</p>

<p>$$=\frac {n+2 - 4(n+1) + 4n}{2(n+1)}E(n+1) = \frac {n-2}{2(n+1)}E(n+1)$$</p>

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

CC BY-SA 3.0
2015-11-10T18:01:47.510Z
Thanks! This is great. Also, I should comment that although in the context of search $E[n]$ is only defined over the positive integers, the function outside that context is a function over the real numbers. Therefore, convexity can still apply. Then, we can show what we want to show. I've updated my answer to reflect this. That said, I like this proof a lot better!
jmbejara
CC BY-SA 3.0
2015-11-10T16:13:24.580Z
2015-11-10T16:20:58.737Z
2015-11-10T16:20:58.737Z
Alecos Papadopoulos
<p>This is my attempt. As I noted in the question (see the linked question as well), I have my doubts.</p>

<p>We want to show that
\begin{align}
[E(n+2) - E(n+1)] - [E(n+1) - E(n)] &amp;&gt; 0 \tag{1}\\
E[n+2] + E[n] &amp;&gt; 2 E[n+1] \notag \\
\frac 1 2 E[n+2] + \frac 1 2 E[n] &amp;&gt; 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.</p>

<p>We can see that
\begin{align*}
\frac{\mathrm d^2}{\mathrm d n^2} E[n]
  &amp;= 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 \\
  &amp;= \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.</p>

CC BY-SA 3.0
2015-11-10T03:45:32.277Z
2015-11-10T17:57:53.380Z
2015-11-10T17:57:53.380Z
jmbejara
<p>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.</p>

<p>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)] &gt; 0.
$$</p>

<p>I have found a related question <a href="https://stats.stackexchange.com/questions/109432/proving-some-properties-of-expected-first-order-statistics-with-respect-to-sampl">here</a>. However,
this linked question considers the max of arbitrary $n_1 &lt; n_2 &lt; n_3$. Here, I'm
considered only with the statement as it appears in Stigler's article.
Does anybody know how to prove this?</p>

<p>Notes:</p>

<ul>
<li>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?).</li>
</ul>

<probability><information><search-and-matching>
Proof that the diff-in-diff (wrt sample size) of the expectation of a first-order statistic is positive (Stigler 1961)
jmbejara
# Proof that the diff-in-diff (wrt sample size) of the expectation of a first-order statistic is positive (Stigler 1961)

(Asked by: username_0 on 2015-11-10)

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](https://stats.stackexchange.com/questions/109432/proving-some-properties-of-expected-first-order-statistics-with-respect-to-sampl). 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?).

**Tags:** probability, information, search-and-matching

---

## 2 answers

### Answer by username_1 on 2015-11-10. Score: 3

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.

> **Comments:**
> **username_0**: Thanks! This is great. Also, I should comment that although in the context of search $E[n]$ is only defined over the positive integers, the function outside that context is a function over the real numbers. Therefore, convexity can still apply. Then, we can show what we want to show. I've updated my answer to reflect this. That said, I like this proof a lot better!  

---

### Answer by username_0 on 2015-11-10. Score: 0

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.


---

