This isn't tested, so take it with a grain of salt, but I think it should work :
EDIT : Code revised.

    class Mage_Catalog_Block_Product_List_Random extends Mage_Catalog_Block_Product_List
    {
        protected function _getProductCollection()
        {
            if (is_null($this->_productCollection)) {
                $categoryID = $this->getCategoryId();
                if($categoryID)
                {
                    // Get array of subcategory ids
                    $catModel = Mage::getModel('catalog/category');
                    $parentCat = $catModel->load($categoryID);
                    $children= explode(',',$parentCat->getChildren());
                    
    
                    // Use the array to filter the collection
                    $collection = Mage::getModel('catalog/product')->getCollection();
    
                    $collection->joinField(
                        'category_id', 'catalog/category_product', 'category_id',
                        'product_id = entity_id', null, 'left'
                    )
                        ->addAttributeToFilter('category_id', array('in' => $children))
                        ->addAttributeToSelect('*');
                $collection->getSelect()->group('entity_id');
                } else {
                    $collection = Mage::getResourceModel('catalog/product_collection');
                }
                Mage::getModel('catalog/layer')->prepareProductCollection($collection);
                $collection->getSelect()->order('rand()');
                $collection->addStoreFilter();
                $numProducts = $this->getNumProducts() ? $this->getNumProducts() : 3;
                $collection->setPage(1, $numProducts)->load();
    
                $this->_productCollection = $collection;
            }
            return $this->_productCollection;
        }
    }

I'm not sure about the timing on calling `$collection->getSelect()->distinct();` - if your products aren't assigned to multiple categories that bit is unnecessary.