Suite aux deux réponses que j'ai reçues (dont aucune n'était complète, j'ai donc écrit la mienne), ce que j'ai finalement fait est le suivant :
UPDATE Table AS target
INNER JOIN
(
select category, appearances_sum
from Table T inner join (
select category as cat, sum(appearances) as appearances_sum
from Table
group by cat
) as agg
where T.category = agg.cat
group by category
) as source
ON target.category = source.category
SET target.probability = target.appearances / source.appearances_sum
Cela fonctionne très rapidement. J'ai aussi essayé avec une sous-requête corrélée mais c'était beaucoup plus lent (ordres de grandeur), donc je m'en tiens à la jointure.