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