Using binomial distribution to solve packet-switching and circuit-switching problem

Question

I have the following problem that I'm really stuck on. I attempted to do part b) and c) but I think I am very wrong since I didn't get the results required in part d). And part (a) I am also stuck on. Can someone please help me solve this problem?

In networks, we use physical cables/wires to send electromagnetic signals from point to point (the signals carry information). You can only fit so many signals on a wire at once, however. There are two approaches towards sharing a cable/wire to transmit data in a network: packet switching and circuit switching. In packet switching, users randomly send information over the wire whenever they feel like it whereas in circuit switching, users reserve a fixed percent of the resources on the wire (regardless of whether they're actively using it).

Assume each user uses 10% of the wire's resources when they send information on the wire and users are randomly active $p$% of the time. If more than 100% of the wire's resources are used at a point in time, we declare a "collision" and no work gets done. Define the utilization of the wire as the average percent of its resources being used over time (utilization during a collision is 0).

a) in the circuit switching scenario, how many users can share this wire as a function of $p$? What is the utilization?

Max users = 10 Utilization is p%

b) In the packet-switching scenario, how many users can share this wire, assuming we want to keep the probability of collision less than 0.1%? What is the utilization? (Write an equation that would let you solve for the number of users/utilization given p

Max users = $$\sum_{k=0}^{10} {n\choose k} p^k(1-p)^{n-k} \geq 0.999$$

Utilization = $$\sum_{k=0}^{10} {n\choose k} \frac{k}{10} p^k(1-p)^{n-k} $$

c) Solve for the previous two answers with p=50 percent and p=5 percent

$p=0.5$:

$$\sum_{k=0}^{10} {11 \choose k} (0.5)^k(1-0.5)^{11-k} >0.999$$

$$\sum_{k=0}^{10} {12 \choose k} (0.5)^k(1-0.5)^{12-k} <0.999$$

so max users is 11.

utilization:

$$\sum_{k=0}^{10} {11\choose k} \frac{k}{10} p^k(1-p)^{11-k} \approx 0.55$$

$p=0.05$

$$\sum_{k=0}^{10} {73 \choose k} (0.5)^k(1-0.5)^{73-k} >0.999$$

$$\sum_{k=0}^{10} {74 \choose k} (0.5)^k(1-0.5)^{74-k} <0.999$$

so max users is 73

Utilization is:

$$\sum_{k=0}^{10} {73\choose k} \frac{k}{10} p^k(1-p)^{73-k} \approx 0.36$$

d) You should have found that for p=5 percent, the packet-switched network can support more users than for p=50 percent. Why, then, does the expected utilization decrease when p=5 percent?

I found that p=5 supports more users than p=50 but the expected utilization doesnt decrease.

Answer 1

If $X$ is the number of users that are active then $X \sim \text{Bin}(n,p)$. So in part (b), for a fixed $p$ we want to find the largest $n$ that allows us to avoid collision with probability at least $1-\alpha$. Collision here means that $X \ge 10$, so we want to choose the largest $n$ that satisfies: $$ P(X \ge 10) \le \alpha \iff \sum_{x=10}^n {n \choose x} p^x(1-p)^{n-x} \le \alpha. $$

Using R (see code below) or any other numerical solver, we can compute the sum on the left hand side for a range of $n$ values and pick the largest $n$ that satisfies the constraint. For $p=0.5$, we get that $n_{0.5} = 12$, and for $p=0.05$, we get that $n_{0.05}=98$. Now, the utility as you define it is defined as $np$, so

$$ u(0.5) = n_{0.5} \times 0.5 = 6 $$ and

$$ u(0.05) = n_{0.05} \times 0.05 = 98 \times 0.05 = 4.9 $$

As for part (a), I feel like the answer must just be 10 users, who each reserve 10% of the wire, there is zero chance of collision here and the wire is at maximum utility under the constraints of the circuit switching scheme. In other words, the number of users that can share the wire is a constant not depending on $p$.

alpha=0.01           # tolerance level

# assume p = 0.5 first, we will generate the probabilities P(Bin(n,0.5) < 10) for n ranging from 10 to 100, and then check which is the largest 'n' that gives a probability smaller than or equal to alpha.
ns = seq(10, 100)
probs = c()
for (i in 1:length(ns)) {
  p = pbinom(10, size=ns[i], prob=0.5, lower.tail=FALSE)
  probs = c(probs, p)
}

# probs contains P(bin(n, 0.5) < 10) for n varying from 10 to 100
# now,find index of largest n such that the probability 
# P(bin(n, 0.5) < 10) <= alpha

idx = max(which(probs<= alpha))
N = ns[idx]



# repeat for p = 0.05
ns = seq(10, 100)
probs = c()
for (i in 1:length(ns)) {
  p = pbinom(10, size=ns[i], prob=0.05, lower.tail=FALSE)
  probs = c(probs, p)
}

# probs contains P(bin(n, 0.05) < 10) for n varying from 10 to 100
# now,find index of largest n such that the probability 
# P(bin(n, 0.05) < 10) <= alpha

idx = max(which(probs<= alpha))
N = ns[idx]

edit

As noted in the comments, I misread the original question and took $\alpha=0.01$, when it should be $\alpha=0.001$. Changing the first line of the code, we get that $n_{0.5}=11$ and $n_{0.05}= 73$. OP updated his question to include the attempt in my solution and changed their initial definition of utilization being $np$.