I came across this equation in the solution to problem 35 of "50 Challenging Problems in Probability" (page 37), which deals with a variant of the gambler's ruin problem. Specifically:

A man is 1 step away from falling off a cliff. He takes random steps either towards or away from the cliff. If the probability of his takinng a step away is always 2/3, and of taking a step towards always 1/3, what is his chance of escaping the cliff?

The book gives the answer as $(x-1)(px + p - 1) = 0$, but I can't figure out how to arrive at that answer using standard factoring methods or the quadratic equation. How do I factor this polynomial?

  • $\begingroup$ @астонвіллаолофмэллбэрг Make that an answer! $\endgroup$ – Toby Mak Feb 9 at 5:36
  • 1
    $\begingroup$ By the rational root test, if you can notice that $1$ is always a root, the factorization follows from long division. $\endgroup$ – Hyperion Feb 9 at 5:36
  • $\begingroup$ @TobyMak Have just done so. Thank you. $\endgroup$ – астон вілла олоф мэллбэрг Feb 9 at 5:37
  • $\begingroup$ This article about the Drunkard's Walk is explained quite nicely. $\endgroup$ – Toby Mak Feb 9 at 5:41
  • $\begingroup$ @TobyMak I appreciate the link, but it's basically a restatement of the answer given in the original book, and also doesn't explain how to factor the quadratic. $\endgroup$ – KD89042 Feb 9 at 5:49

Since $$x^2-1=(x-1)(x+1),$$ we obtain: $$px^2-x+1-p=p(x^2-1)-(x-1)=(x-1)(p(x+1)-1)=(x-1)(px+p-1)$$


.Do you know the factor theorem for polynomials? In particular, since for the polynomial $q(x)=px^2−x+(p−1)$ we have $q(1)=p−1+(p−1)=0$, the theorem tells us that $(x−1)$ is a factor of $q(x)$. Now polynomial division tells us what the other factor is.

Also, as mentioned in another answer, you can use the quadratic formula to get the roots of the polynomial if the roots are not found using these guesses.

  • $\begingroup$ I didn't know it was a named theorem, but I was aware of the result. How did you know that q(1) would equal 0? Is it just a matter of guessing and checking for small integer values, or is there a more principled way? $\endgroup$ – KD89042 Feb 9 at 5:52
  • $\begingroup$ You can reduce your guesses by using the rational root theorem : it says that if $x/y$ in lowest terms is a root of the polynomial , then $x$ must divide the constant term and $y$ the highest coefficient ,so you only need to check $x$ as a divisor of p and $y$ as a divisor of $p-1$, of which thankfully $1/1$ works out. $\endgroup$ – астон вілла олоф мэллбэрг Feb 9 at 5:56

Worst case scenario, if you didn't see any of the tricks in the other answer, you could always use the quadratic formula to get the roots $r_1, r_2$. Doing $(x-r_1)(x-r_2)$ won't quite give you the factorization of the polynomial, because as you can see, if you expand the expression above you get a $1$ in front of $x^2$. However, our polynomial is equal to $a(x-r_1)(x-r_2)$ with $a=p$.

  • $\begingroup$ I tried to use the quadratic formula, but I couldn't figure out how to simplify $ \sqrt(b^2-4ac)$ ( in this case, $\sqrt(1 - 4p(1-p))$ $\endgroup$ – KD89042 Feb 9 at 5:56
  • $\begingroup$ @KD89042 Does $(2x+1)^2 = 4x^2+4x+1$ ring a bell? $\endgroup$ – Ovi Feb 9 at 5:58
  • $\begingroup$ @KD89042 For me, when dealing with quadratics I always keep an eye out for these number patterns: 1-2-1, 1-4-4, 1-6-9, 1-8-16, etc. They all correspond to perfect squares. $\endgroup$ – Ovi Feb 9 at 5:59
  • $\begingroup$ That's a very useful tip, thank you! $\endgroup$ – KD89042 Feb 9 at 6:00
  • $\begingroup$ @KD89042 You're welcome! $\endgroup$ – Ovi Feb 9 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.