The Combinatorics of Distributions

Supplemental Material

Bernd Günther

Introduction

An application to coding theory is given in this supplemental notebook.

The set of all permissible distributions can be constructed inductively on m by specifying three pieces of data:

The subset J of boxes containing at least one object of class less than m; denote its size by j.

The distribution of objects of class less than m over J.

The subset of J containing an object of class m; its size necessarily equals w-k+j.

This gives rise to the following formula and provides us with a rule of construction for the actual set of all distributions:

B(m,w,k)=(∑_(j=k-w)^k)B(m-1,w,j)(({{k}, {j}}))(({{j}, {w-k+j}})).

The package CombDistrib.m is available from www.mathematica-journal.com/data/uploads/2011/06/CombDistrib.m.

Get["CombDistrib.m",Path->NotebookDirectory[]];

Needs["Combinatorica`"]//Quiet

bSet[1,w_,k_]:=If[k==w,{ConstantArray[{1},w]},error]

bSet[m_,w_,k_]:= 
Module[{A,f},f[pred_,cov_,spill_]:=( A=ConstantArray[Range[0],k];Do[A[[cov[[i]]]]=If[MemberQ[spill,i],Append[pred[[i]],m],pred[[i]]],{i,Length[cov]}];Do[If[MemberQ[cov,i],,A[[i]]={m}],{i,k}];A); If[k≥w&&k≤m w,Flatten[Table[Flatten[Outer[f,bSet[m-1,w,j],KSubsets[Range[k],j],KSubsets[Range[j],w+j-k],1],2],{j,Max[w,k-w],Min[k,(m-1) w]}],1],error]]

TableForm[bSet[2,3,4],TableDepth->2,TableHeadings->Automatic]

Each column of the table corresponds to a box; each row contains three objects of type 1 and three objects of type 2. There are 12 admissible distributions.

numdistrib[2,3,4]

Simulation of Superimposed Random Coding

We imagine a large database comprised of R records, each of which is characterized by N properties. The database must be able to produce the collection of all records satisfying a much smaller number of properties than N very quickly upon request. A complete scan of N R Boolean values is probably not the most efficient way to do this, in particular if the value true is sparse. An easy strategy that has been traditionally popular in scientific databases and that is applicable if it is permitted to add a small number of fakes (idiomatically called “false drops”) to the set of correct search results, is superimposed random coding [, , ].

In it, each property is no longer characterized by a Boolean value but by a binary code word of length n≪N and of weight w, which means the code word consists of w randomly chosen 1-bits and n-w 0-bits. The list of all properties under consideration thus leads to a code book of R entries. Then each record is assigned the superposition of all code words corresponding to properties satisfied by the record. For instance, if a record has two properties with code words 010010 and 011000 it is assigned the superposition 011010. The totality of all superpositions now comprises a bit pattern of size n R that is significantly smaller than the original one. For searches, the test properties are subjected to the same superposition procedure, and the set of all records is collected whose bit pattern covers that of the search pattern.

If we consider the bit positions as boxes and the 1-bits corresponding to a particular property as objects of a kind, then it is quite clear that with probability

(Subscript[p, k])=B(m,w,k)(({{n}, {k}}))(((({{n}, {w}})))^(-m)),

the code word corresponding to a record with m properties will have k 1-bits; the same equation as (3) in “The Combinatorics of Distributions.” Similarly, if we are searching for ℓ characteristics, our test pattern will have s 1-bits with probability

(Subscript[p, s])'=B(ℓ,w,s)(({{n}, {s}}))(((({{n}, {w}})))^(-ℓ)) .

A tentative match is obtained if all s 1-bits of the test pattern are among the k 1-bits of the target string. This happens if ℓ'⩽ℓ of the search characteristics are actually satisfied and the remaining ℓ-ℓ' code words are covered at random. For ℓ=ℓ' we have a proper match, otherwise a false drop. For superimposed random coding to be useful, the number of false drops must be small, so they are what we are concerned with in this section. We restrict our attention to the most unfavorable case: ℓ'=0, that is, to a completely random match. The reader interested in the general case is referred to []. The probability of a completely random match (called “drop moment”) is

(Subscript[M, m]^((ℓ)))=(∑_(i,j,k))(({{n}, {i,j,k}}))(((({{n}, {i+j}})))^(-1))(((Subscript[p, i+j])(({{n}, {i}})))^(-1))(Subscript[p, i])',

with p and p' from () and (). This equation follows from the decomposition of the set of n bits into i bits belonging to the test pattern, j bits belonging to the target but not the test pattern, and the remaining k bits outside of the target pattern. We observe that for any set X of size k, (((({{n}, {k}})))^(-1))(Subscript[p, k]) equals the probability that X coincides with the set of 1-bits of the target string.

Equation () is numerically infeasible and requires simplification. By (1) of “The Combinatorics of Distributions,”

(∑_(s=w)^k)B(ℓ,w,s)(({{k}, {s}}))=(((({{k}, {w}})))^ℓ)

