Show Inequality: Explain Why $g(k) \geq \frac{3^k}{2k+1}$ in Football Matches

[evinda]

Hello! (Wave)

Suppose that $k$ football matches are being done and a bet consists of the prediction of the result of each match, where the result can be 1 if the first group wins, 2 if the second group wins, or 0 if we have tie. So a bet is an element of $\{0,1,2 \}^k$. I want to show that $g(k) \geq \frac{3^k}{2k+1}$ where $g(k)$ is the minimum number of bets that is required so that it is sure that at least the second prize will be winned (there will be a bet with at most one wrong prediction).

Could you explain to me why the inequality holds?

 

[evinda]

In total there are $3^k$ possible results, and $2k+1$ results that could be off by one prediction.
But why do we divide $3^k$ by $2k+1$ in order to get a bound for $g(k)$ ?

 

[I like Serena]

Hey evinda! (Smile)

That doesn't look quite right. (Worried)
Suppose we pick $k=2$ and suppose the actual result is unknown.
Then we'll need a minimum of 3 bets to guarantee we're at most one off.
That is, however we place 2 bets, there is always a combination left that is 2 off - we need at least 3.
But your formula suggests that 2 bets would be sufficient.

Then again, if we look at it differently, and we place a random bet, the probability of being at most one off is the number of successful combinations $2k+1$ divided by the total number of combinations $3^k$:
$$P(\text{at most one off}) = \frac{2k+1}{3^k}$$
(Thinking)

 

[evinda]

Hey evinda! (Smile)

That doesn't look quite right. (Worried)
Suppose we pick $k=2$ and suppose the actual result is unknown.
Then we'll need a minimum of 3 bets to guarantee we're at most one off.
That is, however we place 2 bets, there is always a combination left that is 2 off - we need at least 3.
But your formula suggests that 2 bets would be sufficient.

Then, there will be one possible result for the first match, and 3 for the second one... Or 3 for the first match and 1 for the second match, right?

That's why we need 3 bets? (Thinking)

Then again, if we look at it differently, and we place a random bet, the probability of being at most one off is the number of successful combinations $2k+1$ divided by the total number of combinations $3^k$:
$$P(\text{at most one off}) = \frac{2k+1}{3^k}$$
(Thinking)

Can we use this probability to get a bound for $g(k)$? If so, how?

 

[I like Serena]

Then, there will be one possible result for the first match, and 3 for the second one... Or 3 for the first match and 1 for the second match, right?

That's why we need 3 bets? (Thinking)

Suppose we place the bets (0,1) and (1,2).
Then it's still possible for the actual outcome to be (2,0), meaning we don't achieve 2nd place.
We'll need a third bet to cover that.

Can we use this probability to get a bound for $g(k)$? If so, how?

If we keep placing random bets, we have a binomial distribution.
That means we can expect $np$ successes after placing $n$ random bets.
If we pick $n=\frac 1p$, we can expect $1$ success. (Thinking)

 

[evinda]

Using the sphere packing bound we get the desired inequality... (Thinking)

 

[I like Serena]

Using the sphere packing bound we get the desired inequality... (Thinking)

Erm... I'm not really familiar with the sphere packing bound. (Tmi)
Can you clarify? (Wondering)

 

[evinda]

Erm... I'm not really familiar with the sphere packing bound. (Tmi)
Can you clarify? (Wondering)

We consider a code that contains each possible sequences of the $k$ bets, with length $k$ ,$M$ codewords and covering radius $1$.

For each $ x \in \mathbb{F}_3^k $, the distance of any codeword ist $ c_i $ is at most $1$ (since the covering radius is 1).

So $ x$ belongs to a sphere of radius 1 , the $S_{\mathbb{F}_q}(c_i, 1) $.
So we have that $ \mathbb{F}_3^m \subset \bigcup_{i=1}^M S_{\mathbb{F}_q}(c_i,1)$ .

And then by looking at the cardinality of these sets, we get the desired bound.