Either use http referer or pass own param with your urls determining referring category. The first option seems better to me.
The
//check, whether a user does not access a page directly
if(isset($_SERVER['HTTP_REFERER']))
{
//get category object
$category = get_category_by_path($_SERVER['HTTP_REFERER'], false);
//if category URL was passed
if(NULL !== $category)
echo $category->name;
//otherwise get your random category
else
echo get_random_category_function();
}
else
echo get_random_category_function();
function get_random_category_function() {
//code for generating random category
}