# Probability and roundoff errors

#### jcarne

##### New Member
Hi,

I work on a real life problem with roundoff errors and found a glitch in my thinking. If someone knows how to solve this problem I appreciate it.

The problem:

I have a container with n objects inside. I can weight the full container (Q), individual objects ($$q_i$$) and the empty container ($$q_o$$).

We have then that: $$q_0 + \sum\limits_{i=1}^n q_i = Q$$

The scale round the weight to the nearest integer.

Then I have $$n+2$$ measures (Empty container, Full container and n objects)

$$\hat{Q} = Q + \epsilon_Q$$
$$\hat{q_i} = q_i + \epsilon_i$$ for i:0..n

where $$\epsilon_i$$ and $$\epsilon_Q$$ are random variables iid $$U(-\frac{1}{2},+\frac{1}{2})$$ (here it is my error - see Note)

I want measure de difference between $$(\hat{Q} - \hat{q_0})$$ and $$\sum\limits_{i=1}^n \hat{q_i}$$

I'm going to find $$P(|\sum\limits_{i=1}^n \hat{q_i} - (\hat{Q} - \hat{q_0})| \geq k)$$

$$\sum\limits_{i=1}^n \hat{q_i} - (\hat{Q} - \hat{Q_0}) = \sum\limits_{i=1}^n (q_i + \epsilon_i) - (Q + \epsilon_Q - q_0 - \epsilon_0) = \sum\limits_{i=1}^n q_i - (Q - q_0) + \sum\limits_{i=1}^n \epsilon_i - (\epsilon_Q - \epsilon_0) =$$$$\sum\limits_{i=0}^n \epsilon_i - \epsilon_Q$$

Defining $$\tau_Q = -\epsilon_Q$$
We have that $$\tau_Q$$ is $$U(-\frac{1}{2},+\frac{1}{2})$$

Then $$\sum\limits_{i=0}^n \epsilon_i + \tau_Q$$ is a sum of n + 2 iid random variables $$U(-\frac{1}{2},+\frac{1}{2})$$

Note: $$\sum\limits_{i=0}^n \epsilon_i + \tau_Q$$ is integer then $$\tau_Q$$ is not independent from $$\epsilon_i$$

By Central Limit theorem:

$$\lim_{n \rightarrow \infty} P(-z < \frac{S_{n+2} - n\mu}{\sigma\sqrt{n+2}} < z) = \Phi(z) - \Phi(-z)$$

In this case $$U(-\frac{1}{2},+\frac{1}{2})$$ has $$\mu = 0$$ and $$\sigma^2 = \frac{1}{12}$$

$$z = \frac{k}{\sigma\sqrt{n+2}} = \frac{k}{\sqrt{\frac{n + 2}{12}}} = \frac{2\cdot k}{\sqrt{\frac{n + 2}{3}}}$$

Then
$$\lim_{n \rightarrow \infty} P(|\frac{S_{n+2} - n\mu}{\sigma\sqrt{n+2}}| \leq \frac{2\cdot k}{\sqrt{\frac{n + 2}{3}}}) = \Phi(\frac{2\cdot k}{\sqrt{\frac{n + 2}{3}}}) - \Phi(-\frac{2\cdot k}{\sqrt{\frac{n + 2}{3}}})$$

$$\lim_{n \rightarrow \infty} P(|\frac{S_{n+2} - n\mu}{\sigma\sqrt{n+2}}| > \frac{2\cdot k}{\sqrt{\frac{n + 2}{3}}}) = 1 - (\Phi(\frac{2\cdot k}{\sqrt{\frac{n + 2}{3}}}) - \Phi(-\frac{2\cdot k}{\sqrt{\frac{n + 2}{3}}}))$$

$$P(|\sum\limits_{i=1}^n \hat{q_i} - (\hat{Q} - \hat{q_0})| > k) = 1 - \Phi(\frac{2\cdot k}{\sqrt{\frac{n + 2}{3}}}) + \Phi(-\frac{2\cdot k}{\sqrt{\frac{n + 2}{3}}})$$

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------

I think I solved it.

Take a look at the next table

$$\begin{tabular}{|c|c|c|c|} \hline \sum\limits_{i=0}^n \epsilon_i & \epsilon_Q & |\sum\limits_{i=0}^n \epsilon_i - \epsilon_Q| & [|\sum\limits_{i=0}^n \epsilon_i|] \\ \hline -2.37 & -0.37 & 2.0 & 2.0 \\ -4.46 & -0.46 & 4.0 & 4.0 \\ -2.64 & 0.36 & 3.0 & 3.0 \\ 1.06 & 0.06 & 1.0 & 1.0 \\ 1.53 & -0.47 & 2.0 & 2.0 \\ \hline \end{tabular}$$

Note that $$-\epsilon_Q$$ don't afect the final error. I only need to work with $$|\sum\limits_{i=0}^n \epsilon_i|$$ rounded to the nearest integer (fourth column).

Then $$P(|\sum\limits_{i=0}^n \epsilon_i - \epsilon_Q| \ge k) = P(|\sum\limits_{i=0}^n \epsilon_i| \ge k - \frac{1}{2}) = P(|S_{n+1}| \ge k - \frac{1}{2})$$

Where $$S_{n+1}$$ is a sum of $$n+1$$ iid random variables $$U(-\frac{1}{2},+\frac{1}{2})$$

