Putting things together, this means that a random database can be sampled from the MaxEnt model using a double for-loop over all distinct λer i and all distinct λec j
, with in total at most 2s **combinations. For each of these combinations,**
all entries in intersections of the rows and columns with these Lagrange multipliers can be sampled efficiently using the geometric distribution as outlined above.

The total complexity thus consists of two components: sampling the geometric distribution, and the overhead of looping over all combinations of row and column Lagrange multipliers. The latter clearly has a complexity bounded by s**. The former has a complexity proportional to the number of non-zeros**
in the sampled matrix, which is proportional to s **in expectation and tightly**
concentrated around it. Hence, the expected complexity is O(s**) with the actual**
complexity tightly concentrated around this.

We should point out that sampling from the MaxEnt model cannot be used as a substitute for swapping if the row and column sums need to be preserved exactly rather than in expectation. This may be the case for categorical data represented by a binary matrix where each column corresponds to **an attributevalue. However, in that case a MaxEnt model can be fitted on the categorical**
representation of the data. Then the constraints will not be on the row and column marginals, but on the number of times each of the attribute values is seen for each of the attributes. Without going into detail, the MaxEnt distribution would then be a product of categorical distributions (one for each **database** entry), rather than a product Bernoulli distributions.

## 5.2 The Maxent Model To Define Interestingness Of Tiles

The above shows that the MaxEnt model can be used as an alternative to swap randomizations for the generation of randomized versions of **databases. A** comparison with swap randomizations for this purpose of randomizing databases can therefore be made, and the empirical results reported in Sec. **7 show that**
the MaxEnt model allows one to generate randomizations more efficiently than using the swap randomizations strategy.

However, what is more important is that the explicit analytical nature of the MaxEnt model allows one to use it in situations where swap randomizations would be impractical, such as for defining new and subjective measures of interestingness of patterns.

To demonstrate the use of the MaxEnt model for this purpose, we **here**
work out a specific example. In particular, we will focus on binary databases D ∈ {0, 1}
m×n **and a kind of pattern known as a tile (Geerts et al, 2004) that is**
denoted as τ and defined as an ordered pair of a set of rows I ⊆ {1, . . . , m} and a set of columns J ⊆ {1, . . . , n}, i.e. τ = (I, J). We say that a tile τ = (**I, J**)
is present in the database D, denoted as τ ∈ D, iff D(i, j**) = 1 for all** i ∈ I
and j ∈ J. Furthermore, we say that the database entry at row i **and column** j is contained in a tile τ = (I, J) iff i ∈ I and j ∈ J**, and we denote this more** concisely as (**i, j**) ∈ τ.