Well, it's not random. It's the size necessary to store the meta-data about files (including the file names contained in that directory). The number of files / sub-directories at a given time might not map directly to the size reported, because once allocated, space is not freed if the number of files changes. This behaviour makes sense for most use cases (where disk space is cheap, and once a directory has a lot of files in it, it will probably have them again in future), and helps to reduce fragmentation.
For example:
Code:
$ mkdir testdir
$ cd testdir
$ ls -ld .
drwxr-xr-x 2 matthew matthew 4096 2007-12-03 20:28 ./
$ for ((i=0; i<1000; i++)); do touch some_longish_file_name_$i; done
$ ls -ld .
drwxr-xr-x 2 matthew matthew 36864 2007-12-03 20:29 ./
$ rm some_longish_file_name_*
$ ls -ld .
drwxr-xr-x 2 matthew matthew 36864 2007-12-03 20:29 ./
$ cd ..
$ ls -ld testdir
drwxr-xr-x 2 matthew matthew 36864 2007-12-03 20:29 testdir/
$ rmdir testdir ; mkdir testdir
$ ls -ld testdir
drwxr-xr-x 2 matthew matthew 4096 2007-12-03 20:29 testdir/
Here you see that when even empty files are created, the directory size increases - the file names and meta data must be stored somewhere, and it is in the directory object itself. In this case the file names and other meta-data fit in 9 4k blocks (36864 = 4096 * 9).
Deleting the files does not reduce the space used by the directory object - only removing the directory and re-creating it frees the space.