2
$\begingroup$

Consider a bit (say $0$) duplicate $n$ times in some device:
$$[0]_n = (0,0,\dots, 0).$$ During some procedure, let $p$ be the probability for a bit to change by error. For the error correcting code to work, we need the bit $0$ to be still in a strict majority after the procedure. Here is the probability for that to happen: $$ P(n,p)= \sum_{k=0}^{\left\lceil n/2 - 1 \right\rceil} \binom{n}{k} p^k (1-p)^{n-k}.$$

Question: Is it possible to calculate* this sum in general?

*By calculate I mean something like the following examples:
$$\sum_{k=0}^n \binom{n}{k} = 2^n,$$ $$\sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k}=1,$$ $$\sum_{k=0}^n p^k = \frac{1-p^{n+1}}{1-p}.$$

$\endgroup$
4
  • $\begingroup$ @MorganRodgers: I mean a computation of the sum in general. It is a calculus question (motivated by error correcting code). So the calculus tag is required. I edited for clarification. Is it clearer? $\endgroup$
    – Sebastien Palcoux
    Commented Oct 18, 2020 at 12:21
  • 1
    $\begingroup$ The calculus tag is for "basic questions about limits, derivatives, integrals, and applications". So I would say that the calculus tag does not belong. $\endgroup$
    – xxxxxxxxx
    Commented Oct 18, 2020 at 16:37
  • $\begingroup$ @MorganRodgers Every sum can be interpreted as an integral (it is sometimes the only known way to calulate it). $\endgroup$
    – Sebastien Palcoux
    Commented Oct 19, 2020 at 3:14
  • 1
    $\begingroup$ Linking this with a related oldie so that future viewers of the simpler version will find their way here. $\endgroup$
    – Jyrki Lahtonen
    Commented Oct 22, 2020 at 4:42

1 Answer 1

Reset to default
3
$\begingroup$

The precise form of the cumulative distribution function of binomial distribution is a bit complicated, but handle-able. There are some bounds you can use.

Depending on your $p$ and $n$, you might be able to get away with Normal Approximation to the Binomial or De Moivre–Laplace theorem.

There are a number of other approximations on Wikipedia as well

$\endgroup$
2
  • 1
    $\begingroup$ According to the first link you wrote, the integral giving $P(n,p)$ seems to be evaluable. $\endgroup$
    – Sebastien Palcoux
    Commented Oct 19, 2020 at 4:27
  • 1
    $\begingroup$ For example, in term of the regularized incomplete beta function: $$ P(2n+1,p)=\frac{(2n+1)!}{(n!)^2} \int_0^{1-p}(t-t^2)^n dt = \cdots ? $$ $\endgroup$
    – Sebastien Palcoux
    Commented Oct 19, 2020 at 5:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .