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.


1 Answer 1


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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – fedja
    Sep 12, 2010 at 13:57
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 12, 2010 at 15:13
  • $\begingroup$ 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. $\endgroup$
    – fedja
    Sep 12, 2010 at 15:40
  • $\begingroup$ @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/… $\endgroup$ Sep 12, 2010 at 16:58
  • $\begingroup$ 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. $\endgroup$
    – John Jiang
    Sep 13, 2010 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.