MMP.10:5.2 - Preserve existence while repairing a count

An optional assignment gives each of two named requests either no selected option or one of options 0 and 1. Different requests may select the same option. This is a partial function from the two requests to {0,1}. Each request has three possibilities, so there are nine assignments.

Suppose the storage format gives each request two bits: d says whether an option is defined, and q gives its value when defined. When d=0, q is ignored. All sixteen four-bit records denote valid partial assignments. Every assignment has a record, so the representation can support an existence query with translated requirements.

It does not preserve the count. The empty assignment has four records, each of the four assignments defined on exactly one request has two records, and each of the four total assignments has one record. Thus 4 + 4*2 + 4 = 16. Uniform selection among records gives probability 4/16 to the empty assignment and 1/16 to each total assignment, rather than the 1/9 obtained by uniform selection among assignments.

For a count or uniform assignment sample, one repair is the structural condition d=0 implies q=0 for each request. There are now three admissible bit pairs per request and nine records, one per assignment. Another is a single variable with domain {absent,0,1} per request. If the sixteen-record storage representation must remain, group or weight its records using the multiplicities instead. To sample the nine assignments uniformly, give each record of an assignment with m records probability 1/(9*m). The probabilities of all m records then sum to 1/9 for that assignment. Thus each record of the empty assignment receives 1/36, each record of a one-request assignment 1/18, and each total-assignment record 1/9. C.29.1 supplies the required correspondence; MMP.7 supplies a probability law when sampling is the intended operation.

The original existence use can remain sufficient. The new count or sampling question exposes the need for the additional construction. No change in the underlying possible assignments is intended.