Prev: Constrained solutions of a particular equation
Next: Potato head's Oily Obama worries
From: David Bernier on 24 Jun 2010 03:54
Suppose we have 500,000 red chips and 500,000 green chips of the
same size. They are put in a pouch.

We mark a y=0 when t=0 on graph paper.
At time t = 1, we choose a chip at random from the pouch.
If it's green, it counts for +1. If it's red, it counts
for -1.

y at t=1, or y(1) = +1 if the chip is green, and -1 if the
chip is red.

Say we have chose 999 chips (without replacement). The next time
we choose the 1000th chip from the pouch.

Then y(1000) = y(999) +1 if the 1000th chip from the pouch is green,
and y(1000) = y(999) -1 if the 1000th chip from the pouch is red.

We continue choosing chips at random until the pouch is empty.
So in the end we remove 1 million chips. With equal numbers
of red and green chips, y(1,000,000) = 0.

So y(0) = y(10^6) = 0.

My question is, as we increase the number of chips, and after
scaling down of the graphs, can we get something that
approaches a Brownian bridge?


There are simulations of Brownian bridges with initial and final values
of 0.556 and 1.000 here:

< http://demonstrations.wolfram.com/BrownianBridge/ >

It can be worthwhile searching for:
David Williams Brownian bridge xi

For a Brownian bridge on [0, 1] with initial and final values 1,
with vertical scaling fixed once and for all,
we can let
X = excursion of the Brownian bridge B(t)
X = sup_{0<=t<=1} B(t) - inf_{0<=t<=1} B(t) .

Then X is a random variable depending on a sample Brownian bridge.

Then according to Williams,

E[ X^z ]/2 = xi(z), where

xi is related to Riemann zeta as follows:
xi(s) = (1/2) s (s-1) pi^(-s/2) Gamma(s/2) zeta(s).

This gives xi(2) = (1/2) 2 (1) (1/pi) (1) pi^2/6 = pi/6.
xi(2) = 0.523598775598298873077..........

A Monte Carlo simulation gives:

E[ X^2 ] /2 ~= to:

[....]
xi(2.000000 + I*0.000000) ~= 0.522339 + I*0.000000
xi(2.000000 + I*0.000000) ~= 0.521997 + I*0.000000
xi(2.000000 + I*0.000000) ~= 0.521565 + I*0.000000
xi(2.000000 + I*0.000000) ~= 0.521978 + I*0.000000
xi(2.000000 + I*0.000000) ~= 0.521417 + I*0.000000


David Bernier
From: David Bernier on 24 Jun 2010 04:16
David Bernier wrote:
> Suppose we have 500,000 red chips and 500,000 green chips of the
> same size. They are put in a pouch.
>
> We mark a y=0 when t=0 on graph paper.
> At time t = 1, we choose a chip at random from the pouch.
> If it's green, it counts for +1. If it's red, it counts
> for -1.
>
> y at t=1, or y(1) = +1 if the chip is green, and -1 if the
> chip is red.
>
> Say we have chose 999 chips (without replacement). The next time
> we choose the 1000th chip from the pouch.
>
> Then y(1000) = y(999) +1 if the 1000th chip from the pouch is green,
> and y(1000) = y(999) -1 if the 1000th chip from the pouch is red.
>
> We continue choosing chips at random until the pouch is empty.
> So in the end we remove 1 million chips. With equal numbers
> of red and green chips, y(1,000,000) = 0.
>
> So y(0) = y(10^6) = 0.
>
> My question is, as we increase the number of chips, and after
> scaling down of the graphs, can we get something that
> approaches a Brownian bridge?
>
>
> There are simulations of Brownian bridges with initial and final values
> of 0.556 and 1.000 here:
>
> < http://demonstrations.wolfram.com/BrownianBridge/ >
>
> It can be worthwhile searching for:
> David Williams Brownian bridge xi
>
> For a Brownian bridge on [0, 1] with initial and final values 1,

Correction:
For a Brownian bridge on [0, 1] with initial and final values 0,

