Randomness
Randomness is an important computational resource, just as running time and memory space. Randomness sometimes is essential for designing algorithms. Randomness is useful!
Quick Select
In quick sort, a random pivot selection has the property that, for any input data, the expected running time is \(O(n \log n)\). For example, suppose we have an array which is already sorted. If we always pick up the first element in the array as the pivot, the running time will be degenerated to \(O(n^2)\); however, with random pivots, the expected running time will be \(O(n \log n)\).
A simple way of selecting a random pivot is to find a random element in the array and swap it with the first element, and then apply the partitioning.
int r = first + (int) (Math.random() * (last - first + 1)); swap(data, first, r);
Consider the problem of finding the k-th element in an array of size n. Using selection sort, we are able to partially sort the array up to the k-th element and return the result. However, this will require \(O(kn)\) time, and if k=n/2 (finding the median in an array), this is an \(O(n^2)\) time algorithm.
The following is a quick select algorithm which takes an array of size n and an integer k < n and finds the k-th element in the array (k starts from 0 to n-1). Pick a random pivot element from the array. Split the array into two subarrays around the pivot. Count the number of elements to the left of the pivot. Denote by l. if it is k, then return the pivot if it is greater than k, recursively call with the left subarray and k if it is smaller than k, recursively call with the right subarray and k-(l+1) The following is the implementation of quick select; the partitioning method partition() it calls is the same as the one in quick sort.
public static int quickSelect(int[] data, int first, int last, int k)
{
if (first >= last)
return first;
int pivot = partition(data, first, last);
int len = pivot - first; // length of the left part
if (len > k)
return quickSelect(data, first, pivot - 1, k);
if (len < k)
return quickSelect(data, pivot + 1, last, k - len - 1);
// pivot - first == k
return pivot;
}
The quick select algorithm runs in expected linear time O(n). Each level we divide the array in half and search only in one of the two subarrays. On average, the summation of the lengths of the arrays processed is:
n + n/2 + n/4 + n/8 + …… = 2n
So the total running time is \(O(2n) = O(n)\).
This is much more efficient than any sorting algorithm we have seen, which run in time at least O(n log n).
Reference: http://en.wikipedia.org/wiki/Selection_algorithm
The Random Class
The java.util.Random class is a class for pseudorandom number generators. A pseudorandom number generator produces numbers based on certain calculations with an initial seed value. The numbers produced are claimed to look random, although they are generated by a deterministic process.
The following are some useful methods of the class. Reference: http://docs.oracle.com/javase/7/docs/api/java/util/Random.html
Constructors and Methods
- Random() Creates a new random number generator.
- Random(long seed) Creates a new random number generator using a single long seed.
- boolean nextBoolean() Returns the next pseudorandom, uniformly distributed boolean value from this random number generator’s sequence.
- double nextDouble() Returns the next pseudorandom, uniformly distributed double value between 0.0 and 1.0 from this random number generator’s sequence.
- int nextInt(int n) Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator’s sequence.
If we wish to generate the same sequence of random numbers each time (for example, for debugging purpose), we may use the constructor “Random(long seed)” by using the same seed.
Simulation
Randomness is essential for simulation. Due to the complication of real world problems, researchers in many areas (not only computer science, mathematics, physics, but also finance and economics) use random simulations and then make decisions based on analyzing the statistical results. But be aware that, oftentimes the decisions made are so wrong that even the most intelligent people lose lots of money (See this story on how Nobel prize winners lose $4.6 billion in less than four months http://en.wikipedia.org/wiki/Long-Term_Capital_Management).
Next, we will write a program to simulate random walks. A random walk is a path that takes successive random steps. For example, a one-dimensional random walk on the integer number line starts at 0, and at each step moves +1 (right) or -1 (left) with equal probability.
The next method simulates a random walk with the specified length.
public static void walk(int n)
{
int x = 0;
Random random = new Random();
for (int i = 0; i < n; i++)
{
int r = random.nextInt(2);
if (r == 0)
x--;
else
x++;
System.out.println(x);
}
}
The following method simulates random walks for numTrys times; each time the walk takes numSteps steps. It counts the ending location of the walks, and prints out the countings.
public static void walkTest(int numTrys, int numSteps)
{
int x = 0;
Random random = new Random();
int[] counts = new int[numSteps * 2 + 1];// counts of the final position
for (int k = 0; k < numTrys; k++)
{
x = 0;
for (int i = 0; i < numSteps; i++) // one round of walk
{
int r = random.nextInt(2);
if (r == 0)
x--;
else
x++;
}
counts[x + numSteps]++;
}
for (int k = 0; k < numSteps * 2 + 1; k++)
{
System.out.println("x = " + (k - numSteps) + ", \tcount:" +
counts[k] + ", \tprobability: " + (double) counts[k]/numTrys);
}
}