How to add noise to obfuscate patterns in data I have a program that generates output data depending on the inputs it is given. Lets say the data generated is a list of n items where each item is a natural number between 1 and k. I need to release this data in such a way that an observer can't discern any patterns (e.g. if the ith item is 10, that is always followed by 15, 25, etc) or counts (the number of times a given number appears in the output list). So I want to add noise to this output list to achieve this property. How do I go about doing this?  
I've looked a bit into Differential Privacy but I don't think this is applicable since there is no notion of "plausible deniability" with regards to my problem. Also, it is quite hard for me to determine the "sensitivity" of the output list to changes in the input because the underlying application is very complex. One point to note is that multiple runs of the application will produce random lists but the underlying patterns between the data items will be maintained and this is what I'd like to hide with noise.
 A: I am a little late. Differential privacy is applicable for counts queries. This is one of your cases. The sensitivity depends on each case. As I understand your problem the sensitivity is 1. Sensitivity is the maximum possible value you can obtain when you add one element on the data(your list) when you request the query (counts). If you add another element the max value it can have is 1, because it can change only the count of one element by one.
In order to achieve this noise, you could add a noise distributed with $Lap(0,\Delta f/\epsilon)$ where $\Delta f$=1 is the sensitivity we were talking about. $\epsilon$ is a value you decide to give, try different values. Laplace works very well with count queries. Formally is defined as :
\begin{equation*}
    \mathcal{T}(x_1,...,x_n)= count(x_1,...,x_n) + (Y_1,...,Y_k) \ \ where \  Y_i  \sim Lap(0,1/\epsilon)
\end{equation*}
The function to count for every group i is then :
$$
    count(x_i) = \sum_{i=1}^m k_i,k_i\in B_i
$$
$B_i=\{n_1,..,x_n\}$ are the possible groups and where $k_i$:
\begin{equation*}
    k_i= 
    \begin{cases}
    1  & \text{if $i\in B_i$ } \\
     0 & \text{if $i\notin B_i$  }
\end{cases}
\end{equation*}
I hope this helps.
