Monday, July 30, 2007

Random Walking

What is the probability that two random walkers starting from a point meet each other during their walk?

We consider random walks in 1, 2 and 3 dimensions.

A 1d random walk can be thought of as a random walk along a long street(Similar to number line), where at each point he may choose to proceed in the same direction or reverse his direction.

A 2d random walk can be thought of as a random walk on a 2d grid, where at each point he may choose any one of four directions(forward, backward, left and right).

Similarly a random walker walking in 3d space has 6 options at each point(Four directions of 2d walk plus up and down).

I wrote a python program to simulate random walks in 1, 2 and 3 dimensions.

The function randwalk simulates a random walk in any dimension. The dimension is determined by the parameter update which is a function which returns the new position of a random walker given his old position. The limit parameter limits the no: of steps taken by a random walker(Random walkers won't walk forever:-) ).


I obtained the following results.

Two 1d random walkers meet about 95% of time at an average of about 1 move before meeting each other.
Two 2d random walkers meet about 60-70% of time at an average of about 20 moves before meeting each other.
Two 3d random walkers meet about 30-35% of time at an average of about 10 moves (This is surprising) before meeting each other.

The above simulation is not very realistic. It assumes that both random walkers walk the same distance at the same pace.
Also, in real life, random walkers don't choose directions randomly. Instead, they may prefer one path over another according to their tastes and preferences.

References



Introduction to probability, Charles M. Grinstead and J . Laurie Snell

Friday, July 27, 2007

Some interesting links

list of Mathematical illusions
list of Paradoxes

If truth does not exist, the statement "truth does not exist" is a truth, thereby proving itself incorrect.
- Nihilist Paradox

Saturday, July 21, 2007

Stages of knowledge

The four stages of knowledge

stage 1 : The stage where you don't know and you know that you don't know.
stage 2 : The stage where you don't know (the whole thing) and you think that you know.
stage 3 : The stage where you know and you think that you don't know.
stage 4: The stage where you know and you know that you know(This stage is purely hypothetical).



"
The path of the righteous man
is beset on all sides...
by the inequities
of the selfish...
and the tyranny of evil men.
Blessed is he who,
in the name of charity and good will,
shepherds the weak
through the valley of darkness,
for he is truly his brother's keeper
and the finder of lost children.
And I will strike down upon thee with
great vengeance and furious anger...
those who attempt to poison
and destroy My brothers.
And you will know
I am the Lord...
when I lay My vengeance
upon you.

....

maybe it means...
you're the evil man,
and I'm the righteous man,
and Mr. 9-millimeter here,
he's the shepherd...
protecting my righteous ass
in the valley of darkness.

Or it could mean...

you're the righteous man,
and I'm the shepherd,
and it's the world
that's evil and selfish.

Now, I'd like that.

But that shit ain't the truth.

The truth is,

you're the weak...
and I'm the tyranny of evil men.

But I'm tryin', Ringo.
I'm tryin' real hard...

to be the shepherd.
"


- From Pulp Fiction, Jules Winnfield to Ringo

Tuesday, July 17, 2007

magic with ImageMagick

ImageMagick is a set of command line utilities for manipulating images, very useful for performing some transformation on multiple images (For individual images, visual editors like GIMP may be a better choice).

The problem


A friend of mine had 57 images (of 2272x1704 !!!) consuming 61MB of disk space. We had to find a way to resize all of them to 1024x768.


A solution


Once I got all 57 images into my_images, the following commands did the job.


$cd my_images
$mkdir conv
$for i in *.jpg
>do
>convert -resize 1024x768 $i conv/$i
>done


And now 6MB is enough..

The convert command is just one of many tools provided by ImageMagick. It converts an input image to create an output image according to the options given to it.

The syntax is

convert options infile outfile

The resize option is used to...(you know what)

More info..



convert has got like a million options (for rotating, blurring, cropping, etc..).One option even allows to specify an affine transformation matrix to transform the image(Phewwww, Who's going to use that).

Another cool tool is montage which is used to create a composite image from many images.

For ex:-
To create an image that consists of a thumbnail preview of all 57 images in my_images..


$montage -geometry 128x128+8+8 -tile 8x8 -background gray *.jpg conv/all.jpg


The syntax is

montage options infile1 infile2 ... infilen outfile

The geometry option specifies size of each tile (128x128) and spacing between tiles(+8+8).

The tile option specifies no: of rows of tiles and no: of tiles in each row.

The choice of 8x8 for tile option is not arbitrary. It allows a maximum of 64 tiles in one file (and I want all 57 thumbnails in one file), if there are more than 64 input files then thumbnails will be split across multiple files.

Sunday, July 15, 2007

GCC Extensions

Gcc provides some cool extensions to the C language. The following, I think, are very useful.

Designated Initializers for arrays


Just like you can initialize structure variables by specifying name of structure members, you can initialize array elements by specifying indices(You can even specify ranges).
For ex:-
int id[256] = { ['A' ... 'Z'] = 1, ['a' ... 'z'] = 1, ['0' ... '9'] = 1, ['_'] = 1 };

__func__ variable


The __func__ variable contains the name of the current function. This comes in handy when you want to print debugging messages of the form,

func-name : msg

The following macro accomplishes this task

#define DEBUGP(format, ...) fprintf(stderr,"%s : " format,__func__, ## __VA_ARGS__)

Note that you can't pass a char * variable directly to DEBUGP to print it.Instead use

DEBUGP("%s", c); /* print the message in c */

Wednesday, July 11, 2007

nature of time

It is said that Einstein once thought...

What if time were circular?

The beginning would have followed the end...:)