[ps1] 3.4, proper application of the CLT

1 files changed, 51 insertions, 20 deletions

diff --git a/ps1/main.tex b/ps1/main.tex
index 5dfca98..5ee2ece 100644
--- a/ps1/main.tex
+++ b/ps1/main.tex
@@ -315,40 +315,71 @@ And the payments can be computed using \cref{eq:pay} and the fact that $\phi^{-1
 \end{equation}
 
 
-\item Finally, we want to give an asymptotic expression for the expected revenue for the revenue-optimal mechanism, with all of the agents' values i.i.d. from $U[0,1].$
+\item Finally, we want to give an asymptotic expression for the expected
+    revenue for the revenue-optimal mechanism, with all of the agents' values
+    i.i.d. from $U[0,1].$
 \begin{displaymath}
-    \E[\text{revenue}] &= \E\left[\sum_i p_i\right] = \E\left[\sum_i\phi_i(v_i)x_i(v_i)\right]
-= \E\left[I_p\sum_i\phi_i(v_i)\right]
+    \E[\text{revenue}] = \E\left[\sum_i p_i\right] 
+    = \E\left[\sum_i\phi_i(v_i)x_i(v_i)\right]
+    = \E\left[I_p\sum_i\phi_i(v_i)\right]
 \end{displaymath}
-where $I_p$ is the random indicator variable of the auction being allocated, that is, $I_p=1$ iff $\sum_i v_i\geq \frac{n}{2}$. Using \cref{eq:pay2}:
-
+where $I_p$ is the random indicator variable of the auction being allocated,
+that is, $I_p=1$ iff $\sum_i v_i\geq \frac{n}{2}$. Hence:
 \begin{equation}\label{eq:rev}
-\E[\text{revenue}] = \E\left[I_p\sum_i p_i\right] 
-    = \E\left[ I_p\sum_i(2v_i-1)\right]
-    = 2\E\left[I_p\sum_i v_i\right] - n\E[I_p]
+\E[\text{revenue}]
+= \E\left[ I_n\sum_{i=1}^n(2v_i-1)\right]
+= 2\E\left[I_n\sum_{i=1}^n v_i\right] - n\E[I_n]
 \end{equation}
 
 Now observe that:
-\begin{displaymath}
-    \E[I_p] = \Pr\left[\sum_i v_i\geq\frac{n}{2}\right] = \frac{1}{2}
-\end{displaymath}
+\begin{equation}\label{eq:prob}
+    \E[I_n] = \Pr\left[\sum_{i=1}^n v_i\geq\frac{n}{2}\right] = \frac{1}{2}
+\end{equation}
 Since $\sum_i v_i$ is a symmetric random variable centered at $\frac{n}{2}$.
 
-Now we have to compute $\E\left[I_p\sum_i v_i\right]$. It is hard to obtain a closed-form formula, but we can obtain an asymptotic approximation when $n$ goes to infinity by observing that the sum of iid variables behaves like a normal distribution in the limit. This can be made formal by applying the central limit theorem: if we substract the mean and multiply by $n\sqrt{n}$ we should obtain a constant in the limit. We obtain:
+Now we have to compute $\E\left[I_n\sum_{i=1}^n v_i\right]$. It is hard to
+obtain a closed-form formula, but we can obtain an asymptotic approximation
+when $n$ goes to infinity by observing that the sum of iid variables behaves
+like a normal distribution in the limit. This can be made formal by applying
+the central limit theorem. Let us define:
+\begin{equation}\label{eq:xn}
+    X_n\eqdef \frac{1}{\sqrt{n}}\left(\sum_{i=1}^n v_i - \frac{n}{2}\right)
+\end{equation}
+By the central limit theorem, $X_n$ converges in distribution:
 \begin{displaymath}
-    \E\left[I_p\sum_i v_i\right] = \frac{n}{4} + O\left(\frac{1}{n\sqrt{n}}\right)
+    X_n\stackrel{d}{\rightarrow} X\sim\mathcal{N}\left(0,\frac{1}{12}\right)
 \end{displaymath}
-Coming back to \cref{eq:rev} we get:
+Note that:
 \begin{displaymath}
-    \E[\text{revenue}] = \frac{n}{2} -\frac{n}{2} +O\left(\frac{1}{n\sqrt{n}}\right) = 
-O\left(\frac{1}{n\sqrt{n}}\right)
+    \E\left[I_nX_n] = \E\left[h(X_n)\right]
 \end{displaymath}
-Asymptotically, we see that the revenue goes to zero and behaves like $\frac{1}{n\sqrt{n}}$.
-
-
-
+where $h(x) = \mathbf{1}_{x\geq 0}$ is the indicator function of $x$ being
+non-negative. Using convergence in distribution:
+\begin{equation}\label{eq:conv}
+    \E[h(X_n)] \rightarrow \E[h(X)]
+\end{equation}
+It is easy to compute $\E[h(X)]$ directly:
+\begin{equation}\label{eq:lim}
+    \E[h(X)] = \sqrt{\frac{6}{\pi}}\int_0^{+\infty}x e^{-6x^2}dx
+    = \frac{1}{12}\sqrt{\frac{6}{\pi}}= \frac{1}{2\sqrt{6\pi}} \eqdef c
+\end{equation}
+\cref{eq:xn,eq:conv,eq:lim} together give:
+\begin{displaymath}
+    \E[h(X_n)] = \frac{1}{\sqrt n} \E\left[I_n\sum_{i=1}^n v_i\right]
+    - \frac{1}{\sqrt{n}}\frac{n}{4}\rightarrow c
+\end{displaymath}
+Hence as $n$ goes to infinity:
+\begin{equation}\label{eq:asymp}
+    \E\left[I_n\sum_{i=1}^n v_i\right] = \frac{n}{4} + c\sqrt{n} + o(\sqrt{n})
+\end{equation}
 
+\cref{eq:rev,eq:prob,eq:asymp} together give:
+\begin{displaymath}
+    \E[\text{revenue}] = \frac{n}{2} + 2c\sqrt{n} + o(\sqrt{n}) - \frac{n}{2}
+    = 2c\sqrt{n} + o(\sqrt{n})
+\end{displaymath}
 
+As the number of agents goes to infinity, the revenue is $O(\sqrt{n})$.
 \end{enumerate}
 
 \end{document}