Page 4 of 4
Working out the matrix product
To work out the matrix product we have to form sums involving the matrix elements a(i,j) and the vector elements b(k) to be precise
y(i)=sum over all j of a(i,j)*b(j)
This isn’t the place to be teaching matrix algebra, but it comes down to multiplying the elements row j in the matrix by the corresponding elements of vector and adding them up  usually said as "row times column".
How to multiply a vector by a matrix
Computing this very nonrandom value using random numbers seems a very unlikely prospect but it is fairly easy.
For the moment let's suppose that all the values in the matrix are positive and less one and that each row adds up to one. This condition allows us to treat the rows as probabilities of something happening.
Focus for a moment on a single row  its entries give you the probability of some event occurring.
To simulate these events all you do is set up a number of random number generators R(i) one for each row of the matrix. Each random number generator is set up so that it returns b(j) i.e a value in the B vector, with probability a(i,j) . For example, if the matrix A was
A= (0.5 0.3 0.2) (0.2 0.1 0.7)
and the vector b was
(4.3) b= (6.2) (3.2)
Then for the first row of the matrix we would create a random number generator R(1) that produced 4.3 with probability 0.5, 6.2 with probability 0.3 and 3.2 with probability 0.2. For the second row we would create a random number generator R(2) that produced 4.3 with probability 0.2, 6.2 with probability 0.1 and 3.2 with probability 0.7.
That is each random number generator returns the elements of the vector with probabilities given by the rows of the matrix – this can be achieved using the simple methods described earlier.
Now we can forget about matrix multiplication and simply run the random number generators  one for each row. We run the simulation and work out the average value produced by each of the random number generators. The resulting vector of averages one from each random number generator estimates the vector we want i.e. y.
In terms of our earlier example once we have R(1) and R(2) we would run them and work out the average value they produced. This average is an estimate of the result of multiplying the vector b by the matrix A.
That is:
y=(y(1))= (mean of R(1)) =Ab (y(2)) (mean of R(2))
I don’t know if you’ll be impressed by this demonstration of how randomness can be used to get an estimate of an answer that seems to have nothing to do with chance  but you should be.
Let's look at a simple JavaScript program to implement this algorithm to see how easy it really is. First we need two random number generators R1 and R1:
function R1() {
var r = Math.random();
if (r < 0.5) return 4.3;
if (r < 0.5 + 0.3) return 6.2;
return 3.2
}
function R2() {
var r = Math.random();
if (r < 0.2) return 4.3;
if (r < 0.2 + 0.1) return 6.2;
return 3.2;
}
These use the "size of interval" method described in the introduction to generate random numbers with the specified probabilities. Now all we have to do is to write a loop that generates the appropriate random numbers using R1 and R2 and work out the mean:
var num = 100;
var r1mean = 0;
var r2mean = 0;
var total = 0;
for (var i = 1; i <= num; i++) {
r1mean = r1mean + R1();
r2mean = r2mean + R2();
total++; Text1.value = r1mean / total;
Text2.value = r2mean / total;
}
If you try this out using Firefox say you should get results something like:
n R1 R2 100 4.669 3.63799 1000 4.6696 3.75449 10000 4.6552 3.71641 100000 4.6479 3.71656 1000000 4.6510 3.72015
which should be compared to the exact result R1=4.65 R2=3.72
The complete program as a simple HTML page is:
<!DOCTYPE html>
<html lang="en">
<head> <meta charset="utf8" />
<title>Matrix Multiply</title>
</head>
<body>
<input type="text" id="Text1"/>
<br/>
<input type="text" id="Text2"/>
<script>
function R1() {
var r = Math.random();
if (r < 0.5) return 4.3;
if (r < 0.5 + 0.3) return 6.2; return 3.2
}
function R2() {
var r = Math.random();
if (r < 0.2) return 4.3;
if (r < 0.2 + 0.1) return 6.2; return 3.2;
}
var num = 100;
var r1mean = 0;
var r2mean = 0;
var total = 0;
for (var i = 1; i <= num; i++) {
r1mean = r1mean + R1();
r2mean = r2mean + R2();
total++;
Text1.value = r1mean / total;
Text2.value = r2mean / total;
}
</script>
</body>
</html>
This is the beginning of a wide range of computing applications that use random numbers to get at answers that would otherwise be too difficult to compute exactly.
Who needs quantum computers when you have Monte Carlo to play with…
Data Compression The Dictionary Way
One of the most important lossless forms of compression is the LZW dictionary based method. It turns up in lots of compression utilities  ZIP, Compress, Deflate and in GIF and PNG format files. It is [ ... ]

Computational Complexity
A lightning guide to the basic ideas of computational complexity without the maths or the proofs. It's almost more fun than programming!
 Other Articles 
<ASIN:352740760X>
<ASIN:0812975219>
<ASIN:0387942823>
