Re: SF: Back to theory

From: Mike Kent (mkent_at_acm.org)
Date: 02/27/05 

Date: Sun, 27 Feb 2005 01:09:29 -0500

Tim Peters wrote:
...
> I want to elaborate on that, because some results _may_ be artifacts of the
> way primes are chosen. I pick an N-bit prime like so: pick a random
> integer i uniformly from the range 2**(N-1) <= i < 2**N, and then find the
> smallest prime >= i. But not all primes in range are equally likely to get
> picked -- due to the way I'm choosing them, the probability of picking a
> particular prime p is proportional to 1 + the number of composites
> immediately preceding p. I can't imagine why that would bias the results,
> but can't swear that it doesn't. Another thing to test, anyway.

I believe you can get rid of (much of) the bias by modifying your
procedure as follows:

        Pick a fixed number K with 0 < K < N.

        Pick i between 2**(N-1) and 2**N as before. Make a
        list of the primes between i and i+K. If the list is
        empty, pick a new i and repeat; otherwise randomly
        pick an item from the list.

Picking K = 0 gets rid of all the bias -- the modified procedure
them amounts to pick i, see if it's prime. K = 1 is almost as
good since only one of i and i+1 is even. As K gets larger, bias
arises against primes that occur in clusters (the items of a prime
pair are roughly 1/2 as likely to be picked as is a prime with
not near prime neighbors, for instance); as K decreases, the
expected number of iterations increases.

Relevant Pages

  • Re: OT - Bias at the Gray Lady
    ... Imagine the leadership in Obama's church, ... A very subtle but clever bit of writing, ... busted logic to explain the bias. ...
    (alt.autos.toyota)
  • Re: Questions on interfacing to current sense transformer
    ... Right, this is a problem I was anticipating, because there was no way ... I could imagine to bias these signals perfectly so that they would ...
    (sci.electronics.design)
  • Re: SF: Back to theory
    ... > immediately preceding p. ... I can't imagine why that would bias the results, ... > but can't swear that it doesn't. ... I believe you can get rid of the bias by modifying your ...
    (sci.crypt)
  • Re: The future of TeX
    ... I've always had a bias against PDF, and so didn't concern myself with ... I imagine it, too, is a passing phase ...
    (comp.text.tex)
  • Re: OT: Repuglicans are disgusting, 11/10/05 edition
    ... you Imagine that I am anti-religious when I am anything but. ... But that's because I disagree with you. ... Then I'm anti-them ...
    (rec.music.classical.recordings)
Quantcast