Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
What a nice question. –  Louigi Addario-Berry Sep 12 '10 at 11:43
add comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
1  
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 '10 at 13:57
1  
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 '10 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 '10 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 '10 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 '10 at 5:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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