A simple hypothesis P is tested against a composite hypothesis ℚj, j ∈ {1,2, ...,k}, each ℚjbeing a product of n probability distributions. We consider the set of achievable false-positive error probability vectors for a generalized Neyman-Pearson test under a constraint on the probability of correct detection under P. Exact asymptotics (as n → ∞) are derived for this set, in particular the set is determined within an O(1) term.

The fingerprinting capacity has recently been derived as the value of a two-person zero-sum game. In this paper, we study the fingerprinting capacity games with k pirates in a new collusion model called the mixed digit model, which is inspired by the combined digit model of Škorić et al. For small k, the capacities along with optimal strategies for both players of the game are obtained explicitly. For large k, we extend our earlier asymptotic analysis for the binary alphabet with the marking assumption to q-ary alphabets with this general model and show that the capacity is asymptotic to A/(2k2ln q) where the constant A is specified as the maximin value of a functional game. Saddle-point solutions to the game are obtained using methods of variational calculus. For the special case of q-ary fingerprinting in the restricted digit model, we show that the interleaving attack is asymptotically optimal, a property that has motivated the design of optimized practical codes.

This paper studies the maximum achievable rate region of multiple access channels (MAC) for a given blocklength n and a desired error probability ϵ. The inner region for the discrete memoryless MAC is approximated by a single-lettered expression I - 1/√n Qinv(V, ϵ) where I is associated with the capacity pentagon bounds by Ahlswede and Liao, V is the MAC dispersion matrix, and Qinvis the complementary multivariate Gaussian cumulative distribution region. For outer regions, we provide general converse bounds for both average error probability and maximum error probability criteria, and a single-lettered approximation for the discrete memoryless MAC.

Fingerprinting capacity has recently been derived as the value of a two-person zero-sum game. In this work, we study fingerprinting capacity games with k pirates under the combined digit model proposed by Škorić et al. For small k, capacities along with optimal strategies for both players of the game are obtained explicitly. For large k, we extend our earlier asymptotic analysis for the binary alphabet to this general model and show that capacity is asymptotic to A/k2where the constant A is identified. Saddle-point solutions to the functional maximin game are obtained using methods of variational calculus.

We study a fingerprinting game in which the number of colluders and the collusion channel are unknown. The encoder embeds fingerprints into a host sequence and provides the decoder with the capability to trace back pirated copies to the colluders. Fingerprinting capacity has recently been derived as the limit value of a sequence of maximin games with mutual information as their payoff functions. However, these games generally do not admit saddle-point solutions and are very hard to solve numerically. Here under the so-called Boneh-Shaw marking assumption, we reformulate the capacity as the value of a single two-person zero-sum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is k and the fingerprinting alphabet is binary, we show that capacity decays quadratically with k. Furthermore, we prove rigorously that the asymptotic capacity is 1/(k221n2) and we confirm our earlier conjecture that Tardos' choice of the arcsine distribution asymptotically maximizes the mutual information payoff function while the interleaving attack minimizes it. Along with the asymptotics, numerical solutions to the game for small k are also presented.

We study a fingerprinting game in which the collusion channel is unknown. The encoder embeds fingerprints into a host sequence and provides the decoder with the capability to trace back pirated copies to the colluders. Fingerprinting capacity has recently been derived as the limit value of a sequence of maxmin games with mutual information as the payoff function. However, these games generally do not admit saddle-point solutions and are very hard to solve numerically. Here under the so-called Boneh-Shaw marking assumption, we reformulate the capacity as the value of a single two-person zero-sum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is k and the fingerprint alphabet is binary, we derive equations that can numerically solve the capacity game for arbitrary k. We also provide tight upper and lower bounds on the capacity. Finally, we discuss the asymptotic behavior of the fingerprinting game for large k and practical implementation issues.