R help - Oct 2006 - Re : Re : Generate a random bistochastic matrix

Yes, you're right. In fact, it's just an adaptation of a matlab command
and the author advises using N^4 replications that's why it's the
default in the function. The bistochastic matrix is not my subject of interest,
but I need it to perform some random tranformation of a vector of incomes.

Florent Bresson

----- Message d'origine ----
De : Richard M. Heiberger <rmh at temple.edu>
? : Florent Bresson <f_bresson at yahoo.fr>; r-help at stat.math.ethz.ch
Envoy? le : Lundi, 16 Octobre 2006, 16h23mn 39s
Objet : Re: Re : [R] Generate a random bistochastic matrix

I am sorry, I can't figure out what your function is doing.
Why do you have N^4 in the argument?  A matrix should have
N rows and N columns, that is, it should have length N^2.

The function returns a vector, not a matrix.

There is no example of its use.

I am guessing that your function somewhere uses a bistochastic matrix
as an intermediate calculation.  I recommend isolating the bistochastic
matrix function from the larger function that you have constructed.

PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.

Thanks, it's perfect for my needs.

----- Message d'origine ----
De : Martin Maechler <maechler at stat.math.ethz.ch>
? : Florent Bresson <f_bresson at yahoo.fr>
Cc : Richard M. Heiberger <rmh at temple.edu>; r-help at stat.math.ethz.ch
Envoy? le : Lundi, 16 Octobre 2006, 16h29mn 47s
Objet : Re: [R] Re :  Generate a random bistochastic matrix

A simpler approach --- as in similar problems ---
is to use an iterative solution  which works quite fast for any 'n'.
Interestingly, the number of necessary iterations seems to
*decrease* for increasing 'n' :

bistochMat <- function(n, tol = 1e-7, maxit = 1000)
{
    ## Purpose: Random bistochastic *square* matrix (M_{ij}):
    ##            M_{ij} >= 0;  sum_i M_{ij} = sum_j M_{ij} = 1   (for all i,
j)
    ## ----------------------------------------------------------------------
    ## Arguments: n: (n * n) matrix dimension;
    ## ----------------------------------------------------------------------
    ## Author: Martin Maechler, Date: 16 Oct 2006, 14:47
    stopifnot(maxit >= 1, tol >= 0)
    M <- matrix(runif(n*n), n,n)
    for(i in 1:maxit) {
    M <- M / outer((rM <- rowSums(M)), (cM <- colSums(M))) * sum(rM) /
n
    if(all(abs(c(rM,cM) - 1) < tol))
        break
    }
    ## cat("needed", i, "iterations\n")
    ## or rather
    attr(M, "iter") <- i
    M
}

attr(M <- bistochMat(70), "iter")
## typically:
## [1] 8

attr(M <- bistochMat(10), "iter")
## -> 13, 16, 15, 17, ...

set.seed(101) ; attr(M <- bistochMat(10), "iter")             ## 15
set.seed(101) ; attr(M <- bistochMat(10, tol = 1e-15), "iter")## 32

------------------------

Initially, I tried to solve the general [ n x m ] case.
It seems that needs a slightly smarter "bias correction"
instead of just 'sum(M) / n'.
If someone figures that out, please post your solution!

Regards,
Martin Maechler, ETH Zurich

Yes, I would like every generated matrix to be drawn from a uniform
distribution. Martin Maechler's solution was interesting but when I compute
the product of the obtained matrix with any N-vector Y, the resulting vector is
most of the time quite close to a vector like mean(Y)*rep(1,N).

Florent Bresson

----- Message d'origine ----
De : Rolf Turner <rolf at erdos.math.unb.ca>
? : f_bresson at yahoo.fr
Cc : r-help at stat.math.ethz.ch
Envoy? le : Lundi, 16 Octobre 2006, 17h50mn 24s
Objet : Re: [R] Re :  Generate a random bistochastic matrix

I don't think this idea has been suggested yet:

    (1) Form all n! n x n permutation matrices,
    say M_1, ..., M_K, K = n!.

    (2) Generate K independent uniform variates
    x_1, ..., x_k.

    (3) Renormalize these to sum to 1,
        x <- x/sum(x)

    (4) Form the convex combination

        M = x_1*M_1 + ... + x_K*M_K

M is a ``random'' doubly stochastic matrix.

The point is that the set of all doubly stochastic matrices
is a convex set in n^2-dimensional space, and the extreme
points are the permutation matrices.  I.e. the set of all
doubly stochastic matrices is the convex hull of the the
permuation matrices.

The resulting M will *not* be uniformly distributed on this
convex hull.  If you want a uniform distribution something
more is required.  It might be possible to effect uniformity
of the distribution, but my guess is that it would be a
hard problem.

                cheers,

                    Rolf Turner
                    rolf at math.unb.ca