Probability and roundoff errors

#1
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:
#2
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}})\)