الگوریتم تصادفی شمارش مثلث‌ها (جلسه آخر داده‌های حجیم)

الگوریتم این بود که هر بار یک یال را با احتمال یکنواخت انتخاب می‌کرد و در بقیه‌ی جویبار داده چک می‌کرد که یک مثلث تشکیل می‌دهد یا نه و اگر می‌داد (n-2)|E| برمی‌گرداند.

خب کلاً |E| تا یال داریم و به جز دو سر یال n-2 رأس هستند که می‌توانند با آن تشکیل یک مثلث بدهند. پس به احتمال وجود یک مثلث، مقداری که برمی‌گردد (n-2)|E| است و به احتمال نبودنش صفر است. وقتی که امید ریاضی آن را حساب می‌کنیم، با تعداد مثلث‌ها مساوی می‌شود.