概率遞歸關系是描述隨機算法運行時間的基本機制，其構成主要包括算法每一步遞歸的預處理時間以及算法的遞歸調用。概率遞歸關系從隨機算法的復雜細節中抽取出與算法運行時間相關的部分，因此是隨機算法運行時間的一個簡潔表示。由于其簡潔性，概率遞歸關系通常作為分析隨機算法時間復雜度的一個標準模型。在概率遞歸關系的時間復雜度分析中，運行時間尾概率是一個重要的精細化刻畫，表達隨機算法運行時間超過預設閾值不終止的概率隨閾值增長的衰減性。運行時間尾概率分析由于涉及隨機算法時間復雜度的精細刻畫，因而在理論上有挑戰性。在已有結果中，具有一定普適性（即能適用于一大類概率遞歸關系）的方法僅有1994年由Karp推導出的類似主定理的方法，而其他方法都基于手動推導且只適用于單獨特定的概率遞歸關系。因此，是否存在具有一定普適性且能夠改進Karp經典結果的方法是概率遞歸關系尾概率分析的主要問題。報告人基于先前所作概率程序形式驗證方面的成果，通過鞅理論建立了概率遞歸關系運行時間尾概率的指數驗證條件，并進一步通過研究新的針對指數約束條件的求解算法，給出了一個適用于單遞歸以及分治遞歸概率遞歸關系運行時間尾概率的分析算法。實驗結果表明，該算法所導出的運行時間尾概率在漸進行為上嚴格比Karp方法所導出的界限更緊致，且逼近或等同于經典算法Quicksort和Quickselect上由人工證明所導出的緊致尾概率上界。本成果的意義在于是繼Karp經典方法之后的第一個針對概率遞歸關系尾概率分析問題的顯著推進，且相比Karp方法能夠處理范圍更廣的概率遞歸關系。