Posts Tagged ‘ Simulation ’

Random sudokus [p-values]

May 21, 2010
By
Random sudokus [p-values]

I reran the program checking the distribution of the digits over 9 “diagonals” (obtained by acceptable permutations of rows and column) and this test again results in mostly small p-values. Over a million iterations, and the nine (dependent) diagonals, four p-values were below 0.01, three were below 0.1, and two were above (0.21 and 0.42).

Read more »

Random [uniform?] sudokus [corrected]

May 19, 2010
By
Random [uniform?] sudokus [corrected]

As the discrepancy in the sum of the nine probabilities seemed too blatant to be attributed to numerical error given the problem scale, I went and checked my R code for the probabilities and found a choose(9,3) instead of a choose(6,3) in the last line… The fit between the true distribution and the

Read more »

Random [uniform?] sudokus

May 19, 2010
By
Random [uniform?] sudokus

A longer run of the R code of yesterday with a million sudokus produced the following qqplot. It does look ok but no perfect. Actually, it looks very much like the graph of yesterday, although based on a 100-fold increase in the number of simulations. Now, if I test the adequation with a basic chi-square

Read more »

Random sudokus [test]

May 17, 2010
By
Random sudokus [test]

Robin Ryder pointed out to me that 3 is indeed the absolute minimum one could observe because of the block constraint (bon sang, mais c’est bien sûr !). The distribution of the series of 3 digits being independent over blocks, the theoretical distribution under uniformity can easily be simulated: #uniform distribution on the block diagonal

Read more »

Random sudokus

May 16, 2010
By
Random sudokus

After thinking about random sudokus for a few more weeks, I eventually came to read the paper by Newton and DeSalvo about the entropy of sudoku matrices. As written earlier, if we consider (as Newton and DeSakvo) a uniform distribution where the sudokus are drawn uniformly over the set of all sudokus, the entropy of

Read more »

Computational Statistics

May 9, 2010
By
Computational Statistics

Do not resort to Monte Carlo methods unnecessarily. When I received this 2009 Springer-Verlag book, Computational Statistics, by James Gentle a while ago, I briefly took a look at the table of contents and decided to have a better look later… Now that I have gone through the whole book, I can write a short

Read more »

Forsythe’s algorithm

May 8, 2010
By
Forsythe’s algorithm

In connection with the Bernoulli factory post of last week, Richard Brent arXived a short historical note recalling George Forsythe’s algorithm for simulating variables with density when (the extension to any upper bound is straightforward). The idea is to avoid computing the exponential function by simulating uniforms until since the probability of this event is

Read more »

The Bernoulli factory

April 22, 2010
By
The Bernoulli factory

A few months ago, Latuszyński, Kosmidis, Papaspiliopoulos and Roberts arXived a paper I should have noticed earlier as its topic is very much related to our paper with Randal Douc on the vanilla Rao-Blackwellisation scheme. It is motivated by the Bernoulli factory problem, which aims at (unbiasedly) estimating f(p) from an iid sequence of Bernoulli

Read more »

Sudokus more random than random!

April 18, 2010
By
Sudokus more random than random!

Darren Wraith pointed out this column about sudokus to me. It analyses the paper by Newton and De Salvo published in the Proceedings of the Royal Academy of Sciences A that I cannot access from home. The discussion contains this absurd sentence “Sudoku matrices are actually more random than randomly-generated matrices” which shows how mistreated

Read more »

A von Mises variate…

March 25, 2010
By
A von Mises variate…

Inspired from a mail that came along the previous random generation post the following question rised : How to draw random variates from the Von Mises distribution? First of all let’s check the pdf of the probability rule, it is , for . Ok, I admit that Bessels functions can be a bit frightening, but

Read more »