Correcting randomisation function for chance of returning original value I am implementing some GDPR-related data randomisation code; the general rules I need to abide to are as follow:
For each user that requested to be GDPR deleted, there is a certain set of data fields that will need to be passed through a two-step randomisation function.
As an example let's say that we only care about one field, favourite colour, for which there are 6 possible values the user could have picked from (1:'red', 2:'blue', 3:'yellow', 4:'green', 5:'orange', 6:'purple').
For each field, we "roll the dice" separately. The first roll is to determine whether the field should be randomised or not based on some percentage.
Let's say, 15% (so, about 1/7 deleted user will actually get the field randomised).
If the above roll returns TRUE then we perform a second "dice roll", this time to assign a value at random among those that are "legal" for said field.
For our hypothetical user, the first dice roll returned TRUE and thus we will run the second function tasked with picking one of the six possible values listed above and replacing it from the original.
Returning the same value as the original is permitted.
Which means that even over a large sample of users, we will never achieve a situation by which "15% of users have their favourite colour field altered", because there is a chance that the random function will return the same value.
And we finally get to my actual question: if I wanted to account for that, and increase the initial probability so that the actual "on the ground" probability is 15%, how would I go about that?
I would assume it is
target_probability + target_probability * chance_of_value_within_set
so
0.15 + 0.15 * 0.1666... (1/6)
but lacking proper maths training I am not sure this is the right approach.
 A: That's almost, but not quite, correct. Let $I$ denote the initial probability, $T$ the target probability, and $C$ the chance of choosing the original value when trying to randomize (so that $1-C$ is the chance of altering the original value). The relationship between these quantities is
$$
T = I(1-C),
$$
since the proportion $I$ of all entries get an attempted randomization, and within those the proportion $1-C$ actually get randomized (on average). So if you know the target probability $T$ and the chance $C$ of choosing the original value, the best choice for the initial probability is
$$
I = \frac T{1-C},
$$
which is a bit larger than the $I+IC$ you proposed. In the given example, we would set the initial probability to be $\dfrac{0.15}{1-0.1666\cdots} = 0.18$.
A: You are almost correct.
Let $t$ be the target probability of getting a different value.
Suppose we are trying to achieve this probability by deciding to reroll with probability $r$, and choosing one of $n$ values when we reroll. Then the probability of getting a different value is $r \cdot \frac{n-1}{n}$: we must reroll, and give that we reroll, we must get one of the $n-1$ new values.
Solving, $t = r \cdot \frac{n-1}{n}$ gives $r = t \cdot \frac{n}{n-1}$, which we can split up into $r = t + \frac{t}{n-1}$. (Your formula is $t + \frac tn$, which is almost but not quite right.)
For example, in this case, there are $n=6$ possible colors, and we are aiming for a target probability of $t = 0.15$. Then we should take $r = 0.15 \cdot \frac65 = 0.18$: reroll with an $18\%$ probability.
