We are all accustomed to deterministic algorithms; we work with them every day, and feel comfortable in knowing that the results of running them are predictable, barring a coding error of course. The idea of randomized algorithms feels remote and uncomfortable, despite their usefulness and elegance. There are a couple of great examples in the introductory chapters of the book "Probability and Computing" that are an eye opener.
One is verifying polynomial identities: how can you tell that two different representations of polynomials are the same? For example, if we have two polynomials $P(x)$ and $Q(x)$, both of degree $d$ described by the following formulas:
\[
P(x) = \Sigma_{i=0}^{i=d} a_i x^i \\
Q(x) = \Pi_{i=1}^{i=d} (x-b_i)
\]
how can we determine that they are the same polynomial?
Intuitively we first check that the degrees are the same, then we could try to transform one form into the other, either by multiplying out the terms for $Q(x)$, collecting like terms and reducing it to $P(x)$, or finding the $d$ roots $r$ of $P(x)$, and expressing it as a product of $d$ terms of the form $(x-r_i)$ and comparing them to $Q(x)$. The first approach is easier, but can we do better?
The book presents a randomized algorithm to do the same. What if we pick a random number $r$ from the range $[0, Nd]$, where $N$ is a natural number greater than zero. For example if $N$ is $100$, we pick a random number $r$ from the range $[0,100d]$, and evaluate $P(r)$ and $Q(r)$, which could be done in $O(d)$ time. What would the result tell us?
If $P(r) \ne Q(r)$ then the polynomials are not the same. If $P(r) = Q(r)$, then there is a chance that the polynomials are equivalent, but there is also a chance that they are not, and that $r$ in this case is a root of the equation $P(x)-Q(x)=0$. The chance that we picked an $r$ that satisfies the last equation is no more than $1/N$---($1/100$ in the concrete example).
How do we minimize that chance? By repeating the evaluation by drawing another random value $r$ from the interval $[0,Nd]$. The book describes the probability of producing a false result as the evaluations are repeated with and without replacement, and they are less than $(1/N)^k$, where $k$ is the number of evaluations.
Isn't it quite elegant to find out that two polynomials are the same or not simply through repeated evaluations, and not through algebraic manipulations to transform either or both to a canonical form?
One is verifying polynomial identities: how can you tell that two different representations of polynomials are the same? For example, if we have two polynomials $P(x)$ and $Q(x)$, both of degree $d$ described by the following formulas:
\[
P(x) = \Sigma_{i=0}^{i=d} a_i x^i \\
Q(x) = \Pi_{i=1}^{i=d} (x-b_i)
\]
how can we determine that they are the same polynomial?
Intuitively we first check that the degrees are the same, then we could try to transform one form into the other, either by multiplying out the terms for $Q(x)$, collecting like terms and reducing it to $P(x)$, or finding the $d$ roots $r$ of $P(x)$, and expressing it as a product of $d$ terms of the form $(x-r_i)$ and comparing them to $Q(x)$. The first approach is easier, but can we do better?
The book presents a randomized algorithm to do the same. What if we pick a random number $r$ from the range $[0, Nd]$, where $N$ is a natural number greater than zero. For example if $N$ is $100$, we pick a random number $r$ from the range $[0,100d]$, and evaluate $P(r)$ and $Q(r)$, which could be done in $O(d)$ time. What would the result tell us?
If $P(r) \ne Q(r)$ then the polynomials are not the same. If $P(r) = Q(r)$, then there is a chance that the polynomials are equivalent, but there is also a chance that they are not, and that $r$ in this case is a root of the equation $P(x)-Q(x)=0$. The chance that we picked an $r$ that satisfies the last equation is no more than $1/N$---($1/100$ in the concrete example).
How do we minimize that chance? By repeating the evaluation by drawing another random value $r$ from the interval $[0,Nd]$. The book describes the probability of producing a false result as the evaluations are repeated with and without replacement, and they are less than $(1/N)^k$, where $k$ is the number of evaluations.
Isn't it quite elegant to find out that two polynomials are the same or not simply through repeated evaluations, and not through algebraic manipulations to transform either or both to a canonical form?
Comments
Post a Comment