What does Sparse Probes, Hidden Discounts conclude, in numbers, about “The Phase Diagram: Probe Share, Sparsity and the Value of Knowing the Sign”?

Answer: Chapter 4 draws the phase diagram of zero-one baskets and prices the knowledge that there are discounts only.

Scope of the numbers: Its items, amounts, costs and rivals are illustrative and all calculations are generated by its programs; it is a general business reference, not a legal opinion. Marked boxes separate published evidence, runnable Python calculations (18 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python only

rho\delta0.10.20.30.40.50.60.70.80.9
0.9.......19
0.8...1.136#
0.7....1369#
0.6..3.16###
0.5.1168####
0.41189#####
0.328#######
0.22########
0.18########
highest rho with 5+ of 10 exact, by delta:
0.1:0.1 0.2:0.3 0.3:0.4 0.4:0.5 0.5:0.5 0.6:0.6 0.7:0.7 0.8:0.8 0.9:0.9
Show the full program
# Chapter 4. p41: the Donoho-Tanner phase diagram for basket probes.
# Model: n = 50 items; delta = m/n is the probe share, rho = k/m the
# discounts per probe. Each cell runs 10 seeded trials of nonnegative
# basis pursuit (float simplex) with 0/1 baskets (chance 1/2) and
# discounts of 5 to 60 yuan; the digit is the number of exact
# recoveries ('#' = 10 of 10, '.' = 0). Illustrative; seed 20261141.
import math
import random
from fractions import Fraction as Fr

def esum(v):
    s = Fr(0)
    for t in v:
        s += t
    return s


def lp_min(A, b, c, exact=False):
    # min c.x subject to A x = b, x >= 0: two-phase tableau simplex.
    # b is nudged to b + A d (d_j > 0, tiny, distinct) so that no
    # pivot is degenerate; the final basis is re-applied to the true
    # b through B^-1. Exact mode uses fractions and Bland's rule.
    m, n = len(A), len(A[0])
    cv = Fr if exact else float
    add = esum if exact else math.fsum
    tol = 0 if exact else 1e-9
    big = 1 + max(abs(v) for v in b)
    d = [Fr(1, 2 ** (30 + j)) if exact else
         1e-7 * big * (0.5 + (0.6180339887 * (j + 1)) % 1.0)
         for j in range(n)]
    T, sg = [], []
    for i in range(m):
        s = -1 if b[i] < 0 else 1
        row = [cv(s * v) for v in A[i]] + [cv(0)] * (m + 1)
        row[n + i] = cv(1)
        row[-1] = cv(abs(b[i])) + s * add([A[i][j] * d[j]
                                           for j in range(n)])
        T.append(row)
        sg.append(s)
    basis = [n + i for i in range(m)]
    W = n + m

    def pivot(r, q, z):
        pv = T[r][q]
        T[r] = [v / pv for v in T[r]]
        pr = T[r]
        nz = [j for j in range(W + 1) if pr[j] != 0]
        for row in T + [z]:
            f = row[q]
            if row is not pr and f != 0:
                for j in nz:
                    row[j] -= f * pr[j]
        basis[r] = q

    def run(z, stop):
        piv = 0
        while not (stop and -z[W] <= tol):
            q, best = -1, -1e-7
            for j in range(n):
                if exact and z[j] < 0:
                    q = j
                    break
                if not exact and z[j] < best:
                    q, best = j, z[j]
            if q < 0:
                return piv
            r, rt = -1, None
            for i in range(m):
                if T[i][q] > tol:
                    t = T[i][W] / T[i][q]
                    if rt is None or t < rt:
                        r, rt = i, t
            pivot(r, q, z)
            piv += 1
        return piv

    z = [cv(0)] * (W + 1)
    for j in list(range(n)) + [W]:
        z[j] = -add([T[i][j] for i in range(m)])
    piv = run(z, True)
    if -z[W] > (0 if exact else 1e-6 * big):
        return None, None, piv
    z = [cv(v) for v in c] + [cv(0)] * (m + 1)
    for i in range(m):
        if basis[i] < n and z[basis[i]] != 0:
            f = z[basis[i]]
            z = [z[j] - f * T[i][j] for j in range(W + 1)]
    piv += run(z, False)
    x = [cv(0)] * n
    for i in range(m):
        if basis[i] < n:
            x[basis[i]] = add([T[i][n + j] * abs(b[j])
                               for j in range(m)])
    lam = [-sg[j] * z[n + j] for j in range(m)]
    return x, lam, piv


def trial(rng, n, k, m):
    A = [[1 if rng.random() < 0.5 else 0 for _ in range(n)]
         for _ in range(m)]
    x = [0] * n
    for j in rng.sample(range(n), k):
        x[j] = rng.randint(5, 60)
    y = [int(math.fsum(A[i][j] * x[j] for j in range(n)))
         for i in range(m)]
    xh, _, _ = lp_min(A, y, [1] * n)
    return xh is not None and [round(v) for v in xh] == x


rng = random.Random(20261141)
n, T = 50, 10
deltas = [d / 10 for d in range(1, 10)]
rhos = [r / 10 for r in range(9, 0, -1)]
edge = {}
print("rho\delta " + " ".join("%4.1f" % d for d in deltas))
for rho in rhos:
    cells = []
    for d in deltas:
        m = round(d * n)
        k = max(1, round(rho * m))
        hit = 0
        for _ in range(T):
            hit += trial(rng, n, k, m)
        cells.append("#" if hit == T else ("." if hit == 0 else str(hit)))
        if hit >= T / 2:
            edge[d] = max(edge.get(d, 0), rho)
    print("   %3.1f    " % rho + " ".join("%4s" % c for c in cells))
print("highest rho with 5+ of 10 exact, by delta:")
print("  " + " ".join("%.1f:%.1f" % (d, edge.get(d, 0)) for d in deltas))

Single source and citation

Fan, Y. (2026). Compressed Sensing and L1 Minimisation: Sparse Mystery-Shopper Probes and the Exact Recovery of Competitors' Hidden-Discount Matrices (Version 1.0.0), Chapter 4: The Phase Diagram: Probe Share, Sparsity and the Value of Knowing the Sign. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-242 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026242,
  author    = {Fan, Yafu},
  title     = {Compressed Sensing and L1 Minimisation: Sparse Mystery-Shopper Probes and the Exact Recovery of Competitors' Hidden-Discount Matrices},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book