Зафиксируем левую и правую границы LBord, RBord. Теперь для каждого человека посчитаем вероятность того, что, если он отдаст токен налево, токен вернётся к нему, не выйдя за левую границу. Обозначим для i-го человека эту вероятность Lret[i][LBord][RBord]. Обозначим вероятность отдать токен налево L[i], а направо - R[i]. Тогда там сумма бесконечной геометрической прогрессии:

Lret[i][LBord][RBord] = R[i-1] / (1 - L[i-1] * Lret[i-1][LBord][RBord])

Для крайнего слева Lret[LBord][LBord][RBord] = 0. Для остальных хорошо считается динамикой слева направо.

Аналогично введём Rret[i][LBord][RBord]. Тогда вероятность для позиции, заданной левой границей, правой границей и положением токена перейти саму в себя равна:

Pret[Token][LBord][RBord] = L[Token] * Lret[Token][LBord][RBord] + R[Token] * Rret[Token][LBord][RBord].

Когда мы посчитаем эту вспомогательную динамику, начнём считать основную: она будет идти по отрезкам с фиксированными границами и токеном либо ровно на левой либо ровно на правой границе. Обозначим матрицу этой динамики P[B][LBord][RBord]. B = 0 для левой, B = 1 для правой.

Тогда:

P[1][LBord][RBord + 1] = P[1][LBord][RBord] * R[RBord] / (1 - Pret[RBord][LBord][RBord]) + P[0][LBord][RBord] * (1 - Pret[LBord][LBord][RBord])

Вспомогательная динамика пройдёт за О(n^3). Основная - за О(n^2). Надеюсь, что нигде не лажанул.