Histogram estimation (from sub-set of image pixels)
I think random sampling approach seems to be not effective, since the statistical population (pixel intensities) distribution in images is heavily localized. There might be more scientific approaches, but if you need only a rough near estimation I'd like to suggest a method. Here is how:


Blur the image with a low-pass mask (average out neighboring pixels) [Optional, if you are O.K with blurring computations]
Down sample (make it smaller like by a factor of 2) the blurred image
Compute histogram of the down-samples blurred version of the image.


Here is a code experiment:

I=imread('coins.png');
Mask=ones(5,5);
tic
H1=imhist(I);
toc
I_Averaged=imfilter(I,Mask); %OPTIONAL STEP
I_DownSampled=I(1:3:end,1:3:end);
tic 
H2=imhist(I_DownSampled);
toc


The results:


Elapsed time is 0.003042 seconds. %For Original Hist
Elapsed time is 0.000365 seconds. %For DownSampled Hist


and the rough histogram and original image histogram are shown in below images:

1.Rough




  2.Original




Almost no difference, for 8 times faster computations.