$$P(|S_{n+1}| \ge k - \frac{1}{2}) = 1-P(|S_{n+1}| < k - \frac{1}{2})$$
$$= 1-P(-k+\frac{1}{2} < S_{n+1} < k - \frac{1}{2})$$
$$= 1-[P(S_{n+1} < k - \frac{1}{2}) - P(S_{n+1} \le -k + \frac{1}{2})]$$
$$= 1-P(S_{n+1} < k - \frac{1}{2}) + P(S_{n+1} \le -k + \frac{1}{2})$$
$$= 1-P(\frac{S_{n+1}}{\sigma \sqrt{n+1}} < \frac{k - \frac{1}{2}}{\sigma \sqrt{n+1}}) + P(\frac{S_{n+1}}{\sigma \sqrt{n+1}} \le \frac{-k + \frac{1}{2}}{\sigma \sqrt{n+1}})$$

$$\sigma^2=\frac{1}{12}$$

$$= 1-P(\frac{S_{n+1}}{\sqrt{\frac{1}{12}} \sqrt{n+1}} < \frac{k - \frac{1}{2}}{\sqrt{\frac{1}{12}} \sqrt{n+1}}) + P(\frac{S_{n+1}}{\sqrt{\frac{1}{12}} \sqrt{n+1}} \le \frac{-k + \frac{1}{2}}{\sqrt{\frac{1}{12}} \sqrt{n+1}})$$

$$= 1-P(\frac{S_{n+1}}{\sqrt{\frac{1}{12}} \sqrt{n+1}} < \frac{\sqrt{3}\cdot {(2k - 1)}}{\sqrt{n+1}}) + P(\frac{S_{n+1}}{\sqrt{\frac{1}{12}} \sqrt{n+1}} \le \frac{\sqrt{3} \cdot {(-2k + 1)}}{\sqrt{n+1}})$$

Applying Central Limit Theorem, we obtain this aproximation

$$P(|\sum\limits_{i=1}^n \hat{q_i} - (\hat{Q} - \hat{q_0})| \geq k) = 1-\Phi(\frac{\sqrt{3}\cdot {(2k - 1)}}{\sqrt{n+1}}) + \Phi(\frac{\sqrt{3} \cdot {(-2k + 1)}}{\sqrt{n+1}})$$

I think this is right

Last edited:

#### jcarne

##### New Member
I think I solved.

Take a look at the next table
$$\sum\limits_{i=0}^n \epsilon_i$$

$$\begin{tabular}{|c|c|c|c|} \hline \sum\limits_{i=0}^n \epsilon_i & \epsilon_Q & |\sum\limits_{i=0}^n \epsilon_i - \epsilon_Q| & [|\sum\limits_{i=0}^n \epsilon_i|] \\ \hline -2.37 & -0.37 & 2.0 & 2.0 \\ -4.46 & -0.46 & 4.0 & 4.0 \\ -2.64 & 0.36 & 3.0 & 3.0 \\ 1.06 & 0.06 & 1.0 & 1.0 \\ 1.53 & -0.47 & 2.0 & 2.0 \\ \hline \end{tabular}$$

Note that $$-\epsilon_Q$$ don't afect the final error. I only need to work with $$|\sum\limits_{i=0}^n \epsilon_i|$$ rounded to the nearest integer

Then $$P(|\sum\limits_{i=0}^n \epsilon_i - \epsilon_Q| \ge k) = P(|\sum\limits_{i=0}^n \epsilon_i| \ge k - \frac{1}{2}) = P(|S_{n+1}| \ge k - \frac{1}{2})$$

Where $$S_{n+1}$$ is a sum of $$n+1$$ iid random variables $$U(-\frac{1}{2},+\frac{1}{2})$$

$$P(|S_{n+1}| \ge k - \frac{1}{2}) = 1-P(|S_{n+1}| < k - \frac{1}{2})$$
$$= 1-P(-k+\frac{1}{2} < S_{n+1} < k - \frac{1}{2})$$
$$= 1-[P(S_{n+1} < k - \frac{1}{2}) - P(S_{n+1} \le -k + \frac{1}{2})]$$
$$= 1-P(S_{n+1} < k - \frac{1}{2}) + P(S_{n+1} \le -k + \frac{1}{2})$$
$$= 1-P(\frac{S_{n+1}}{\sigma \sqrt{n+1}} < \frac{k - \frac{1}{2}}{\sigma \sqrt{n+1}}) + P(\frac{S_{n+1}}{\sigma \sqrt{n+1}} \le \frac{-k + \frac{1}{2}}{\sigma \sqrt{n+1}})$$

$$\sigma^2=\frac{1}{12}$$

$$= 1-P(\frac{S_{n+1}}{\sqrt{12} \sqrt{n+1}} < \frac{k - \frac{1}{2}}{\sqrt{12} \sqrt{n+1}}) + P(\frac{S_{n+1}}{\sqrt{12} \sqrt{n+1}} \le \frac{-k + \frac{1}{2}}{\sqrt{12} \sqrt{n+1}})$$

$$= 1-\Phi(\frac{k - \frac{1}{2}}{\sqrt{12} \sqrt{n+1}}) + \Phi(\frac{-k + \frac{1}{2}}{\sqrt{12} \sqrt{n+1}})$$