Probability of repetition

This is a discussion on Probability of repetition within the Game Programming forums, part of the General Programming Boards category; Seeding rand with a specific value is supposed to ensure that every time you call rand(), you get the same ...

  1. #1
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826

    Probability of repetition

    Seeding rand with a specific value is supposed to ensure that every time you call rand(), you get the same sequence. I don't know if this is actually true, once you start taking other people's hardware into account.

    Let's say I write a program, and compile it, and give you the .exe. You and I both run it. Are we guaranteed to get the same sequence of numbers? That's the basis for this question:

    Take a series of N bits. Make a square out of it. Let's say we have 8192 bytes, for unsigned short number of bits. It looks like this:
    Code:
    unsigned char bits[ 256 ][ 32 ] = { ...all of our bits... };
    It doesn't matter what we fill it in with. Just fill it with stuff, that way it's the same for everyone. It's static, constant, and we never change it. Everyone has this same block of bits.

    Now we all start at the same point, doesn't matter where. Let's say we 'seed' with 12345. First, we find the 12345th bit. Do a bit of math, that should put us oh let's say:

    12345 / 256 = 48
    256 * 48 = 12288
    12345 - 12288 = 57
    57 / 8 = 7
    8*7 = 56
    57 - 56 = 1

    So what's that give us? 1st bit, in the 7th byte in the 48th row? Good enough. So that's where we start. At that point, we take 2 bits:

    01 /* 00 north, 01 east, 10 south, 11 west */

    Doesn't matter what it is. That tells us we need to go. We are in fact taking the integer you want from the bits to the east of where we are. You wanted an integer, so we take the next 32 bits for you. We copy them off into your return value, and there's your rand. We save where we are for the next call to rand.

    The next call picks the first 2 bits from where we left off, to see where to go next. Doesn't matter what it is, that's what we use. It also takes the 2 bits after that, to skip that direction that many bits. I could make that number be the number of bytes we skip, the number of rows, whatever. Doesn't matter, as long as it is consistent. Then I give you your number, and repeat this process for every rand call.

    My question is this: Given consecutive calls to rand, how likely am I to encounter running into the same loop, or short series of numbers? Like this:

    rand 0 = go 2 the east, pop out your number
    rand 1 = go north, pop out your number
    rand 2 = go west, ...
    rand 3 = go south

    Damnit, I'm in aloop now. I will always get the same four consecutive numbers!

    Now it doesn't have to be an immediate loop of four. I'm just wondering if I do the above, how likely am I to get stuck in a pattern, and how likely is it to be a small noticeable pattern? I could fiddle with those numbers a bit. I don't need to use 2 bits. I could 11 or 17 or whatever to tell me where to skip.

    Say I just call rand in a loop, plotting x/y on a graph. With a small set of bits (65k~), how likely am I to encounter a repeating loop?


    Quzah.
    Hope is the first step on the road to disappointment.

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,188
    Let's say I write a program, and compile it, and give you the .exe. You and I both run it. Are we guaranteed to get the same sequence of numbers?
    Assuming you set the seed to a known value, it absolutely should, but it depends on the nature of the algorithm and the binary. (I'm assuming here that the standard doesn't say that `rand' must not sample entropy from other sources. And of course, if you send me an executable that links a DLL, I may have a different version of that DLL.)

    Basically, if a PRNG is initialized to a known value, the implementation isn't broken, and the implementation doesn't sample entropy from another source you get the same sequence every time. That's almost the definition of "PRNG".

    Given consecutive calls to rand, how likely am I to encounter running into the same loop, or short series of numbers?
    It depends on the implementation, but assuming a decent algorithm, basically you can expect a period of 2^log2(RAND_MAX + 1), 2^(log2(RAND_MAX + 1) - 1), or 2^(log2(RAND_MAX + 1) / 2).

    At most you will see a period of 2^BITSOFSTATE, but the real period depends on the number of possible states so this is usually artificially limited. (For example, in order to prevent an all zero double word from ever appearing in the state which for some algorithms would result in an unusually long string of zeros in the output.)

    I'm just wondering if I do the above, how likely am I to get stuck in a pattern, and how likely is it to be a small noticeable pattern?
    I can't say without exact details, and depending on the details, it is impossible to say without simply counting the possible states.

    That said, I believe it would be somewhat likely. (I'd say you'd have a period of no larger than 2^((XMATRIXSIZE * YMATRIXSIZE) / DIRECTIONBITS) despite using 2^(XMATRIXSIZE * YMATRIXSIZE * 8) bits.)

    The algorithm you have proposed samples bits, but it never mutates the state. When it comes to PRNG algorithms, that's a sure sign that you are wasting bits.

    With a small set of bits (65k~), how likely am I to encounter a repeating loop?
    O_o

    100%

    [Edit]
    Well, I may have misunderstood the context.

    Do you mean "If I sample only 65k bits from the above algorithm, will I encounter a loop?".

    That's much more likely, so I'll go with that instead.

    Again, your algorithm never mutates the state. Your selecting algorithm is only 2 bits. I will not worry about the exact math, but I believe your period can be approximated by assuming that your matrix was itself filled with a random algorithm exhibiting equal distribution. (Ignoring details about the size and such.) With those numbers and those assumption, you have a 1 in 4 chance of hitting any given direction, and because those odds always hold you always have a 1 in 4 chance of getting the opposite direction immediately. I'd say you have a 1 in 16 chance of having a period of only 2! I'm sure you can see where I'm going with this.
    [/Edit]

    Soma

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Yeah I was thinking it wouldn't work out well. I was just toying with it as I was trying to drift off to sleep last night. I don't know if I explained it well, but here's the idea (now assume this is all bits, not the characters '1' and '0'):
    Code:
    foo[][] =
    {
        10110101 11010100 00101011 ...
        00111010 11101010 11100111 ...
        ...
    }
    We have a bunch of bits and we treat them as a 2D array of bits. We pick any starting position, and pull a number from it (a number being however many bits you want, in any direction you feel like heading. Then you use the next N bits in that direction to tell you where to go from there.

    So if I make it really small and readable:
    Code:
    00000000
    11111111
    10101001
    10110100
    10111011
    00010000
    11011111
    01010101
    There's our bits, 8x8. We start a 3/3, and read say 4 bits for our actual number that minirand is returning:
    Code:
    00000000
    11111111
    10101001
    10110100
    10111011
    00010000
    11011111
    01010101
    Then we pull the next 2 bits for the direction to head next:
    Code:
    00000000
    11111111
    10101001
    10110100
    10111011
    00010000
    11011111
    01010101
    That means we pull our next 4 bits (next minirand number) from there, heading north from the southern bit shown in blue.

    Anyway, it was a fun idea, even if not very usable.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,453
    > Let's say I write a program, and compile it, and give you the .exe. You and I both run it. Are we guaranteed to get the same sequence of numbers?
    According to C99, the answer is apparently yes.
    The srand function uses the argument as a seed for a new sequence of pseudo-random
    numbers to be returned by subsequent calls to rand. If srand is then called with the
    same seed value, the sequence of pseudo-random numbers shall be repeated. If rand is
    called before any calls to srand have been made, the same sequence shall be generated
    as when srand is first called with a seed value of 1.
    Whether you give the exe to someone else, or run it yourself many times, if you start with the same seed, you're going to get the same sequence.

    Now if you give the source code to someone else to compile, the answer is pretty likely to be "no". The standard doesn't say anything about HOW to implement a PRNG. But typically these seem to use LCG generators.

    If you provided your own "my_srand()" and "my_rand()", then you would be able to answer "yes" regardless of whether you were distributing source or object code.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Looping/Repetition help
    By ArcadeEdge in forum C Programming
    Replies: 4
    Last Post: 09-17-2010, 07:01 PM
  2. Need help for repetition method!
    By rangerys in forum C Programming
    Replies: 9
    Last Post: 09-09-2010, 08:26 AM
  3. Repetition in do{}while
    By Beast() in forum C Programming
    Replies: 25
    Last Post: 06-16-2004, 10:47 PM
  4. Repetition of a line
    By niroopan in forum C++ Programming
    Replies: 1
    Last Post: 09-15-2002, 04:44 PM
  5. repetition and selection- can anyone help?
    By Tarls in forum C++ Programming
    Replies: 2
    Last Post: 03-29-2002, 09:18 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21