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

Thanks, I tried someting like this, but computation takes times for large
matrices

btransf    <-    function(y,X=length(y)^4)    { 
        N    <-    length(y)
        bm    <-    matrix(rep(1/N,N^2),N,N)
        for(j in 1:X){
                    coord    <-    sample(1:N,4,replace=T)
                    d    <-   
runif(1,0,min(bm[coord[1],coord[2]],bm[coord[3],coord[4]]))
                    bm[coord[1],coord[2]]    <-    bm[coord[1],coord[2]]-d 
                    bm[coord[3],coord[4]]    <-    bm[coord[3],coord[4]]-d
                    bm[coord[1],coord[4]]    <-    bm[coord[1],coord[4]]+d 
                    bm[coord[2],coord[3]]    <-    bm[coord[2],coord[3]]+d   
}
                    y.btransf    <-    bm%*%y
                    y.btransf    <-    y.btransf+(mean(y)-mean(y.btransf))
                    as.vector(y.btransf)    }

the fonction is designed to perform a mean-preserving transformation of a
vector.

----- 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, 14h58mn 13s
Objet : Re: [R] Generate a random bistochastic matrix

bistochastic.3x3 <- function() {
  B <- matrix(0, 3, 3)
  
  ## 2 df
  tmp.1 <- runif(3)
  B[1,] <- tmp.1/sum(tmp.1)
  
  ## 1 df
  tmp.2 <- runif(2)
  B[2:3, 1] <- (1-B[1,1]) * tmp.2/sum(tmp.2)
  
  ## 1 df
  B[2, 2] <- runif(1, max=min(1-B[1,2], 1-B[2,1]))
  
  ## Fill in the rest
  B[2,3] <- 1-sum(B[2, 1:2])
  B[3,2] <- 1-sum(B[1:2, 2])
  B[3,3] <- 1-sum(B[1:2, 3])
  
  B
}

B <- bistochastic.3x3()
apply(B, 1, sum)
apply(B, 2, sum)


To extend this to larger than 3x3 requires the same kind of
conditional generation of alternating rows and columns of the
matrix.  The hard part is the extension of the two-way conditioning
I illustrated in the B[2, 2] line.

Rich

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.

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

Thanks, I think it's a shrewd solution, but the problem is that it cannot
generate every N*N bistochastic matrix and every cell tends to 1/N as B tends to
infinity

Florent Bresson

----- Message d'origine ----
De : Dimitris Rizopoulos <dimitris.rizopoulos at med.kuleuven.be>
? : Florent Bresson <f_bresson at yahoo.fr>
Cc : r-help at stat.math.ethz.ch
Envoy? le : Lundi, 16 Octobre 2006, 16h35mn 02s
Objet : Re: [R] Generate a random bistochastic matrix

you can try something like the following:

B <- 10
N <- 5
mats <- r2dtable(B, rep(1, N), rep(1, N))
out <- matrix(0, N, N)
for(i in 1:length(mats))
    out <- out + mats[[i]]
out <- out / B
out
colSums(out)
rowSums(out)



I hope it helps.

Best,
Dimitris

----
Dimitris Rizopoulos
Ph.D. Student
Biostatistical Centre
School of Public Health
Catholic University of Leuven

Address: Kapucijnenvoer 35, Leuven, Belgium
Tel: +32/(0)16/336899
Fax: +32/(0)16/337015
Web: http://med.kuleuven.be/biostat/
     http://www.student.kuleuven.be/~m0390867/dimitris.htm


----- Original Message ----- 
From: "Florent Bresson" <f_bresson at yahoo.fr>
To: <r-help at stat.math.ethz.ch>
Sent: Monday, October 16, 2006 10:22 AM
Subject: [R] Generate a random bistochastic matrix


Please, I would like to generate a random bistochastic matrix, that is 
a squared matrix of non-negative numbers  with  each row and each 
column sum to 1, for example :

.2    .3    .5
.6    .3    .1
.2     .4     .4

I don't know of to code this. Do you have any idea ?

Thanks

Florent Bresson








___________________________________________________________________________



______________________________________________
R-help at stat.math.ethz.ch mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide 
http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.


Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

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

>>>>> "Florent" == Florent Bresson <f_bresson at
yahoo.fr>
>>>>>     on Mon, 16 Oct 2006 16:17:51 +0000 (GMT) writes:
    Florent> 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).

    [................]

uuhm;  not quite, in general!
Be more careful before you state such things!
It seems your claim would be equivalent to saying that my
function returned matrix entries very close to 1/N which is not
true:
If you do a small simulation with  my function and your  N = 20,

  mm <- replicate(100, bistochMat(20))
  str(mm)
  hist(mm)

you get a pretty reasonable result: The entries are on average
1/N (0.05 here), and I am expecting a somewhat skewed (to the
right) distribution which we get indeed.

Martin