# Probability that the row in the table contain only one bit one?

I am an electrical engineer that is currently working with an $$m \times n$$ matrix that only contains bit 0 and bit 1 in its cell. Assuming that bit 0 and bit 1 can appear in a cell with probability $$p$$ and $$q$$ respectively, where $$p+q=1$$. Also, assume that the probability of 1 and 0 in each cell is independent of any other cell.

1/ How can I evaluate the probability that a row contain only one bit 1 ?

For example, row 1, row 2, and final row contain only one bit 1

2/ On average, how many row will contain only one bit 1 ?

In my application, there is a row dropping action that can be describe as follows:

Starting at the row that contain only bit one (row 5) and begin to look up and look down (blue arrow), if we see bit 1 above (same column) or bit 1 right below it (same column) then we will initiate a drop row action for the corresponding row. Note that I have marked the bit 1 above and bit 1 below in a blue rectangular cell. So, in total 4 rows will be dropped. That is row 1, 2,7 and 8.

3/ On average, how many row will be dropped ?

I have a guts feeling that this may have something to do with the binomial distribution or geometric distribution but cannot get me head around it. Please help me with this ?

Edit for clarity:

1/ For question 3, it is possible that there are many rows that contains one bit 1.

2/ For question 3, row that contain one bit 1 will never be dropped !

Thank you for your enthusiasm !

• In the third question, is it possible that more than one row contains only a single "1" entry? In this case, how the "row dropping action" works? Thank you! I think that we have to check for the first row which contains only a single 1 in the first spot and do the action; then we have to check for the first row which contains a single 1 in the second spot and do the action, and so on. Correct me if I'm wrong. Commented Nov 15, 2023 at 13:14
• Question 3 requires a little more clarity. Can rows containing 1 bit also be dropped rows? If so, will dropped 1 bit rows cause other rows to be dropped? Commented Nov 15, 2023 at 13:22
• @LucaOnnis, it is possible that more than one row contains only a single "1" entry. Note that, we have to do the dropping action for every row contains only a single "1" entry. Commented Nov 15, 2023 at 13:22
• @MetehanTuran Can rows containing one bit 1 also be dropped rows? No the row that contain one bit 1 is not considered as drop row Commented Nov 15, 2023 at 13:28
• @TuongNguyenMinh So if there are two rows $(0,0,1)$ then none of them will be dropped? Ok so I have misunderstand the third question, I'll post it later. Commented Nov 15, 2023 at 13:50

First question

Let $$A\in\mathcal{M}_{m\times n}$$ be a matrix with $$0,1$$ entries. Then we define the random variable: $$R_i$$ = number of 1 in the $$i$$-th row. It is straigthforward to note that $$R_i\sim B(n,q)$$ for all $$i\in\{1,\dots,m\}$$ (here $$B(n,q)$$ is a binomial distribution of parameters $$n$$,$$q$$).

This implies that $$P(R_i = 1) = \binom{n}{1}qp^{n-1}$$ which solves the first question.

Second question

We define the random variable $$R'$$ which counts the number of rows with only one entry equal to 1. Then $$R'\sim B(m,P(R_i = 1)) \sim B(m,\binom{n}{1}q(1-p)^{n-1})$$ which has expcted value the product of its parameters:

