\documentclass{article}
\include{macros}

\begin{document}
% lecture number : lecture title : scribe

%\include{macros.tex}
\lecture{8}{Matching Poisson Processes}{Ben Hough}{jbhough@math.berkeley.edu}

\section{Two color matching}

Consider the problem of matching two independent Poisson(1) point processes in 1 dimension (call the points black and red).  We obtain a deterministic and invariant matching algorithm by iteratively matching and removing all pairs of consecutive black and red points where the black point is positioned immediately to the left of the red point.  To understand the efficiency of this matching, we assume, without loss of generality, that the black Poisson process contains a point $x$ at the origin and ask for the probability that this point is not matched within distance $R$ from the origin.  This probability may be computed as follows.  Define a simple random walk $S_k$ where $S_0 = 0$ and $S_k = S_{k-1}+1$ if the $k^{th}$ point from the origin is black, and $S_k = S_{k-1}-1$ if the $k^{th}$ point from the origin is white.  Then we have

\begin{eqnarray*}
\P(x \textrm{ does not get matched within } n \textrm{ next points}) &=& \P(1 + S_k >0 \textrm{ for }k=1,2,\dots,n)\\
&\sim& \frac{c}{\sqrt{n}}
\end{eqnarray*}

>From this fact one can deduce

\begin{exercise} ($\star$)
\begin{equation}
\P(x \textrm{ is not matched within dist }R) \sim \frac{1}{\sqrt{R}}.
\end{equation}
\end{exercise}

\begin{exercise} ($\star$)
Show that for any invariant matching $\E R_0^{1/2} = \infty$ where $R_0$ is the matching distance for the point at the origin.  
\end{exercise}

\begin{exercise} ($\star$) \label{MINM}
For the mutual iterated nearest neighbor matching starting with a black point at the origin, prove that there exists $c>0$ so that
\begin{equation}
\P(R_0>r) \leq r^{-c}
\end{equation}
\end{exercise}

\begin{exercise}($\star \star \star$)
Show that the statement in Exercise \ref{MINM} holds with $c = \frac{1}{18}$.
\end{exercise}

To prove the statement in exercise \ref{MINM} one may proceed as follows:

\begin{itemize}
\item[Step 1:] Show that a black point $x$ and a red point $y$ cannot be matched if the number of black points between $x$ and $y$ does not equal the number of red points.

\item[Step 2:]Define a simple random walk $S_k$ so that $S_0 = 0$ and $S_k = S_{k-1}+1$ if the $k^{th}$ point to the right of the origin is black, and $S_{k} = S_{k-1}-1$ otherwise.  Assume that a black point $x$ lies at the origin and let $R_0$ denote the number of points crossed by the matching interval for $x$.  Assuming that $S_j<0$ for $n \leq j \leq 2n$, conclude that $R_0<n$.

\item[Step 3:]  Show that for simple random walk:  
\begin{equation}
\P(\forall k \leq n, \exists j \in [k,2k], S_j \geq 0) \leq n^{-c}.
\end{equation}

\end{itemize}

\section{One color matching}

\begin{theorem}$ $
\begin{itemize}
\item[(a)]  For any measurable invariant deterministic matching in $d=1$ we have $\E R_0 = \infty$.
\item[(b)]  Conversely, for all $d$, the mutual iterated nearest neighbor matching satisfies $\P(R_0>r) \leq \frac{C_d}{r^d}$.
\end{itemize}
\end{theorem}
\begin{proof}[Proof of (b), (Pemantle):]

Call a point $x$ of the Poisson process $r${\it -bad} if $R_x>r$.  Using the fact that any two $r$-bad points are separated by distance at least $r$, we obtain:
\begin{eqnarray}
\P(R_0>r) &=& \frac{\E(\# r\textrm{-bad points in } [-n,n]^d)}{(2n)^d} \\
&\leq& \frac{(n+r/2)^d/(V_d(r/2)^d)}{n^d},
\end{eqnarray}
where $V_d$ is the volume of the $d$-dim unit ball.  Taking the limit as $n \rightarrow \infty$ we find that
\begin{equation}
\P(R_0>r)  \leq \frac{2^d}{V_d (r^d)}.
\end{equation}
\end{proof}
\begin{proof}[Proof of (a):]$ $ 

\begin{itemize}
\item[Step 1:] 
{\bf Claim:}  A measurable, invariant and deterministic even-odd matchings cannot exist.  To see this, consider the set $I = [-6L,-4L] \cup [-L,L]$.  Assuming that a measurable, invariant and deterministic even-odd matching exists, then taking $L$ sufficiently large we can with arbitrarily large probability determine the matching on $I$ (except for boundary points) by observing only the points in $I$.  But this assertion is clearly false, since by observing only the points in $I$ we cannot know whether the number of points in the interval $[-4L,-L]$ is even or odd.

\item[Step 2:]  
{\bf Claim:}  For any measurable, invariant, deterministic matching, the matching intervals cover $\R$ almost surely.  If there exist uncovered points, then ergodicity implies that the uncovered points must have positive density.  Since the number of points in the Poisson process that lie between any two uncovered points must be even, the existence of uncovered points provides a way to construct a measurable, invariant, deterministic even-odd matching which cannot exist.

\item[Step 3:]  
{\bf Claim:} Almost surely, no point in $\R$ is covered only finitely many times by matching intervals.  The argument is the same as before:  if there exists a point covered by exactly $k$ matching intervals, then such points must occur with a positive density.  But the number of Poisson points that can lie between two such points is necessarily even and hence the existence of such points allows for the construction of a measurable, invariant and deterministic even-odd matching.

\item[Step 4:]
For $x,y \in \Z$, set 
\begin{equation}
m(x,y) = \E(\# \textrm{ points in } (x-1/2,x+1/2) \textrm{ whose matching inverval covers } y).
\end{equation}
Claim 3 implies that $\sum_{x} m(x,y) = \infty$, and invariance gives $m(x+j,y+j) = m(x,y)$.  It follows that $\sum_y m(x,y) = \infty$.
Since the expected number of Poisson points in $[x-1/2,x+1/2]$ is finite, this completes the proof.

\end{itemize}
\end{proof}

\end{document}