a 20-line random walk [heap corrupted]

The Partridge Family were neither partridges nor a family. Discuss.
Clodi
Posts: 175
Joined: November 18th, 2012, 7:47 pm

a 20-line random walk [heap corrupted]

Post by Clodi » December 22nd, 2014, 2:19 am

Hello, as you may or may not know, if you walk randomly from point a to point b, after n steps, point b is expected to be sqrt(n) units of distance away from n. (NOT n units of distance away from n!)

Now, why is this code going against maths and science?

Code: Select all

void main()
{
	int position = 0;
	FILE* pFile = fopen( "random walk.txt","w" );

	for( int i = 0; i < 1000000000; i++ )
	{
		int a = rand() % 10;  //random number generated
		
		     if( a < 5  ) { position--; }   //position update
		else if( a >= 5 ) { position++; }

		//show result
		if( i % 10000000 == 0 ) { fprintf( pFile,"%d\t%d\n",i,abs( position ) ); }
	}
}
Here I am plotting distance traveled d against number of steps.. it shouldn't be a straight line. The square of the distance against time should give a straight line! HELP!! :?
Attachments
random walk picture.jpg
random walk picture.jpg (16.89 KiB) Viewed 5607 times
Last edited by Clodi on December 30th, 2014, 4:28 pm, edited 1 time in total.

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: a 20-line random walk

Post by albinopapa » December 22nd, 2014, 6:30 am

Why absolute value of position? That would always show a positive result.

The idea of the random walk is that over a given amount of time you should break even on average, but you also should hit the same highs the same amount of times as you hit the lows. If the lows are never below 0 then they will never cancel each other out...that's how I understand the random walk algorithm anyway.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Clodi
Posts: 175
Joined: November 18th, 2012, 7:47 pm

Re: a 20-line random walk

Post by Clodi » December 22nd, 2014, 8:54 am

Why absolute value of position?
I need the distance, not the position, so, since I am lazy, instead of creating a new variable I just took the absolute value of position to get distance
The idea of the random walk is that over a given amount of time you should break even on average
That's exactly what I thought. However, no. The walker ends up farer and farer as the number of steps increases. However, the total distance traveled per minute remains constant but the overall distance between him now and the starting point increases but less and less. The square of the overall distance between him now and the starting point increases directly proportionally to the number of steps (straight line). This is the theory ..I think. :cry:
Attachments
random walk 2.jpg
random walk 2.jpg (22.35 KiB) Viewed 5596 times

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: a 20-line random walk

Post by albinopapa » December 22nd, 2014, 9:41 am

Okay, so if the steps are F, F, F, B, B, F, B, B, the position would be 0, but the distance would be 8, is that what you are trying to get?

F = position++
B = position--

or forward and backward.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Clodi
Posts: 175
Joined: November 18th, 2012, 7:47 pm

Re: a 20-line random walk

Post by Clodi » December 22nd, 2014, 10:29 am

Exactly.
Distance traveled by the walker would be 8, but the final distance B after N steps, that is what I am interested in plotting against time, would be zero in this case, after the 8th step. :lol:

User avatar
LuX
Posts: 1492
Joined: April 22nd, 2012, 12:33 pm
Location: Finland

Re: a 20-line random walk

Post by LuX » December 22nd, 2014, 1:36 pm

Well, to begin with, random number generation using rand isn't truly random, which is why you might experience these oddities.

after running this code for a while, the average distance started to get closer and closer to 0, ultimately it hovers ±2 around 0.

Code: Select all

TEMPLATE_INLINE V RND( V Min, V Max )
{
	return static_cast< V >( static_cast< double >( rand( ) ) / static_cast< double >( RAND_MAX ) * ( static_cast< double >( Max ) -  static_cast< double >( Min ) + 1.0 ) + static_cast< double >( Min ) );
}