$$\mathbb{E}(R') = m\binom{n}{1}qp^{n-1}$$

Third question

We first find the first row such that it contains only a single 1 and it is in the first spot. Define $$W_1$$ the number of rows with these conditions. The probability for a row that there is a single and only 1 in the first spot is $$qp^{n-1}$$, then $$W_1\sim B(m,qp^{n-1})$$. We select one among them (not necessarely the first, it's really the same) and we do the drop action. We eliminate a number $$E_1$$ of rows, which is the number of all the $$m-W_1$$ rows with the first entry equal to 1. The probability for a row to have the first entry equal to 1 is exactly $$q$$, so $$E_1\sim B(m-W_1,q)$$.

We do the same process for the rows with the property that the second entry is 1, and that there is only a single 1 in it. $$W_2\sim B(m-W_1-E_1,qp^{n-1})$$ and we eliminate $$E_2\sim B(m-W_2-W_1-E_1,q)$$.

In general: $$W_k\sim B(m-\sum_{i = 1}^{k-1}(E_i+W_i),qp^{n-1})$$ and $$E_k\sim B(m-W_k-\sum_{i = 1}^{k-1}(E_i+W_i),q)$$

Now the idea is to compute $$\mathbb{E}(\sum_{k = 1}^{n}E_k) = \sum_{k = 1}^{n}\mathbb{E}(E_k)$$, where $$n$$ is the number of columns of the matrix $$A$$.

I'll finish to write later

• $m\times n$=$m\times n$ Commented Nov 15, 2023 at 13:26
• @r.e.s. Thank you! LaTeX advices are always appreciated. Commented Nov 15, 2023 at 13:55
• As soon you remove these $W_1$ rows, the rest of the rows is not distributed the same (there are essentially conditioned on not having a single 1 at the first position), and the probability to have a 1 at the first position becomes smaller than $q$. Commented Nov 16, 2023 at 8:04
• q is the probability in the first step to have a 1 in the first position; in the second step to have a 1 in the second position, etc. Since the entries of the matrix $A$ are indipendents, the probability remains equal to $q$! Maybe I have to specify these details.. that each step $q$ is the probability to have a 1 in the position $k$ (in the $k$-th step). Commented Nov 16, 2023 at 10:09
• The error becomes obvious for only n=1 column: No row is ever going to be dropped, but your answer gives E_1 ~ B(m-W_1,q), which can be bigger than 0. The rows, which are not in W_1 are the rows with zeroes, and have probability 0 to have a one. Independence breaks the moment you ignore W_1. Commented Nov 17, 2023 at 18:05

#### Question 1 & 2

(Kept short, as there is already an excellent answer.) The amount $$R$$ of ones in a row is binomially $$B(n,q)$$-distributed, so the probability for a one-1-row is $$\binom n1qp^{n-1} = nqp^{n-1}$$. Since there are $$m$$ rows, the expected amount is $$m$$ times this probability, $$nmqp^{n-1}$$.

#### Question 3

The trick for calculating the expected amount of elements that do something is usually just to calculate the probability of an element doing this and multiply it with the amount of elements.

But how big is the probability for a row, say the first, to be dropped? As I understand the question, a row is dropped if

• It has more than 1 one. (rows with only one 1 never get dropped)
• and it has a 1 in a column where a 1-one-row also has one.

Both of these events are strongly affected by the amount of 1 the row has, so let's condition on this amount being $$k$$. If a row has $$k$$ ones and $$k≥2$$, then it gets dropped when some of the $$m-1$$ other rows has only one 1, and this 1 is in some of the $$k$$ rows.

The probability of having only one 1 at a fixed place is $$qp^{n-1}$$ and so the probability of having it on one of $$k$$ places is $$kqp^{n-1}$$. The probability of this not happening is thus $$1-kqp^{n-1}.$$ The rows are independent, so the probability of there being no row that drops our row is $$\bigl(1-kqp^{n-1}\bigr)^{m-1}$$ and the probability that our row is dropped is thus 1 minus the term above: $$P(\text{Row 1 gets dropped}\mid \text{Row 1 has k ones}) = 1-\bigl(1-kqp^{n-1}\bigr)^{m-1}$$ This k, amount of ones in our first row is, again, $$B(n,q)$$-distributed, so by the law of total probability \begin{align} P(\text{Row 1 gets dropped}) &= \sum_{k=2}^n P(\text{Row 1 gets dropped}\mid \text{Row 1 has k ones})P(\text{Row 1 has k ones}) \\ &= \sum_{k=2}^n \bigl(1-\bigl(1-kqp^{n-1}\bigr)^{m-1}\bigr)\binom nk q^kp^{n-k}. \end{align} The expected amount of dropped rows is then $$mP(\text{Row 1 gets dropped}) = m\sum_{k=2}^n \bigl(1-\bigl(1-kqp^{n-1}\bigr)^{m-1}\bigr)\binom nk q^kp^{n-k}.$$ I see no obvious way to simplify this sum.

• Test case: $m=n=2,$ and $p=q=1/2$. In this case, one row gets dropped in each of these four outcomes: $\begin{pmatrix}1&0\\1&1\end{pmatrix}$,$\begin{pmatrix}0&1\\1&1\end{pmatrix}$,$\begin{pmatrix}1&1\\1&0\end{pmatrix}$,$\begin{pmatrix}1&1\\0&1\end{pmatrix}$; otherwise no rows get dropped. Since there are $2^4=16$ equally-likely outcomes, the expectation of the number of dropped rows is therefore $1\cdot (4/16)+0\cdot(12/16)=1/4$; but your formula gives $1/2$. Commented Nov 16, 2023 at 14:23
• Aha! It looks like you made a typo where you first wrote $kq^{n-1}$, as that should be $k\,q\,p^{n-1}$, making $P(\text{Row 1 gets dropped}\mid \text{Row 1 has$k$ones}) = 1-(1-k\,q\,p^{n-1})^{m-1}.$ (BTW, the revised answer then agrees with simulations that I've done.) Commented Nov 16, 2023 at 16:52
• @TuongNguyenMinh Per your request, I've posted my code together together with what I believe is the correctly revised answer to question #3. Commented Nov 17, 2023 at 11:13
• Thanks @r.e.s., this is indeed the typo, which then got carried over into the subsequent formulae Commented Nov 17, 2023 at 17:53
• @TuongNguyenMinh I believe that formula is correct if a "one-1 row" gets dropped only when there is at least one copy of it elsewhere in the matrix; i.e., such a row does not cause itself to be dropped. (The rules as-stated seem a bit unclear about this.) Commented Dec 31, 2023 at 7:01

For the first question, all possible states are:

100...0
010...0
.......
000...1

So $${n}\choose{1}q.p^{n-1}$$ will represent probability that a row contain only one bit $$1$$. Because we expect $$n-1$$ bit0's and $$1$$ bit1. And this can happen in $${n}\choose{1}$$ different ways. See Binomial Distribution Wikipage for more information.

For the second question, you actually want expected value of containing one bit $$1$$ with respect to all rows. The probability of containing 1 bit is equal for all rows. This is called uniform distribution. Call this random variable as $$R$$. Simply multiplying by $$m$$ gives us the average number of rows that contain only one bit $$1$$.

$$E[R]=$$ $$m{n}\choose{1}$$ $$q.p^{n-1}$$

Per the OP's request, below is Python code that I used to simulate question #3, the results of which agree with the (revised) answer of @Dodezw, i.e.,$$\mathbb{E}(N)= m\sum_{k=2}^n \bigl(1-\bigl(1-k\,q\,p^{n-1}\bigr)^{m-1}\bigr)\binom nk\,q^kp^{n-k}.$$

Here are contour plots of the above function, for $$q=1/2$$ and $$q=1/3$$, for $$2\le m\le 100$$ and $$2\le n\le 20$$. Each curve interpolates $$(m,n)$$-values for which $$\mathbb{E}(N)$$ approximates the labelled constant:

Numerical observations:

1. For all $$q\in(0,1)$$ and all $$n\ge 1$$, $$f(m,n,q):=\mathbb{E}(N)$$ is a strictly increasing function of $$m$$.
2. For all $$q\in(0,1)$$ and all $$m\ge 2$$, as $$n$$ increases, $$f(m,n,q)$$ first increases to a maximum, then decreases toward $$0$$: i.e., there exists $$n^*$$, such that $$f(m,n^*,q)=\max_{n}f(m,n,q).\$$ (NB: $$n^*(m,q)$$ is the dotted line shown in each plot above, forming a "ridge line" along the top of the "hill" we're "viewing from above" in each of these plots.)
3. For $$q=1/2$$ and for $$m$$ up to $$4$$, Wolfram Alpha symbolically computes that $$\mathbb{E}(N)= m\,(m+1)\,n\,2^{-(n+1)}(1+\mathcal{O}(n\,2^{-(n+1)}))$$ which suggests the approximate formula $$f(m,n,1/2) \approx g(m,n):=m\,(m+1)\,n\,2^{-(n+1)}$$ for some range of $$(m,n)$$-values. The following plot shows error contours, such that for all points $$(m,n)$$ above a given labelled contour, $$|g(m,n)-f(m,n,1/2)|$$ is less than the label-value:

Python code for simulating question #3:

import math
import random

def get_M(m, n, q):
"""returns m x n matrix M with elements i.i.d Bernoulli(q), q=P(bit=1)"""
M = []
for i in range(m):
row = [(1 if random.random()<q else 0) for j in range(n)]
M += [row]
return M

def trial(m, n, q):
"""return the number of dropped rows in one sample of M(m, n, q)"""
M = get_M(m, n, q)
indrows = []   # accumulates "indicator" rows (i.e. which rows have exactly one 1)
indcols = []   # accumulates "indicator" cols (i.e. which cols have the 1 in the indicator rows)
for i in range(m):       # for all rows ...
if M[i].count(1)==1:     # if there's exactly one 1 in the row ...
indrows += [i]                # accum. that row#
indcols += [M[i].index(1)]    # accum. the index of the 1 in that row
count = 0
for i in range(m):           # for all rows ...
if (i not in indrows):       # if the row does not contain exactly one 1 ...
for j in range(n):       # then check each element in that row
if M[i][j]==1 and j in indcols:   # if element==1 in an "indicator" column
count += 1                    # then that row counts as dropped
break            # go on to the next row
return count

def EN(m, n, q):  #q = P(bit=1)
"""return E(N) computed from the posted formula"""
p = 1 - q
return m*sum([(1-(1-k*q*p**(n-1))**(m-1))*math.comb(n,k)*q**k*p**(n-k) for k in range(2, n+1)])

def est_EN(nsamp, m, n, q):
"""return (mean, sd) such that mean +- 3*sd is an approx 99% CI for E(N), using nsamp simulated random samples
NB: this is generic code implementing a 'running' mean & variance algorithm"""
mean = ssd = 0
for i in range(1, nsamp+1):
z = trial(m, n, q)
dev = z - mean
mean += dev/i
ssd += dev*(z - mean)
sd = math.sqrt(ssd/(nsamp-1)/nsamp)
return mean, sd

Example:

m, n, q = 3, 2, .5
print(f"{(m, n, q)=}, {nsamp=}")

formula_EN = EN(m, n, q)
print(f"  {formula_EN = :.6f}")

nsamp = 10**8
(mean, sd) = est_EN(nsamp, m, n, q)
print(f"simulated_EN = {mean:.6f} +- {3*sd:.6f}")

Output for this example:

(m, n, q)=(3, 2, 0.5), nsamp=100000000
formula_EN = 0.562500
simulated_EN = 0.562553 +- 0.000198

Wall time: 4min 52s
• Thank you but I do not know the implication of this $\mathbb{E}(N)= n\,2^{-n}\,\binom{m}{2}(1+\mathcal{O}(n\,2^{-(n+1)}))$, could you elaborate more ? Do we have any weird result for the case of small $m$ or small $n$ or big $m$ or big$n$ ? Commented Nov 18, 2023 at 4:09
• I had to weaken my assertion about that behavior seeming to hold for all $m$ -- numerically the behavior seems a bit different for large enough $m$. (I would love to study this problem more, but unfortunately have to put it aside for the time being.) Commented Nov 18, 2023 at 6:11
• Thank you ! That is so very nice of you Commented Nov 18, 2023 at 8:03