and this, in turn, leads to

(Subscript[M, m]^((ℓ)))=(((({{n}, {w}})))^(-m-ℓ))(∑_(k=w)^n)B(m,w,k)(({{n}, {k}}))(((({{k}, {w}})))^ℓ).

dropMoment[n_,w_,l_,m_]:=Binomial[n,w]^(-m-l) Sum[numdistrib[m,w,k] Binomial[n,k] Binomial[k,w]^l,{k,w,n}];

For our simulation we choose a code word length.

nCodeLength=500;

We assume that each database record is characterized by 80 positive properties.

mSourceWeight=80;

It was observed in [] that the optimal value of the code word weight w is obtained from ((((w/n)))^m)=(1/2).

wCodeWeight=Round[nCodeLength ( 1 -2 ^(-1/mSourceWeight))]

Our simulated search will be conducted with two test properties.

testCodeWeight=2

With this choice of parameters we can expect the following percentage of false drops.

N[dropMoment[nCodeLength,wCodeWeight,testCodeWeight,mSourceWeight]]

For our actual implementation it is more efficient to record the position of 1-bits instead of writing down the whole binary string; with this understanding the superposition of bit strings corresponds to the union of sets. A single code word is generated as follows.

codeWord:=Sort[RandomSample[Range[nCodeLength],wCodeWeight]]; SetAttributes[codeWord,Listable]

codeWord

A superposition of code words is generated like this.

codeWordAux[k_]:=codeWord

codeWordCombination[numItems_]:=Union[Flatten[Array[codeWordAux,numItems]]]

Notice that the dummy parameter k_ forces Mathematica to make a separate call of the random generator for each item of the array. A typical search word will look as follows.

codeWordCombination[testCodeWeight]

Here is a typical target word.

codeWordCombination[mSourceWeight]

Our simulation is now implemented in the following procedure.

Module[{targetWords,targetCombination,testWords,testCombination,iterationCounter, testIdx,targetIdx},iterationCounter=0; 
While[True,iterationCounter++;targetWords=Array[codeWordAux,mSourceWeight];targetCombination=Union[Flatten[targetWords]];
 testWords=Array[codeWordAux,testCodeWeight];
testCombination=Union[Flatten[testWords]];
If[Length[Complement[testCombination,targetCombination]]==0,Break[]]];
Print["wait time: " <> ToString[iterationCounter]];
For[testIdx=1,testIdx<=testCodeWeight,testIdx++,
Print["testWords[" <>ToString[testIdx] <> "]="<>ToString[testWords[[testIdx]]] <> " covered by"]
For[targetIdx=1,targetIdx≤mSourceWeight,targetIdx++,
If[Length[Intersection[testWords[[testIdx]],targetWords[[targetIdx]]]]>0,
Print["   targetWords["<>ToString[targetIdx]<>"]="<>ToString[targetWords[[targetIdx]]]]]]
]
]

We repeat the pattern-matching random experiment until the first false drop is encountered. With probability (q^(r-1))(1-q), q=(Subscript[M, m]^((ℓ))), we have to try r times and hence expect the following number of repetitions.

N[1/dropMoment[nCodeLength,wCodeWeight,testCodeWeight,mSourceWeight]]

However, because of the variance the actual results may scatter significantly; the variance is given below and is almost as great as the drop moment.

N[Sqrt[1-dropMoment[nCodeLength,wCodeWeight,testCodeWeight,mSourceWeight]]/dropMoment[nCodeLength,wCodeWeight,testCodeWeight,mSourceWeight]]

For a validation of equation () it is better to repeat the experiment a certain number of times and count false drops.

simulateFalseDrop:= Length[Complement[codeWordCombination[testCodeWeight],codeWordCombination[mSourceWeight]]]==0;
simulateFalseDropAux[k_]:=If[simulateFalseDrop,"false drop","ok"];
nRepetitions=10000;
TableForm[Tally[Array[simulateFalseDropAux,nRepetitions]]]

Asymptotics

Here is a plot of the coordinate transformation (7) of “The Combinatorics of Distributions” of the unit segment, which, for large m, drags almost the entire segment into a small neighborhood of 1.

invzeta[m_,t_]:=(1+Sum[t^k,{k,1,m-1}])/m;
ParametricPlot[{Tooltip[{invzeta[20,t],t},"m=20"],Tooltip[{invzeta[50,t],t},"m=50"], Tooltip[{invzeta[200,t],t},"m=200"]},{t,0,1},AxesOrigin->{0,0}, PlotRange->{{0,1},{0,1}},AxesLabel->{t,ζ}]

This is all the more unpleasant since (6) of “The Combinatorics of Distributions” is singular at ζ=1.

domfact[m_,z_]:=(1/(m*(1-z))-1/m)/
    (1/(1-z^m)-1)^((1-z^m)/(m*(1-z))); 
