## Is the nearest walk to Brownian motion uniform?

Let $W:[0,1]\rightarrow\mathbb R$ be standard Brownian motion with $W(0)=0$.

Let $F_n$ denote the collection of all the $2^n$ many piecewise linear continuous functions $f:[0,1]\rightarrow\mathbb R$ such that $f(0)=0$ and $f$ is linear with slope $\pm \sqrt{n}$ on the intervals $[\frac in,\frac{i+1}n]$ for $0\le i<n$.

Let $\psi_n$ denote a uniformly randomly chosen element of $F_n$, i.e., $\mathbb P(\psi_n=f)=2^{-n}$ for each $f\in F_n$.

Let $\phi_n$ denote a uniformly randomly chosen element of $$\text{arg min}_{f\in F_n}\left(\sup_{0\le x\le 1}|W(x)-f(x)|\right).$$ In other words, $\phi_n$ is an element of $F_n$ that minimizes the sup-norm distance to $W$. More simply, we can say that $\phi_n$ is a nearest walk to Brownian motion.

Question: Do $\phi_n$ and $\psi_n$ have the same distribution? In other words, is $\mathbb P(\phi_n=f)=2^{-n}$ for all $f\in F_n$? I am mostly interested in the case $n\rightarrow\infty$, but will accept a rigorous answer for $n=2$.

Motivation: Donsker's Theorem says that $\psi_n$ converges weakly to $W$, whereas it is clear that almost surely, $\phi_n$ converges to $W$ uniformly.

EDIT: Here is a follow-up question.

-
What a nice question. – Louigi Addario-Berry Sep 12 2010 at 11:43

My understanding of the question is this:

There is a function $V_n$ that maps the $L^\infty([0,1])$ to the set $F_n$ of $2^n$ piecewise linear functions as defined. $V_n$ gives the Voronoi subdivision, taking each point of the big set to the nearest neighbor of the smaller set.

I believe you're asking whether $V_n$ pushes Brownian measure on $L^\infty$ to uniform measure(?)

This doees not seem plausible, starting with $F_2$, because unlike random walks and Brownian motion, this process has a memory effect.

Think of the provisional grouping of paths into an upper group and a lower group, based on behavior in the interval $[0,1/2]$. The two distributions of positions at time 1/2 are skewed, because of how Gaussian tails decay rapidly. The provisionally upper group has mean $\sqrt 2/2$, but more of them are less than $\sqrt 2/2$ than greater than $\sqrt 2/2$. This means that those that start provisionally up have less than probability .5 to continue upward, more than probability .5 to go down or to switch to down-up, and low probability of switching to down-down. In other words, I believe the Voronoi measure is biased toward paths that end at 0, rather than at $\pm \sqrt 2$.

It should be possible for someone to compute the exact distribution in this case.

-
The words "Voronoi subdivision" make sense only if the cell boundaries have measure zero, which is very far from the truth here. On the other hand, I also think that each of continuum conjectures of this type (why not to look at all the functions that have the distance to $W$ not more than $a$ times the optimal with $a>1$ instead, say) has 0 probability to be true. I'll give it more thought when I have more time. – fedja Sep 12 2010 at 13:57
Cell boundaries have meaure 0. For any two PL paths $\alpha, \beta$, the probability distribution for the the difference of sup distances of $W$ to the pair of paths is a nice, absolutely continuous measure, with computable piecewise-analytic density. (although the first derivative of the density is discontinuous at any value that is the $\pm$distance between parallel segments of $\alpha, \beta$). Therefore, the probability of the difference being 0 is 0. – Bill Thurston Sep 12 2010 at 15:13
That would be true if the paths had no common pieces, which, in our case, they do more often than not. Just look at what happens if two paths have a common piece and their deviation from $W$ is largest inside that piece. – fedja Sep 12 2010 at 15:40
@Bill Thurston: Thanks! I think this settles it. I have posted a follow-up question (how different are the two distributions as $n\rightarrow\infty$) separately: mathoverflow.net/questions/38481/… – Bjørn Kjos-Hanssen Sep 12 2010 at 16:58
The problem seems that the space of PL paths is not Hausdorff under uniform metric. But the choice of $2^n$ paths makes cells well-defined and the boundaries associated with them are indeed measure 0. – John Jiang Sep 13 2010 at 5:39