-----------------------------------------------------------------------------------------------

      static int average = 0;
		static int times = 0;
		int position = 0;

		repeat( 100 )
		{
			position = 0;

			for ( int i = 0; i < 1000000; i++ )
			{
				int a = RND( 0, 9 );

				if ( a < 5 ) position--;
				else if ( a >= 5 ) position++;
			}

			average += position;
			times ++;
		}


		text.render( PointD( 20, 185 ), 0xFFFFFFFF, "distance %i", position );
		text.render( PointD( 20, 210 ), 0xFFFFFFFF, "average %f, times %i", double( average ) / double( times ), times );

Code: Select all

average -1.306078, times 10200 ( thats 10 200 000 000 steps )
The position ( or distance ) after each pass may vary from ±20 to ±1500, but on average the player is near 0.
ʕ •ᴥ•ʔ

Clodi
Posts: 175
Joined: November 18th, 2012, 7:47 pm

Re: a 20-line random walk

Post by Clodi » December 22nd, 2014, 6:07 pm

THANK YOU SO MUCH Lux!!!!!

I knew that random generators are not random but pseudo-random.
I also know that rand() has proven to give problems time and time again.

..I just thought it was that kind of problems that wouldn't affect a noob like me playing around with random generation and its basic properties. I am genuinely surprised of your findings. And I am very grateful for that.

So.. did you just write your own random generator or did you take it from somewhere? Could you please explain those lines of code? I really cannot understand any of it :D

Cla

User avatar
LuX
Posts: 1492
Joined: April 22nd, 2012, 12:33 pm
Location: Finland

Re: a 20-line random walk

Post by LuX » December 22nd, 2014, 11:01 pm

Good question. Unfortunately I don't remember where I got it from, but I didn't make it. I remember it being something about certain numbers appearing more frequently than others when using rand(), and the RND function is supposed to equalize all numbers. And interestingly enough, when I use "int a = rand( ) % 10;" instead of "int a = RND( 0, 9 );" the average stays around -70 instead of around 0.

In short, the function first generates a random number from 0.0 to 1.0. Then it multiplies that with the max and min difference and adds the min at the end. Say we want a random float value from 4.0 to 10.0: we first generate our random multiplier, say, 0.2, then multiply that with 10.0 - 4.0 = 6.0. So 0.2 * 6.0 = 1.2. and finally add the minimum to get it to the proper range: 1.2 + 4.0 = 5.2.

If you want to use it in your game, just replace the first part with "template < typename V > inline".
ʕ •ᴥ•ʔ

Clodi
Posts: 175
Joined: November 18th, 2012, 7:47 pm

Re: a 20-line random walk

Post by Clodi » December 23rd, 2014, 5:45 am

Thank you.
I have just notice your repeat function.
How can I make one in C++?

something like:

Code: Select all

void repeat( int a )
{
	for( int i = 0; i < a; i++ )
	{
		//do stuff
	}
}
that syntax is more similar to MatLab than C / C++!

edit: I wrote this before main():

Code: Select all

template < typename V > inline
{
   return static_cast< V >( static_cast< double >( rand( ) ) / static_cast< double >( RAND_MAX ) * ( static_cast< double >( Max ) -  static_cast< double >( Min ) + 1.0 ) + static_cast< double >( Min ) );
}
the compiler didn't really like it, it said:
1>c:\users\acer\desktop\random walk\random walk\random walk\main.cpp(8): error C2988: unrecognizable template declaration/definition
:roll:

User avatar
LuX
Posts: 1492
Joined: April 22nd, 2012, 12:33 pm
Location: Finland

Re: a 20-line random walk

Post by LuX » December 23rd, 2014, 8:28 am

Ah, I meant the very first word...

Code: Select all

template < typename V > inline V RND( V Min, V Max )
{
   return static_cast< V >( static_cast< double >( rand( ) ) / static_cast< double >( RAND_MAX ) * ( static_cast< double >( Max ) -  static_cast< double >( Min ) + 1.0 ) + static_cast< double >( Min ) );
}
You should check out template functions if you aren't familiar with them.

And the repeat "function" is only a macro, but I rarely use it and don't recommend using it because it can easily cause problems if you aren't careful. But it sure is convenient for writing something quickly.
ʕ •ᴥ•ʔ

Post Reply