Make 500Kb "windows" tiling the genome. As an example - it looks like you already have your files ready.

bedtools makewindows -w 500000 -g genomes/human.hg19.genome > hg19.500kb.bed

Create a random BED file of 1,000,000 intervals each 100bp in size. As an example - it looks like you already have your files ready.

bedtools random -n 1000000 -l 100 -g genomes/human.hg19.genome > random.bed

Calculate the coverage of the random BED records on the 500Kb windows. The first 3 columns are the window itself, the 4th is the count of BED records that overlapped the window, the fifth is the total number of base pairs in the window with coverage, the 6th is the size of the window, and the 7th is what you are after: the fraction of bases in the window with coverage.

bedtools coverage -a random.bed -b hg19.500kb.bed \
  | sort -k1,1 -k2,2n \
  | awk '$1=="chr10"' \
  | head

chr10    0    500000    162    15947    500000    0.0318940
chr10    500000    1000000    143    14136    500000    0.0282720
chr10    1000000    1500000    147    14487    500000    0.0289740
chr10    1500000    2000000    157    15473    500000    0.0309460
chr10    2000000    2500000    164    16252    500000    0.0325040
chr10    2500000    3000000    160    15501    500000    0.0310020
chr10    3000000    3500000    164    16322    500000    0.0326440
chr10    3500000    4000000    165    16178    500000    0.0323560
chr10    4000000    4500000    150    14931    500000    0.0298620
chr10    4500000    5000000    169    16542    500000    0.0330840

BEDOPS would work well for this, along with standard UNIX utilities.

Let's start with an extents file that defines the bounds of our chromosomes, say for hg19:

We'll grab chromosome 10 and reformat the chromosome name to match your chromosome naming scheme:

$ grep chr10 hg19.extents.bed | awk '{print "10\t"$2"\t"$3}' > chr10.extents.bed

Next, we'll make a BED file of windows or bins from this chromosome, every 500 kb:

$ awk ' \
    BEGIN \
    { \
        binSize = 500000; \
        binIdx = 0; \
    } \
    { \
        chr = $1; \
        start = $2; \
        stop = $3; \
        for (binStart = start; binStart < (stop - binSize); binStart += binSize) { \
            print chr"\t"binStart"\t"(binStart + binSize)"\tbin-"binIdx; \
            binIdx++; \
        } \
    }' chr10.extents.bed \
    > chr10.bins.bed

Next, we use BEDOPS bedops --partition to split your input regions (regions.bed) that span across bins. We can chain together a series of BEDOPS operations that calculate the number of overlapping bases across now-correctly partitioned regions:

$ bedops --partition chr10.bins.bed regions.bed \
    | bedmap --echo --indicator --delim '\t' - regions.bed \
    | grep "1$" - \
    | cut -f1-3 - \
    | bedmap --echo --bases --delim '\t' chr10.bins.bed - \
    | awk -v binSize=500000 '{print $0"\t"($5/$binSize)}' - \
    > final_answer.bed

The file final_answer.bed contains all the bins in BED format, with six columns: bin chromosome, bin start, bin stop, bin index, the number of bases from regions.bed that overlap that bin, and the percentage of overlap.

The chain of commands shown above might look a little overwhelming, but you can use UNIX tee in between steps so you can examine the output being passed to the next command. This is a great way to learn the command line and particularly standard input and output management, which I think you'll find is a critical part of doing bioinformatics.

BEDOPS is really useful for this task - you can pass in standard input and route standard output between BEDOPS tools like bedops and bedmap, and UNIX utilities like grep, cut and awk. After you use BEDOPS for a while, it almost becomes an expressive language for dealing with set operations of this kind.

Finally, the --partition option in bedops is a powerful piece of kit, which lets you quickly cut input regions that span bins, among other uses.