tag:blogger.com,1999:blog-3722233.post6676383261921810484..comments2022-11-30T20:33:43.467-06:00Comments on Computational Complexity: A natural function with very odd propertiesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3722233.post-64732665365073055462012-09-25T22:51:11.368-05:002012-09-25T22:51:11.368-05:00A correction: I meant as delta goes to 0. A correction: I meant as delta goes to 0. Sashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78574766893494130602012-09-25T17:31:59.566-05:002012-09-25T17:31:59.566-05:00Gasarch,
1-d brownian motion is usually defined a...Gasarch,<br /><br />1-d brownian motion is usually defined as a probability distribution on functions f:R --> R with the following properties:<br /><br />* for any reals x, y, f(x) - f(y) is distributed like a gaussian random variable with mean 0 and variance (x-y)^2<br />* the increments f(x_1) - f(x_2), f(x_2) - f(x_3), etc., for any x_1 < x_2 < x_3, ... are independent<br />* f is continuous with probability 1<br /><br />A classical construction by Levy shows that such things exist. Another classical result is that with probability 1, a function sampled from this distribution is continuous and non-differentiable. <br /><br />Intuitively, the random variable f is a continuous time random walk on the real line: f(t) tells us the position at time t (well, and we have negative times, but let's restrict f to [0, 1) to make this easier). One can get the Brownian motion as the limit of discrete random walks with smaller and smaller steps. I.e. think of a random walk that proceeds in time steps of length delta and at each time i*delta moves to f((i-1)*delta) + N(0, delta) where N(0, delta) is a gaussian with mean 0 and variance delta^2. This defines f at points that are integer multiples of delta. To define f everywhere, interpolate linearly. Now, as delta goes to infinity, f converges to brownian motion in distribution. This in fact happens even if the steps are not guassian but follow any distribution with finite variance. This "central limit theorem" for random walks is the Donsker invariance principle.<br /><br />A great referene is the book by Moerters and Peres: http://research.microsoft.com/en-us/um/people/peres/brbook.pdfSashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55839164430239874862012-08-21T05:58:37.425-05:002012-08-21T05:58:37.425-05:00#2 - iirc any non-empty measure 0 subset of the in...#2 - iirc any non-empty measure 0 subset of the interval without isolated points is Cantor (modulo an increasing continuous map of the interval). Being essentially unique makes it natural, I'd say.Boris Borcichttps://www.blogger.com/profile/05869004550299424489noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12054602002598126632012-08-08T02:18:48.283-05:002012-08-08T02:18:48.283-05:00"In general, any semi-martingale can be writt..."In general, any semi-martingale can be written as a determinsitic process plus a brownian motion process plus a gamma process."<br /><br />Interesting. Can you give an accessible reference for this result?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46993361338809173082012-08-01T14:23:49.477-05:002012-08-01T14:23:49.477-05:00The gamma process is such that each increment look...The gamma process is such that each increment looks like a gamma random variable. So it consists of a few jumps mixed with a more small jumps mixed with a huge number of tiny jumps, etc. One of my favorite properties of the gamma process is that it is a "perfect sun shade." Meaning if you were to sit under a gamma process you would be able to see in all directions EXCEPT straight up and down. So if the sun were perfectly over head, it wouldn't block any views at all--but it would block the sun out completely.<br /><br />I've rethought my answer to #2. I'm going with it being natural also. I had forgotten that zeros of a brownian motion form a perfect set and is uncountable. So I'm happy with that being natural also.<br /><br />So all three have nice probabilistic answers and so show that the properties are "generic."Dean Fosterhttps://www.blogger.com/profile/13906505132477512644noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57287378269640007702012-08-01T12:38:43.715-05:002012-08-01T12:38:43.715-05:00Can't be true if you want continuous as well.Can't be true if you want continuous as well.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41133478059211437252012-08-01T09:51:58.568-05:002012-08-01T09:51:58.568-05:001) Please elaborate- what is the 1-d Brownian Moti...1) Please elaborate- what is the 1-d Brownian Motion function?<br />I assume its someting like, a particle starts at 0 and<br />at every stage it goes left or right (how much?) and so<br />f(t) = prob that its at place t. But I am unclear on this so<br />please elaborate. I agree that something like that is clearly<br />natural.<br /><br />2) What is the Gamma Process?GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36900988692162610862012-07-31T21:10:20.359-05:002012-07-31T21:10:20.359-05:00I agree with the previous anonymous comment: If yo...I agree with the previous anonymous comment: If you have ever viewed real numbers in terms of their decimal expansions I don't see how you can avoid acknowledging that the (say) decimal strings that only have 0 and 1 in their expansions is natural set.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31903039603381831742012-07-31T17:14:02.996-05:002012-07-31T17:14:02.996-05:00Answer to #6 is gamma process!
I still going with...Answer to #6 is gamma process!<br /><br />I still going with the stochastic process definition of natural. So I should mention the gamma process as what I think of as the "answer" to question 6: http://en.wikipedia.org/wiki/Gamma_process. It is a pure jump process and hence only has a countable number of jumps--this means its derivative is equal to zero almost everywhere. But, since there is a chance of jump in any arbitrarilly small time interval--it is a purely increasing process. It has lots of other nice properties--but I won't go into them now. (In general, any semi-martingale can be written as a determinsitic process plus a brownian motion process plus a gamma process. I consider semi-martingales the most natural processes we can work with, and the french school of probability proves theorems of this nature.)Dean Fosterhttps://www.blogger.com/profile/13906505132477512644noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77909356550021262442012-07-31T13:24:46.421-05:002012-07-31T13:24:46.421-05:00Isn't the Cantor set natural when seen as {0,1...Isn't the Cantor set natural when seen as {0,1}^Z for example? (A very natural family of objects, used in many places.)<br /><br />And isn't the boundary of a fractal a natural thing? Fractals also appear in many places, where the goal is not only to "define a funny function".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83192285201995170752012-07-31T12:22:25.589-05:002012-07-31T12:22:25.589-05:00Please let me agree with Sasho, for the following ...Please let me agree with Sasho, for the following pragmatic reason. <br /><br />A central teaching of modern quantum information science is that dynamical phenomena whose coarse-grained descriptions are naturally algebraic (e.g., projective quantum measurements) are associated to informatically equivalent fine-grained descriptions (e.g, Carmichael-style quantum trajectory unravellings) whose functional descriptors generically have the paradoxical traits that Lance's post describes. <br /><br />Hence, from a purely pragmatic point-of-view, students henceforth should be taught that these paradoxical functions are "natural".<br /><br />It's incredibly obvious, isn't it Mandrake? :)John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11016830877204830952012-07-31T10:48:39.329-05:002012-07-31T10:48:39.329-05:00For #4, as Konstantin and I pointed out last time,...For #4, as Konstantin and I pointed out last time, there is a probabilistic example that's at least as natural as the gambling game: the Wiener process aka Brownian motion in one dimension. The gambling game is neat, and of a similar spirit. By analogy with the devil's staircase, maybe the points where the F has derivative zero (or where the player loses money?) form an uncountable measure zero set. Then we'll have random walk based examples for all three beasts.Sashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1972761617168611042012-07-31T09:55:03.409-05:002012-07-31T09:55:03.409-05:00Ah- good point.
That raises the odd question- is ...Ah- good point.<br /><br />That raises the odd question- is there a strictly increasing<br />function with dervi 0 at almost every point of [0,1],<br />strictly increasing, and you can PROVE this easily<br />(the function may be contrived).GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58029595234299046312012-07-31T08:55:49.449-05:002012-07-31T08:55:49.449-05:00Doesn't "strictly increasing" mean x...Doesn't "strictly increasing" mean x > y -> f(x) > f(y). Cantor functions are nondecreasing.Anonymousnoreply@blogger.com