Prev: Simulink and ModelSim automation
Next: Skewed GED Random Number Generator
From: Walter Roberson on 11 Mar 2010 02:05
Greg Heath wrote:
> On Mar 10, 11:53 pm, Greg Heath <he...(a)alumni.brown.edu> wrote:

>> Does that mean there is no finite order bound if, on the ith trial
>> you select x(i) from x = randperm(N) until all integers 1:N
>> were chosen?

> Forget that.
>
> n = 0;
> h = zeros(1,N) % histogram
> while min(h) == 0
> n = n+1;
> m = 1+round((N-1)*rand);
> y(n) = m; % random stream
> h(m) = h(m)+1;
> end
>
> is obviously faster.

Faster than what?

There is no limit to the number of times in a row that m might come out
as (say) 1 in that algorithm, so that algorithm is not guaranteed to
finish (except by running out of memory). The algorithm has a
"worst-case" O(infinity) run-time. Calculating its "expected"
(average-case) running time is non-trivial.
From: Greg Heath on 11 Mar 2010 03:33
On Mar 11, 1:51 am, Walter Roberson <rober...(a)hushmail.com> wrote:
> Greg Heath wrote:
> > On Mar 9, 3:58 pm, Walter Roberson <rober...(a)hushmail.com> wrote:
> >> randperm(12)
>
> >> is of order N*log(N) and a guarantee of a finite run time.
>
> >> Any routine that uses selection "with replacement" and compares against the
> >> answers already selected has an infinite tail on the run time.
> > Does that mean there is no finite order bound if, on the ith trial
> > you select x(i) from x = randperm(N) until all integers 1:N
> > were chosen?
>
> Selecting x(i) on the ith trial is not selection "with replacement", it
> is selection "without replacement".

No. You misunderstand. I was proposing that randperm(N)
be called for each i. Then I realized, duh, that you only need x(1).
That, of course, led to the simpler 1+round((N-1)*rand).

That's why I followed up with "Forget that."


Sorry for the confusion.

Greg
From: Greg Heath on 11 Mar 2010 03:37
On Mar 11, 2:05 am, Walter Roberson <rober...(a)hushmail.com> wrote:
> Greg Heath wrote:
> > On Mar 10, 11:53 pm, Greg Heath <he...(a)alumni.brown.edu> wrote:
> >> Does that mean there is no finite order bound if, on the ith trial
> >> you select x(i) from x = randperm(N) until all integers 1:N
> >> were chosen?
> > Forget that.
>
> > n = 0;
> > h = zeros(1,N)      % histogram
> > while min(h) == 0
> >     n    = n+1;
> >     m    = 1+round((N-1)*rand);
> >     y(n) =  m;      % random stream
> >     h(m) = h(m)+1;
> > end
>
> > is obviously faster.
>
> Faster than what?

Faster than calling randperm(N) each time and then only
use 1 of the N.

> There is no limit to the number of times in a row that m might come out
> as (say) 1 in that algorithm, so that algorithm is not guaranteed to
> finish (except by running out of memory). The algorithm has a
> "worst-case" O(infinity) run-time. Calculating its "expected"
> (average-case) running time is non-trivial.- Hide quoted text -

I agree.

Hope this helps.

Greg
First  |  Prev  | 
Pages: 1 2 3
Prev: Simulink and ModelSim automation
Next: Skewed GED Random Number Generator