Question

Counting heads. Given integersn and k, along with ${\mathit{p}}_{\mathbf{1}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{p}}_{\mathbf{n}}\mathbf{}\mathbf{}\mathbf{\in }\mathbf{}\left[0,1\right]$, you want to determine the probability of obtaining exactly heads when biased coins are tossed independently at random, where pi is the probability that the ith coin comes up heads. Give an $\mathbf{0}\left(n^2\right)$algorithm for this task. Assume you can multiply and add two numbers in $\left[0,1\right]$in $\mathbf{0}\left(1\right)$time.

Short answer

It is given in that we have ‘n ’ biased coins that are tossed independently, i.e., no mutual exclusion and tossing of one coin have no effect on result of other coin.

Also, $i^{th}$coin will produce head, with probability $p_i$.

Step-by-step solution

Subproblem

Let us consider that n-1 coins are already tossed together and n^th coin is toss separately.

Now let $P\left(1...n,k\right)$ is the probability of getting exactly ‘k’ heads when ‘n ’ coins are tossed.

Now applying our consideration, we will define a storing table $n*k$and fill the various probability.

Thus there are two ways of getting exactly ‘k ’ heads with ‘n ’ coins:

• If $n-1$coins have $k$heads and $n$^th coin show tail.
• If $n-1$coins have $k-1$heads and $n$^th coin is head.

According to the above two cases, we can define our subproblem as:

$\mathbf{P}\left(n,k\right)\mathbf{=}\mathbf{P}\left(n-1,k\right)\mathbf{*}\left(1-p\left[n\right]\right)\mathbf{+}\mathbf{P}\left(n-1,k-1\right)\mathbf{*}\mathbf{p}\left[n\right]$

Analysing the recursion equation

If we are tossing first $i$coins, where $j$is the number of heads,

And L(i,j) as total probability of getting head,

localid="1657267432115" $\mathbf{L}\left(i,j\right)\mathbf{=}\{\begin{array}{l}{P}_i*L\left(i-1,j-1\right)+\left(1-p_i\right)*L\left(i-1,j\right);\mathrm{for}j=0,1..i\\ 0;\mathrm{for}j\le 0\end{array}$

On solving this recursion equation, the time complexity will be $0\left(nk\right)$.

This is because our algorithm will run for ‘n’ coins but will stop if it gets k heads. So we will be using first loop for to toss each coin which would be ‘n’ and then second loop will check for head in the tossed coin.