Plot[{Tooltip[domfact[20,z],"m=20"], Tooltip[domfact[50,z],"m=50"], Tooltip[domfact[200,z],"m=200"]}, 
  {z,0.9,1},AxesLabel->{ζ,(1/(m*(1-ζ))-1/m)/
     (1/(1 - ζ^m)-1)^((1-ζ^m)/(m*(1-ζ)))}]

Furthermore, the base of the dominating power in (6) of “The Combinatorics of Distributions” seems to suggest a maximum moving to the right with increasing m. This is a false impression created by the awkward parameter transformation.

Here is a plot of the parameter transformation (22) of “The Combinatorics of Distributions.”

ParametricPlot[{-(1-η)/Log[η],η},{η,0,1},AxesOrigin->{0,0},PlotRange->{{0,1},{0,1}},AxesLabel->{t,η}]

Here are the first four power series coefficients (Subscript[α, n]).

TableForm[Table[α[k],{k,0,3}],TableHeadings->{Table[k,{k,0,3}],None}]

The overall dominating term is the one raised to the (((m w))^th) power, here plotted against η and against t.

domTerm1=Plot[{((1-η)/η)^((1-η)/(-Log[η])) / (-Log[η])},{η,0,1},AxesOrigin->{0,0},AxesLabel->{η,(1/(-Log[η]))(((((1-η)/η)))^((1-η)/(-Log[η])))},AspectRatio->1];
domTerm2=ParametricPlot[{-(1-η)/Log[η],((1-η)/η)^((1-η)/(-Log[η])) / (-Log[η])},{η,Exp[-100],1},AxesOrigin->{0,0},PlotRange->{{0,1},{0,3/2}}, AxesLabel->{t,(1/(-Log[η]))(((((1-η)/η)))^((1-η)/(-Log[η])))},AspectRatio->1];
Show[GraphicsRow[{domTerm1,domTerm2}],ImageSize->Medium]

The maximum at η=(1/2), corresponding to (k/(m w))=t=(1/(2 log[2])), is clearly discernible. We append a numerical example comparing the exact number of distributions with its approximations by theorems 1 and 2 in “The Combinatorics of Distributions.”

maxDim=5;
zeta[t_,m_]:=x/.FindRoot[(∑_(j=0)^(m-1))x^j== m t,{x,1}];
numdistribaprx1[m_,w_,k_]:= 1 / ( Sqrt[ (2 π w)^m zeta[k/(m w),m]^m (1 - m w zeta[k/(m w),m]^(m-1)/k)]) (1/(1-zeta[k/(m w),m])-1)^(m w) (w/(k(1-zeta[k/(m w),m]))-1)^(-k);
etabt[t_]:=Re[x/.FindRoot[-(1-x)/Log[x]==t,{x,0.5}]];
alphaAux[n_,x_,y_]:=α[n]/.{t->x,η->y};
numdistribaprx2Aux[m_,w_,t_,η_]:=Sqrt[η^(w - 1)/((2*Pi*w)^m*
     (1 - t*η))]*
  (m*(((1 - η)/η)^((1 - η)/
        (-Log[η]))/(-Log[η])))^
   (m*w)*Exp[Sum[(alphaAux[n,t,η]*
      w)/m^(n - 1),{n, 2, 
     maxDim}]];
numdistribaprx2[m_,w_,k_]:=numdistribaprx2Aux[m,w,k/(m w),etabt[k/ (m w)]];
tblrow[m_,w_,k_]:={k,
ScientificForm[N[numdistrib[m,w,k]],4], ScientificForm[numdistribaprx1[m,w,k],4], ScientificForm[numdistribaprx2[m,w,k],4] ,EngineeringForm[N[k/ (m w)],4], EngineeringForm[N[zeta[k/ (m w),m]],4], EngineeringForm[N[etabt[k/ (m w)] ],4]};
tbl4display=Table[tblrow[20,20,k],{k,50,350,50}];
TableForm[tbl4display, TableHeadings -> {None,{"k","B(m,w,k)","Theorem 1","Theorem 2","t","ζ","η"}}]

References

C. S. Roberts, “Partial-Match Retrieval via the Method of Superimposed Codes,” Proceedings of the IEEE, 67(12), 1979 pp. 1624–1642. ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1455812.

B. Günther, “On the Probability Distribution of Superimposed Random Codes,” IEEE Transactions on Information Theory, 54(7), 2008 pp. 3206–3210. doi:10.1109/TIT.2008.924658.

B. Günther, “The Superposition Markov Chain: Finite Occupancy with Coupling, and the Asymptotics Thereof,” Probability and Mathematical Statistics, 30(1), 2010 pp. 103–120. www.math.uni.wroc.pl/~pms/publicationsArticle.php?nr=30.1&nrA=6&ppB=103&ppE=120.

B. Günther, “Error Analysis for Superimposed Random Coding,” International Journal of Computer Mathematics, 88(7), 2011 pp. 1373–1386. doi:10.1080/00207160.2010.501377.