> with vertical scaling fixed once and for all,
> we can let
> X = excursion of the Brownian bridge B(t)
id est:
> X = sup_{0<=t<=1} B(t) - inf_{0<=t<=1} B(t) .
>
> Then X is a random variable depending on a sample Brownian bridge.
>
> Then according to David Williams,
>
> E[ X^z ]/2 = xi(z), for any complex number z where
>
> xi is related to Riemann zeta as follows:
> xi(s) = (1/2) s (s-1) pi^(-s/2) Gamma(s/2) zeta(s).
>
> This gives xi(2) = (1/2) 2 (1) (1/pi) (1) pi^2/6 = pi/6.
> xi(2) = 0.523598775598298873077..........
>
> A Monte Carlo simulation I'm doing gives:
>
> E[ X^2 ] /2 ~= to:
>
> [....]
> xi(2.000000 + I*0.000000) ~= 0.522339 + I*0.000000
> xi(2.000000 + I*0.000000) ~= 0.521997 + I*0.000000
> xi(2.000000 + I*0.000000) ~= 0.521565 + I*0.000000
> xi(2.000000 + I*0.000000) ~= 0.521978 + I*0.000000
> xi(2.000000 + I*0.000000) ~= 0.521417 + I*0.000000
>
>
> David Bernier

From: David Bernier on 24 Jun 2010 19:25
David Bernier wrote:
> David Bernier wrote:
>> Suppose we have 500,000 red chips and 500,000 green chips of the
>> same size. They are put in a pouch.
>>
>> We mark a y=0 when t=0 on graph paper.
>> At time t = 1, we choose a chip at random from the pouch.
>> If it's green, it counts for +1. If it's red, it counts
>> for -1.
>>
>> y at t=1, or y(1) = +1 if the chip is green, and -1 if the
>> chip is red.
>>
>> Say we have chose 999 chips (without replacement). The next time
>> we choose the 1000th chip from the pouch.
>>
>> Then y(1000) = y(999) +1 if the 1000th chip from the pouch is green,
>> and y(1000) = y(999) -1 if the 1000th chip from the pouch is red.
>>
>> We continue choosing chips at random until the pouch is empty.
>> So in the end we remove 1 million chips. With equal numbers
>> of red and green chips, y(1,000,000) = 0.
>>
>> So y(0) = y(10^6) = 0.
>>
>> My question is, as we increase the number of chips, and after
>> scaling down of the graphs, can we get something that
>> approaches a Brownian bridge?
>>
>>
>> There are simulations of Brownian bridges with initial and final values
>> of 0.556 and 1.000 here:
>>
>> < http://demonstrations.wolfram.com/BrownianBridge/ >
>>
>> It can be worthwhile searching for:
>> David Williams Brownian bridge xi
>>
>> For a Brownian bridge on [0, 1] with initial and final values 1,
>
> Correction:
> For a Brownian bridge on [0, 1] with initial and final values 0,
>
>> with vertical scaling fixed once and for all,
>> we can let
>> X = excursion of the Brownian bridge B(t)
> id est:
>> X = sup_{0<=t<=1} B(t) - inf_{0<=t<=1} B(t) .
>>
>> Then X is a random variable depending on a sample Brownian bridge.
>>
>> Then according to David Williams,
>>
>> E[ X^z ]/2 = xi(z), for any complex number z where
>>
>> xi is related to Riemann zeta as follows:
>> xi(s) = (1/2) s (s-1) pi^(-s/2) Gamma(s/2) zeta(s).
>>
>> This gives xi(2) = (1/2) 2 (1) (1/pi) (1) pi^2/6 = pi/6.
>> xi(2) = 0.523598775598298873077..........
>>
>> A Monte Carlo simulation I'm doing gives:
>>
>> E[ X^2 ] /2 ~= to:
>>
>> [....]
>> xi(2.000000 + I*0.000000) ~= 0.522339 + I*0.000000
>> xi(2.000000 + I*0.000000) ~= 0.521997 + I*0.000000
>> xi(2.000000 + I*0.000000) ~= 0.521565 + I*0.000000
>> xi(2.000000 + I*0.000000) ~= 0.521978 + I*0.000000
>> xi(2.000000 + I*0.000000) ~= 0.521417 + I*0.000000

Currently, I'm getting this:

xi(2.000000 + I*0.000000) ~= 0.512887 + I*0.000000
xi(2.000000 + I*0.000000) ~= 0.512871 + I*0.000000
xi(2.000000 + I*0.000000) ~= 0.512833 + I*0.000000
xi(2.000000 + I*0.000000) ~= 0.512850 + I*0.000000

vs. pi/6 ~= 0.523598.

I think I'm underestimating sup_{0<=t<=1} B(t)
and | inf_{0<=t<=1} B(t) | on average.

The Brownian bridge samples are produced by a stochastic/random
Fourier synthesis recipe given by David William (UK).

It involves linear combination of
g_1, .... g_10000 where
g_{k} (t) = sin(pi.k.t) for 0<=t<=1 .

The coefficients are independent normal r.v.s with median 0 and variance
that decreases with n.

