استفاده از مشخصات مساله

به جای اینکه مساله را مستقیما حل کنیم می توانیم مشخصاتی از آن را در نظر بگیریم و این مشخصات را با هم مقایسه کنیم. (چون چک کردن تساوی آنها به طور مستقیم زمانبر است.)

در این صورت می توانیم با چک کردن تصادفی این مشخصات مسائلی که یکسان بودن دو چیز را بررسی می کنند حل کنیم.

الگوریتم: به صورت تصادفی تساوی زیرمجموعه ای از مشخصات را بررسی می کنیم و اگر یکسان بودند تساوی اعلام می کنیم.

تحلیل: دو حالت وجود دارد: واقعا مساوی بودن (A) و واقعا نامساوی بودن (A'). پیشامد B را هم تشخیص درست در نظر می گیریم. طبق احتمال شرطی داریم:

pr(B) = Pr(B|A)Pr(A)+Pr(B|A')Pr(A')

با استفاده از pr<=1 و محاسبه ی احتمالهایی مثل محاسبه ی احتمالهای دیگر برای آن کران پیدا کرد.