0
$\begingroup$

I have packet streams $1...k$ and, streams with Prob(err) $p1...pk$. The $p$'s are consts $>0$. I'd like to maximize the probability all make it simultaneously while I'm allowing at most $N$ packets to pass through, hence, every stream should get some portion of $N$. i.e.

max $f=(1-p_1^{n_1})(1-p_2^{n_2})...(1-p_2^{n_2})$ or max $\prod_{i=1}^k (1-p_i^{n_i})$

s.t. $\sum_{i=1}^k n_i=N$

The problem is to find here the optimal set of portions, or $n$'s.

Now, to simplify, I remove the requirement from $n$'s to be integers, now $n \in R+$

...

I have tried to solve $max \ log(f)$ which reduces this problem to $\sum_{i=1}^k ln(1-p_i^{n_i})$

Now, I've tried to do Lagrangian and by solving it for the case of only $n1,n2$ I get

$n1=\frac{1}{lnp_1}ln\bigg(\frac{\lambda}{\lambda+lnp_1}\bigg)$ and a similar form for $n_2$. My problem is that later, for $\lambda$, I get a closed form expression like,

$ lnp_2ln\bigg(\frac{\lambda}{\lambda+lnp_1}\bigg)+lnp_1ln\bigg(\frac{\lambda}{\lambda+lnp_2}\bigg) = Nlnp_1lnp_2$

My solution was to convert to,

$ lnp_2ln\bigg(1+\frac{lnp_1}{\lambda}\bigg)+lnp_1ln\bigg(1+\frac{lnp_2}{\lambda}\bigg) = -Nlnp_1lnp_2$

and use Taylor series $ln(1+x)=x-x^2/2+...$. I am not getting sensible results there if to take the two first elements, i.e. $ln(1+x)\approx x-x^2/2$, taking better approximation converts to an intimidating polynomial :)...

Maybe I've made a mistake somewhere earlier?

$\endgroup$
  • $\begingroup$ You may want to study Shannon's Entropy function H(p) = -p*ln(p) en.wikipedia.org/wiki/Entropy_(information_theory) $\endgroup$ – Pieter21 Mar 18 '15 at 11:03
  • $\begingroup$ What reason do you have to believe an analytic solution exists? It might, of course, but this is probably not difficult to solve numerically. $\endgroup$ – Michael Grant Mar 19 '15 at 13:35
  • $\begingroup$ @Pieter21, here I talk about packets not bits and its about finding the right combination of n's for my scheduling algorithm. Moreover, these packets are assumed to be repetitions of real data as my scheduling policy deals with retransmission solely. Cheers $\endgroup$ – Yakir Matusovsky Mar 19 '15 at 19:46
  • $\begingroup$ I have been hoping that I can find an analytical one, @MichaelGrant, since I am trying to use that allocation method in my simulation for comparison of allocation policies, hence, I'd expect the formula to be computationally efficient... $\endgroup$ – Yakir Matusovsky Mar 19 '15 at 19:48
  • $\begingroup$ Well, you've already resorted to Taylor approximations, so my suggestion is to embrace the numerical solution with gusto. :-) $\endgroup$ – Michael Grant Mar 19 '15 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.