Possibly the cut-off at 10,000 Fourier series terms is not bad.
But I only sample the 10,000 values of t:
0.0001, 0.0002, ..... j/(10^4) .... 1.000000000 [ 1 <= j <= 10,000 ].

That way, the true maximum of a sample Brownian bridge
given by Fourier series with 10,000 terms could be somewhat _higher_
than what I get, since Brownian motion is very irregular, meandering
or "volatile".

Or, my Fourier synthesis might need more sines.

David Bernier
From: Henry on 28 Jun 2010 08:47
On 25 June, 00:25, David Bernier <david...(a)videotron.ca> wrote:
> David Bernier wrote:
> > David Bernier wrote:
> >> My question is, as we increase the number of chips, and after
> >> scaling down of the graphs, can we get something that
> >> approaches a Brownian bridge?

I assume you are scaling down by sqrt(2n) where n is the number of up
steps (red chips) and also the number of down steps (green chips).

> > For a Brownian bridge on [0, 1] with initial and final values 0,
> >> with vertical scaling fixed once and for all,
> >> we can let
> >> X = excursion of the Brownian bridge B(t)
> > id est:
> >> X = sup_{0<=t<=1} B(t) - inf_{0<=t<=1} B(t) .
>
> >> Then X is a random variable depending on a sample Brownian bridge.
>
> >> Then according to David Williams,
>
> >> E[ X^z ]/2 = xi(z), for any complex number z where
>
> >> xi is related to Riemann zeta as follows:
> >> xi(s) = (1/2) s (s-1) pi^(-s/2) Gamma(s/2) zeta(s).
>
> >> This gives xi(2) = (1/2) 2 (1) (1/pi) (1) pi^2/6 = pi/6.
> >> xi(2) = 0.523598775598298873077..........

I am not sure I would get this.

As far as I can tell where X*sqrt(2n) is the range of a 2n step walk
starting and finishing at 0, we have
E[X] = (2^(2n) / C(2n,n) - 1) / sqrt(2n)
which is between sqrt(pi/2) = 1.2533... and
sqrt(pi/2) - 1/sqrt(2n)

So E[X^2] should be more than (E[X])^2
and so E[X^2]/2 should exceed 0.78... for 2n sufficiently large

>
> >> A Monte Carlo simulation I'm doing gives:
>
> >> E[ X^2 ] /2 ~= to:
>
> >> [....]
> >> xi(2.000000 + I*0.000000) ~= 0.522339 + I*0.000000
> >> xi(2.000000 + I*0.000000) ~= 0.521997 + I*0.000000
> >> xi(2.000000 + I*0.000000) ~= 0.521565 + I*0.000000
> >> xi(2.000000 + I*0.000000) ~= 0.521978 + I*0.000000
> >> xi(2.000000 + I*0.000000) ~= 0.521417 + I*0.000000
>
> Currently, I'm getting this:
>
> xi(2.000000 + I*0.000000) ~= 0.512887 + I*0.000000
> xi(2.000000 + I*0.000000) ~= 0.512871 + I*0.000000
> xi(2.000000 + I*0.000000) ~= 0.512833 + I*0.000000
> xi(2.000000 + I*0.000000) ~= 0.512850 + I*0.000000
>
> vs. pi/6 ~= 0.523598.

It seems that even for a 2n=14 step walk (so 7 steps up and 7 steps
down), there are 3432 possible paths, where the expected range is
12952/3432 = 3.77... and the expected square of the range is
52180/3432 = 15.20....

Scaling the range by sqrt(14) and its square by 14 would give
E[X^2]/2=0.54... which is more than your numbers. A path with more
steps should give a higher figure.

I may have misunderstood or miscalculated

