The paper concerns sampling from a data stream {$S_{i}$}: at a moment t the sampler should hold a value $S_{t-j}$, where j$\in${0,$\ldots$,n-1} should be chosen according to an a priori specified probability distribution D on {0,$\ldots$,n-1}, where D as well as the window size n are fixed and do not depend on t. We assume that the sampler has a constant size memory, while n might be large, so the sampler cannot remember the last n values of the stream except for a few. The problem is that the window of the last n elements changes at each step and when we have to resample, then almost all values from which we have to choose are already forgotten. The case of uniform distribution D has been considered by Braverman, Ostrovsky, and Zaniolo in 2013. We present an alternative generic approach based on specific Markov chains called devil’s staircases. Unlike the previous solution, it is not limited to the uniform distribution: it generates a sample according to any admissible distribution in the window of size n and uses memory of size $\mathrm{O}(1)$. We provide sufficient conditions for the distribution D to be admissible. Although the class of such distributions is quite wide from the point of view of practical applications, we show some natural limitations for this class.

A majority of research in communication in wireless networks is devoted to maximizing information flow, improving connectivity, or making the system robust against physical perturbations such as jamming. In this work we study how intentional jamming can be used for assuring privacy of wireless communication under the popular Signal-to-Interference-plus- Noise-Ratio (SINR) model. The considered problem, called Zone-restriction with Max-coverage, is as follows: how to place a number of jamming stations in order to generate interference that block the signal of given genuine stations in a specified restricted area, i.e., by making the SINR value of the genuine stations’ signal below a pre-defined threshold in that area. In the construction of algorithms, we aim at optimizing both the accuracy – by minimizing the impact of the jamming stations to the area of genuine communication and by maximizing their influence to the area that should be jammed, as well as the energy consumption of the jamming stations. We present several solutions in various settings of the network, which often lead to challenging analysis even in relatively simple cases. Among others, we show that, surprisingly, it is possible to jam arbitrarily large areas by jammers using total energy arbitrarily close to zero.