+ Reply to Thread
Results 1 to 2 of 2

Thread: Probability and roundoff errors

  1. #1
    Points: 11, Level: 1
    Level completed: 21%, Points required for next Level: 39

    Posts
    2
    Thanks
    0
    Thanked 1 Time in 1 Post

    Probability and roundoff errors




    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 by jcarne; 03-23-2017 at 04:49 PM. Reason: We want Prob than an error is greater or equal than current error

  2. #2
    Points: 11, Level: 1
    Level completed: 21%, Points required for next Level: 39

    Posts
    2
    Thanks
    0
    Thanked 1 Time in 1 Post

    Re: Probability and roundoff errors


    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}})

  3. The Following User Says Thank You to jcarne For This Useful Post:

    logistiquecim (05-01-2017)

+ Reply to Thread

           




Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts






Advertise on Talk Stats