From: David Bernier on 28 Jun 2010 20:32
Henry wrote:
> On 25 June, 00:25, David Bernier<david...(a)videotron.ca> wrote:
>> David Bernier wrote:
>>> David Bernier wrote:
>>>> My question is, as we increase the number of chips, and after
>>>> scaling down of the graphs, can we get something that
>>>> approaches a Brownian bridge?
>
> I assume you are scaling down by sqrt(2n) where n is the number of up
> steps (red chips) and also the number of down steps (green chips).
>
>>> For a Brownian bridge on [0, 1] with initial and final values 0,
>>>> with vertical scaling fixed once and for all,
>>>> we can let
>>>> X = excursion of the Brownian bridge B(t)
>>> id est:
>>>> X = sup_{0<=t<=1} B(t) - inf_{0<=t<=1} B(t) .
>>
>>>> Then X is a random variable depending on a sample Brownian bridge.
>>
>>>> Then according to David Williams,
>>
>>>> E[ X^z ]/2 = xi(z), for any complex number z where
>>
>>>> xi is related to Riemann zeta as follows:
>>>> xi(s) = (1/2) s (s-1) pi^(-s/2) Gamma(s/2) zeta(s).
>>
>>>> This gives xi(2) = (1/2) 2 (1) (1/pi) (1) pi^2/6 = pi/6.
>>>> xi(2) = 0.523598775598298873077..........
>
> I am not sure I would get this.
>
> As far as I can tell where X*sqrt(2n) is the range of a 2n step walk
> starting and finishing at 0, we have
> E[X] = (2^(2n) / C(2n,n) - 1) / sqrt(2n)
> which is between sqrt(pi/2) = 1.2533... and
> sqrt(pi/2) - 1/sqrt(2n)
>
> So E[X^2] should be more than (E[X])^2
> and so E[X^2]/2 should exceed 0.78... for 2n sufficiently large

I tried to put together some background on "Brownian bridges"
from knowledgeable sources and here's what I've got:

David Williams wrote a paper
entitled: "Brownian Motion and the Riemann Zeta-Function"
which I have as a PDF file. I don't
know where or when it was published or
appeared.

However, I'm pretty sure this page from the
University of Wales, Swansea is about the author
of "Brownian Motion and the Riemann Zeta-Function":
< http://www-maths.swan.ac.uk/staff/dw/ >

Williams writes:
"Intuitively, Brownian bridge with values in R,
BB(R), is BM(R) with time-parameter set [0,1]
conditioned to be at 0 at times 0 and 1.
Rigorously, there is unique measure W^{0,0}
on C[0, 1] with [...] "

[ BM(R) is Brownian motion with values in R.]

I think he means standard Brownian
motion, say x(t), where t is a real number
in [0, oo), x(0) = 0 and the variance
of the Gaussian normal r.v. x(t) is t,
with mean zero. So in particular
x(1) or the position at time t=1 is
a r.v. whose variance is 1.

I have some understanding of BM on an
intuitive level. I can't explain precisely
how one "conditions [Brownian motion]
to be at 0 at times t=0 and t=1." or
how the measure W^{0,0} on C[0, 1]
is defined or constructed.

But I agree with you in describing
the r.v. X as the (length of) "the range" of
a standard Brownian motion for t in [0, 1];
this is conditioned on the BM being at zero
at time t=1.

For my simulations related to X, I used
Fourier series with independent mean zero
normal random variables as coefficients for
sin(pi.k.t), k in N\ {0}.

Also, the graphs for the coloured chips in
my discrete problem may or may not approach
the well-studied process of Brownian bridges.

If I remember correctly, the probabilists'
Brownian bridge X has mean one.

David Bernier


>>
>>>> A Monte Carlo simulation I'm doing gives:
>>
>>>> E[ X^2 ] /2 ~= to:
>>
>>>> [....]
>>>> xi(2.000000 + I*0.000000) ~= 0.522339 + I*0.000000
>>>> xi(2.000000 + I*0.000000) ~= 0.521997 + I*0.000000
>>>> xi(2.000000 + I*0.000000) ~= 0.521565 + I*0.000000
>>>> xi(2.000000 + I*0.000000) ~= 0.521978 + I*0.000000
>>>> xi(2.000000 + I*0.000000) ~= 0.521417 + I*0.000000
>>
>> Currently, I'm getting this:
>>
>> xi(2.000000 + I*0.000000) ~= 0.512887 + I*0.000000
>> xi(2.000000 + I*0.000000) ~= 0.512871 + I*0.000000
>> xi(2.000000 + I*0.000000) ~= 0.512833 + I*0.000000
>> xi(2.000000 + I*0.000000) ~= 0.512850 + I*0.000000
>>
>> vs. pi/6 ~= 0.523598.
>
> It seems that even for a 2n=14 step walk (so 7 steps up and 7 steps
> down), there are 3432 possible paths, where the expected range is
> 12952/3432 = 3.77... and the expected square of the range is
> 52180/3432 = 15.20....
>
> Scaling the range by sqrt(14) and its square by 14 would give
> E[X^2]/2=0.54... which is more than your numbers. A path with more
> steps should give a higher figure.
>
> I may have misunderstood or miscalculated
>

 |  Next  |  Last
Pages: 1 2
Prev: Constrained solutions of a particular equation
Next: Potato head's Oily Obama worries