How to use random proportional editing?
The Proportional editing only affects vertices in the circle of influence (Scroll wheel to resize)  




The default cube is subdivided and I selected a single vertex. Then with the Proportional editing set to random Grabbed and translated on the X axis. Note which vertices are affected.



Then I selected more vertices and repeated the process. Note which vertices are affected now.

I also tried it on a Mesh Circle and the same results occured. I did have to make the circle of influence very very big to affect all the unselected vertices in the circle. 

In the video you cannot see the circle of influence, I am guessing it is so big it is off the edge of his viewport.