[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: rand("state")
From: |
Francesco Potorti` |
Subject: |
Re: rand("state") |
Date: |
Thu, 16 Feb 2006 19:27:37 +0100 |
>> Or else you can see it as this: have a generator of period P, from which
>> you have already taken N non-overlapping sequences of length L. The
>> probability that one more sequence of lenght L starting from a random
>> point does not overlap with one of the already taken N sequences is
>> equal to the probability that no taken sequence starts in an interval of
>> length 2*L, that is, (1-N/P)^(2*L), under the assumption that N*L<<P,
>> which is true in our case.
>>
>> If what I wrote is correct, then you have the probability of choosing a
>> new good sequence, given that you have already chosen N.
>
>I don't have time right now to figure out if it is correct, but I will
>add this:
>
>(1-N/P)^(2*L) = ((1-N/P)^(P/N))^((N/P)(2*L)) = exp(-2*L*N/P)
>
>That last equality is approximate, but it is very close whenever N/P is
>small, and it is always small.
In fact, what you wrote is the probability of non collision in an Aloha
communications system. Now, we should compute the probability of
generating N non-overlapping sequences, which is
prod_i=0^N-1 exp(-2*L*i/P) = exp(sum_i=0^N-1 -2*L*i/P)
= exp(-2*L/P*N*(N-1)/2)
= exp(-L/P*N*(N-1))
~ exp(-L/P*N^2)
~ 1-L/P*N^2
so, the probability of at least two sequences overlapping is, with
excellent approximation, L/P*N^2. If we set P=10^6001, L=10^l, N=10^n,
the probability of overlapping is 10^(l+2*n-6001). Nice result.
If I made no errors, of course. Anyone willing to check this?
--
Francesco Potortì (ricercatore) Voice: +39 050 315 3058 (op.2111)
ISTI - Area della ricerca CNR Fax: +39 050 313 8091
via G. Moruzzi 1, I-56124 Pisa Email: address@hidden
Web: http://fly.isti.cnr.it/ Key: fly.isti.cnr.it/public.key
-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.
Octave's home on the web: http://www.octave.org
How to fund new projects: http://www.octave.org/funding.html
Subscription information: http://www.octave.org/archive.html
-------------------------------------------------------------
- Re: rand("state"), (continued)
- Re: rand("state"), Mike Miller, 2006/02/15
- Re: rand("state"), Mike Miller, 2006/02/15
- Re: rand("state"), Francesco Potorti`, 2006/02/16
- Re: rand("state"), Paul Kienzle, 2006/02/16
- Re: rand("state"), Mike Miller, 2006/02/16
- Re: rand("state"), Paul Kienzle, 2006/02/16
- Re: rand("state"), Francesco Potorti`, 2006/02/16
- Re: rand("state"), Mike Miller, 2006/02/16
- Re: rand("state"), Francesco Potorti`, 2006/02/16
- Re: rand("state"), Mike Miller, 2006/02/16
- Re: rand("state"),
Francesco Potorti` <=
- Re: rand("state"), Michael Creel, 2006/02/17
- Re: rand("state"), Francesco Potorti`, 2006/02/17
- Re: rand("state"), Mike Miller, 2006/02/17
- Re: rand("state"), Francesco Potorti`, 2006/02/17
- Re: rand("state"), Mike Miller, 2006/02/17
- Re: rand("state"), Francesco Potorti`, 2006/02/17