Putnam 2014 A4

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

w

2 users

TOPICS

No tags match your search

M

No tags match your search

M

Putnam 2014 A4

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kent Merryfield

18574 posts

Kent Merryfield

#1 h Dec 7, 2014, 11:57 PM • 5 Y

Y by Davi-8191, adityaguharoy, ImSh95, Adventure10, Mango247

Suppose $X$ is a random variable that takes on only nonnegative integer values, with $E[X]=1,$ $E[X^2]=2,$ and $E[X^3]=5.$ (Here $E[Y]$ denotes the expectation of the random variable $Y.$ ) Determine the smallest possible value of the probability of the event $X=0.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kent Merryfield

18574 posts

Kent Merryfield

#2 h Dec 7, 2014, 11:58 PM • 3 Y

Y by ImSh95, Adventure10, Mango247

OK, I know the answer, and I know the configuration that gives that answer, but I don't have a proof that I particularly like. The smallest possible value of $P(X=0)=\frac13.$ The configuration that gives that also has $P(X=1)=\frac12,$ $P(X=3)=\frac16,$ and $P(X=x)=0$ for all other values of $x.$

Here's one take on it. Let $p_k=P(X=k).$ Then let $q_k=kp_k.$ Since $\sum_{k=0}^{\infty}q_k=\sum_{k=1}^{\infty}q_k=1,$ we can take $q_k$ to be a set of probabilities -- say, $P(Y_k)=q_k$ . Then our problem becomes this: for $Y$ a random variable that takes only positive integer values, maximize $E\left(\frac1Y\right)$ subject to the constraints $E(Y)=2$ and $\mathrm{Var}(Y)=1.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2453 posts

#3 h Dec 8, 2014, 12:06 AM • 4 Y

Y by rafayaashary1, ImSh95, Adventure10, Mango247

A sketch:

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

87 posts

#4 h Dec 8, 2014, 1:24 AM • 3 Y

Y by ImSh95, Adventure10, and 1 other user

Let $p_0$ , $p_1$ , $p_2$ , $p_{\geq 3}$ be the probabilities that $X$ is 0, 1, 2, or at least 3. The problem becomes linear programming.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4210 posts

#5 h Dec 8, 2014, 1:32 AM • 4 Y

Y by stephcurryforthetrey, ImSh95, Adventure10, Mango247

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

652 posts

#6 h Dec 8, 2014, 3:22 AM • 3 Y

Y by ImSh95, Adventure10, Mango247

basically equivalent to above solutions

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2172 posts

#7 h Dec 8, 2014, 7:42 AM • 3 Y

Y by ImSh95, Adventure10, Mango247

Shoot, I did not read this problem carefully and thought that X was a random positive real variable. That made the problem significantly harder.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

109 posts

#8 h Dec 8, 2014, 5:06 PM • 4 Y

Y by fungarwai, Davi-8191, ImSh95, Adventure10

Let the probability that $X=n$ be $a_n$ . Let $f$ be the generating function of $a_n$ Then,

$f(x)=a_0 +a_1x +a_2x^2+ \cdots$

Then:
$f'(x)\& =a_1 +2a_2x+ 3a_3x^2 +\cdots$
$(x(f'(x))'= f'(x) +xf''(x) \&= a_1 +4a_2x+ 9a_3x^2 + \cdots$
$(x( f'(x) +xf''(x)))' = f'(x) +3xf''(x) + x^2f'''(x)\&= a_1 +8a_2x+ 27a_3x^2 + \cdots$

Substituting $1$ into each of these,

$f'(1)\& =a_1 +2a_2+ 3a_3 +\cdots = E[X] =1$
$f'(1) +f''(1) \&= a_1 +4a_2+ 9a_3 + \cdots =E[X^2]=2$
$f'(1) +3f''(1) + f'''(1)\&= a_1 +8a_2+ 27a_3 + \cdots = E[X^3]= 5$

Therefore, $f'(1)= f''(1)=f'''(1)= 1$ .

Now consider the Taylor expansion of $f$ about $1$ :

$f(x)= f(1) + \frac{f'(1)}{1!} (x-1)+\frac{f''(1)}{2!} (x-1)^2+\frac{f'''(1)}{3!} (x-1)^3+ \cdots$

$f(1)=1$ , because the sum of the probabilities is $1$ . Thus, substituting $x=0$ ,

$\boxed{ a_0 = f(0) = 1 - 1+ \frac{1}{2}- \frac{1}{6} + \cdots \geq \frac{1}{3}}$

In fact, the Taylor expansion gives us such an equality sequence. We must have $f^{(n)}(1)=0$ for $n \geq 4$ , so then

$f(x)= 1 + (x-1)+\frac{1}{2}(x-1)^2+\frac{1}{6} (x-1)^3 = \frac{1}{3} + \frac{x}{2} + \frac{x^3}{6}$

Therefore, the minimum value of $a_0$ is $\frac{1}{3}$ , which occurs when $a_0= \frac{1}{3}, a_1 = \frac{1}{2}, a_2 =0, a_3 = \frac{1}{6}$ and $a_n =0$ for $n \geq 4$ . These conditions fit the requirements of the problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1449 posts

#9 h Dec 8, 2014, 5:37 PM • 2 Y

Y by ImSh95, Adventure10

Wow the N-1 C 3 thing is way cleaner than what I did. My solution was to write down all the max. values of P(X=i) separately, which gave about one entire page of inequalities, from which the ones I needed popped out. Now I don't have a lot of confidence that the grader is going to follow it seeing that a much better solution exists.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

611 posts

#10 h Dec 8, 2014, 5:39 PM • 4 Y

Y by Davi-8191, ImSh95, Adventure10, Mango247

I like the idea of using generating funcions here very much. It seems very natural. However, I see problems in the above solution: The Taylor-expansion of $f$ about $1$ may not exist (e.g. what if the expection of $X^4$ ist infinite). Why do we have $1-1 + \frac 1 2 - \frac 1 6 + ... \ge \frac 1 3$ ? (Since we have both negative and positive terms on the left hand side, this would need some justification.)

Once you have $f(1) = f'(1) = f''(1) = f'''(1) = 1$ a simpler and maybe better way to continue: Use $f'''(x) \le 1$ (since $f'''(x)$ is increasing) on $[0,1]$ , then keep integrating this inequality over the interval $[x,1]$ for $x \in [0,1]$ to get first $1 - f''(x) \le 1-x$ , then $1-f'(x) \ge \frac 1 2 - \frac 1 2 x^2$ , and then $1-f(x) \le \frac 2 3 - \frac 1 2 x - \frac 1 6 x^3$ .

For $x = 0$ we get $f(0) \ge \frac 1 3$ and we also get that equality is reached for $f(x) = \frac 1 3 + \frac 1 2 x + \frac 1 6 x^3$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

109 posts

#11 h Dec 8, 2014, 10:50 PM • 3 Y

Y by ImSh95, Adventure10, Mango247

Thanks, I too am not completely sure about it.

I feel like the Taylor expansion about $1$ should exist, because the generating function must exist. Could we not then rearrange terms so that it becomes a polynomial in $(x-1)$ ? (I'm not so sure about that myself).

Also, the $\frac{1}{3}$ will be a minimum, because the Taylor expansion has alternating positive and negative terms which are decreasing in absolute value. Thus, as the sum continues, it won't go lower than $\frac{1}{3}$ .

If that isn't valid, then I suppose your way is a better way to go

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

77 posts

#12 h Dec 9, 2014, 12:41 AM • 3 Y

Y by ImSh95, Adventure10, Mango247

Mewto55555 wrote:

That's pretty much exactly what I did...during the lunch break. *Goes and cries in a corner.*

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

226 posts

#13 h Apr 6, 2015, 7:06 PM • 3 Y

Y by ImSh95, Adventure10, Mango247

andersonw wrote:

So $\frac{11}{6}\sum_{n=0}^\infty np_n -\sum_{n=0}^\infty n^2p_n + \frac{1}{6}\sum_{n=0}^\infty n^3p_n = \frac{11}{6}-2+\frac{5}{6}=\frac{2}{3}$ .

Hi guys, I'm in the midst of preparation for the Putnam exam right now, and I'm pretty new to expected value problems like these. I was wondering, in Andersonw's solution, how he was allowed to assert what he said above to find the minimum value for $P(x = 0)$ . Forgive me if this may sound trivial, but how did he find the numbers $\frac{11}{6}, 1$ , and $\frac{1}{6}$ to multiply the sums to express $E[X], E[X^2]$ and $E[X]^3$ , respectively? Why can't he multiply those individual sums by other numbers? For example, why does $\sum_{n=0}^\infty np_n -2\sum_{n=0}^\infty n^2p_n + \frac{4}{5}\sum_{n=0}^\infty n^3p_n = 1 - 2 + 4 = 1$ not lead to this minimum? Thanks.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

21 posts

#14 h Apr 6, 2015, 9:29 PM • 1 Y

Y by Adventure10

He used the fact that $\frac{11n}{6}-n^2+\frac{n^3}{6}=1$ for $n=1,2,3$ and is equal to $0$ for $n=0$ . Thus, $\displaystyle\sum_{n=0}^\infty \left(\frac{11n}{6}-n^2+\frac{n^3}{6}\right)p_n=p_1+p_2+p_3+\displaystyle\sum_{n=4}^\infty p_n\left(\frac{11n}{6}-n^2+\frac{n^3}{6}\right)$ from where the fact that $\frac{11n}{6}-n^2+\frac{n^3}{6}>1$ for all other $n\geq 4$ leads to the conclusion that $p_1+p_2+p_3+\displaystyle\sum_{n=0}^\infty p_n\left(\frac{11n}{6}-n^2+\frac{n^3}{6}\right)\geq p_1+p_2+p_3+\displaystyle\sum_{n=4}^\infty p_n=1-p_0$
But since the LHS is equal to $\frac{2}{3}$ , it follows that $p_0\geq\frac{1}{3}$ .

I think $1,-2,\frac{4}{5}$ would not work since $n-2n^2+\frac{4}{5}n^3<1$ for $n=1,2$ . So, you can't say the sum is bigger than $\displaystyle\sum_{n=1}^\infty p_n$ .

I think the coefficients are found by looking for $a,b,c$ such that
$\begin{align*} a(1)+b(1^2)+c(1^3)&=1\\ a(2)+b(2^2)+c(2^3)&=1\\ a(3)+b(3^2)+c(3^3)&=1\\ \end{align*}$
Solving this system gives only one solution: the coefficients $\frac{11}{6},-1,\frac{1}{6}$ . You need this so that you can compare some sum $\displaystyle\sum_{n=0}^\infty (an+bn^2+cn^3)p_n$ to $\displaystyle\sum_{n=0}^\infty p_n=1$ , in other words to isolate $p_0$ .

This post has been edited 1 time. Last edited by JosephSuk, Apr 7, 2015, 12:18 AM
Reason: Mistake in notation

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

226 posts

#15 h Apr 6, 2015, 10:28 PM • 4 Y

Y by adityaguharoy, ImSh95, Adventure10, Mango247

Oh, okay. So it's now clear to me how you derive the minimum once you actually have the polynomial $(an+bn^2+cn^3)$ . I was wondering about the motivation and thought process behind forming that polynomial, but I'm guessing that any polynomial that allows you to effectively compare to $\displaystyle\sum_{n=0}^\infty p_n=1$ and isolate $p_0$ works to find the minimum. Am I getting the right idea?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1886 posts

Potla

#16 h May 24, 2015, 8:58 PM • 6 Y

Y by Justanotherone, adityaguharoy, OlympusHero, starchan, ImSh95, Adventure10

Cauchy-Schwarz ^^

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

759 posts

#17 h Jun 19, 2016, 8:05 AM • 6 Y

Y by Mathcat1234, ImSh95, kiyoras_2001, Ru83n05, Adventure10, Mango247

Simple approach:

We are basically given three equations
$\begin{align} p_1 + 2p_2 + 3p_3 + \cdots &= 1 \\ p_1 + 4p_2 + 9p_3 + \cdots &= 2 \\ p_1 + 8p_2 + 27p_3 + \cdots &= 5 \end{align}$ and we seek to maximize $p_1 + p_2 + p_3 + \cdots$ . We can take a linear combination to have the first three match up, by doing $(3) \cdot 1 - (2) \cdot 6 + (1) \cdot 11$ . This will yield
$6p_1 + 6p_2 + 6p_3 + 12p_4 + 30p_5 + \cdots = 4$ The coefficient of $p_k$ can easily be shown to be equal to $k^3 - 6k^2 + 11k$ which is greater than $6$ for $k > 3$ . Thus,
$p_1 + p_2 + p_3 + p_4 + \cdots \le \frac{2}{3}$ and so the answer is clearly $\frac{1}{3}$ . The equality case can easily be set up from these inequalities by letting $p_4 = p_5 = \cdots = 0$ and then solving the resulting 3x3 matrix.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

226 posts

#18 h Dec 29, 2017, 1:51 AM • 3 Y

Y by ImSh95, Adventure10, Mango247

Ah, and two and a half years later, I finally have this problem fully within my grasp. My write-up is very elementary, but it has the main ideas already mentioned in this thread. Hopefully it isn't too dirty.

Write out the three equations for our expected values to get $\sum_{i=0}^\infty ip_i = 1, \sum_{i=0}^\infty i^2p_i = 2, \sum_{i=0}^\infty i^3p_i = 5.$ Since $\sum_{i=0}^\infty p_i = 1$ , we have a system of four equations with infinite variables. All these sums are convergent, so we shouldn't be having any issues adding or subtracting them. Thus, all but four of the $p$ 's are free variables, so let's let $p_0, p_1, p_2, p_3$ depend on all the other $p$ 's. Obtain two new equations by subtracting the first equation from the second equation, and then by subtracting the second equation from the third equation. We get $\sum_{i=0}^\infty i(i - 1)p_i = 1, \sum_{i=0}^\infty i^2(i - 1)p_i = 3.$ Subtract two times this left equation from the right equation to get $\sum_{i=0}^\infty i(i - 1)(i - 2)p_i = 1$ $(*)$ and then subtract three times the left equation from the right equation to get $\sum_{i=0}^\infty i(i - 1)(i - 3)p_i = 1$ $(**)$ . Noting that $p_2$ and $p_3$ vanish in $(*)$ and $(**)$ respectively, while $p_0$ and $p_1$ vanish in both, isolate $p_3$ in $(*)$ and $p_2$ in $(**)$ to get $p_3 = \frac{1}{6} - \sum_{i=4}^\infty \frac{i(i - 1)(i - 2)}{6}p_i, p_2 = \sum_{i=4}^\infty \frac{i(i - 1)(i - 3)}{2}p_i.$ Plug into the equation for $E[X] = 1$ and isolate $p_1$ to get $p_1 = \frac{1}{2} - \sum_{i=4}^\infty \left[i(i-1)(i-3) - \frac{i(i-1)(i-2)}{2} + i\right]p_i.$ Finally plug $p_1, p_2, p_3$ into the equation $\sum_{i=0}^\infty p_i = 1$ to get $p_0 + \frac{2}{3} - \sum_{i=4}^\infty \left[\frac{i(i-1)(i-3)}{2} - \frac{2i(i-1)(i-2)}{6} + i\right]p_i = 1.$ This final equation simplifies to $p_0 + \frac{2}{3} - \sum_{i=4}^{\infty} \left[\frac{i^3 - 6i^2 + 11i}{6}\right]p_i = 1 \rightarrow p_0 = \frac{1}{3} + \sum_{i=4}^{\infty} \left[\frac{i^3 - 6i^2 + 11i}{6}\right]p_i.$ Since probabilities must be nonnegative, and $i^3 - 6i^2 + 11i$ is positive for $i \ge 4$ , setting $p_4, p_5, ... = 0$ minimizes $p_0$ to be $\boxed{\frac{1}{3}.}$

Indeed, this is achievable with $p_0 = \frac{1}{3}, p_1 = \frac{1}{2}, p_2 = 0, p_3 = \frac{1}{6}$ and all other probabilities to be $0$ .

This post has been edited 2 times. Last edited by hnkevin42, Dec 29, 2017, 8:03 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

544 posts

#19 h Feb 12, 2019, 11:14 PM • 2 Y

Y by ImSh95, Adventure10

Solution... not very pretty.

Note

This post has been edited 3 times. Last edited by shankarmath, Feb 12, 2019, 11:20 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#20 h Aug 27, 2019, 9:46 PM • 2 Y

Y by ImSh95, Adventure10

This is a very very cute and funny problem.

We claim the minimum is $1/3$ , with equality achieved when $P(X=0)=1/3$ , $P(X=1)=1/2$ , $P(X=3)=1/6$ , and $P(X=n)=0$ for $n\not\in\{0,1,3\}$ .

Let $p_i=P(X=i)$ . Note that $f(k):=\sum_{i=1}^\infty i^k p_i$ satisfies $f(1)=1$ , $f(2)=2$ , and $f(3)=5$ . We see then that
$\sum_{i=1}^\infty\left[\frac{11}{6}i-i^2+\frac{1}{6}i^3\right]p_i=\frac{11}{6}f(1)-f(2)+\frac{1}{6}f(3)=2/3.$ Note that
$\frac{11}{6}i-i^2+\frac{1}{6}i^3\ge 1$ for all $i\in\mathbb{N}$ , so in fact,
$\left[\sum_{i=1}^\infty p_i\right]\le 2/3,$ so $p_0\ge 1/3$ , as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1318 posts

3ch03s

#21 h Aug 27, 2019, 11:27 PM • 3 Y

Y by ImSh95, Adventure10, Mango247

Ok. This is really interesting. Salute to heavens for kent.

for any polynomial $p(x)=ax^3+bx^2+cx+d$ we have $E[p(X)]=5a+2b+c+d$ . Then for $p(x)=(x-1)(x-2)(x-3)=x^3-6x^2+11x+6$ we have $E[p(X)]=-2$ , but $E[p(X)]=\sum_{k=0}^{\infty} p(k)P[X=k]=p(0)P[X=0]+\sum_{k>3} p(k)P[X=k]=-6P[X=0]+S=-2$ where $S=\sum_{k>3} p(k)P[X=k]\geq 0$ , as $p(k)>0$ for $k>3$ . So $P[X=0]\geq 1/3$ .

For equality note that $P[X=0]=1/3$ implies $S=0$ and then $P[X=k]=0,\forall k>3$ , that means $X$ takes values in 0,1,2,3 a.s. But note that if we set a polynomial with coefficents $a=1,b=-4,c=3,d=0$ we have $E[p(X)]=0$ and also $p(x)=x(x-1)(x-3)$ . so $E[P(X)]=p(2)P[X=2]=-P[X=2]=0$ then $P[X=2]=0$ .

finally note that $E[X-1]=0=2P[X=3]-P[X=0]=2P[X=3]-1/3$ and $E[X-3]=-2=-3P[X=0]-2P[X=1]=-1-2P[X=1]$ which gives $P[X=1]=1/2$ and $P[X=3]=1/6$ . and note that holds $E[X]=1/2+1/6*3=1, E[X^2]=1/2+1/6*9=2, E[X^3]=1/2+1/6*27=5$ .

Regards
Claudio.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#23 h Oct 11, 2019, 6:00 AM • 2 Y

Y by ImSh95, Adventure10

Let $p_i = \Pr[X=i]$ . We want to maximize $1-p_0=\textstyle \sum_{n=1}^\infty p_n$ . We have
$\begin{align*} \mathbb{E}[X]&=\sum_{n=1}^\infty np_n = 1 \implies p_1+2p_2+3p_3 = 1-\sum_{n=4}^\infty np_n := a \\ \mathbb{E}[X^2]&=\sum_{n=1}^\infty n^2p_n = 2 \implies p_1+4p_2+9p_3 = 2-\sum_{n=4}^\infty n^2p_n := b. \\ \mathbb{E}[X^3]&=\sum_{n=1}^\infty n^3p_n = 5 \implies p_1+8p_2+27p_3 = 5-\sum_{n=4}^\infty n^3p_n :=c. \end{align*}$ Solving this system of equations in $p_1,p_2,p_3$ in terms of $a,b,c$ , and summing $p_1+p_2+p_3$ gives
$p_1+p_2+p_3 = \frac{11}{6}a - b + \frac16 c.$ Substituing in the values of $a,b,c$ and adding $\textstyle \sum_{n=1}^\infty p_n$ to both sides gives
$\begin{align*} p_1+p_2+p_3+\sum_{n=4}^\infty p_n &= \frac{11}{6}\left[ 1-\sum_{n=4}^\infty np_n \right] - \left[ 2-\sum_{n=4}^\infty n^2p_n \right] + \frac16 \left[ 5-\sum_{n=4}^\infty n^3p_n \right] + \sum_{n=1}^\infty p_n \\ &= \frac23 + \sum_{n=4}^\infty \left[ -\frac16 n^3 + n^2 - \frac{11}{6} n + 1\right]p_n. \end{align*}$ But the term in the summation is always negative for $n\ge 4$ , so the maximum of $\textstyle \sum_{n=1}^\infty p_n$ is $\tfrac23$ , achieved when $p_n=0 \ \forall n\ge 4$ . Hence, the maximum of $p_0$ is $\tfrac13$ .

This post has been edited 1 time. Last edited by pad, Oct 15, 2019, 6:26 AM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2785 posts

#25 h Mar 17, 2020, 2:26 AM • 1 Y

Y by ImSh95

Let $x_i$ be the probability of $X=i$ ; we wish to maximize $\sum_{i=1}^{\infty}x_i$ . From $E(X)=1$ we have $x_1+2x_2+3x_3=1-\sum_{k=4}^{\infty} kx_k$ , from $E(X^2)=2$ we have $x_1+4x_2+9x_3=2-\sum_{k=4}^{\infty} k^2x_k$ , and from $E(X^2)=5$ we have $x_1+8x_2+27x_3=5-\sum_{k=4}^{\infty} k^3x_k$ . This is a three variable system of 3 equations, so we can solve for $x_1, x_2, x_3$ . After some computation, we find that $x_1+x_2+x_3=\frac{2}{3}+\sum_{k=4}^{\infty} (-\frac{1}{6}k^3+k^2-\frac{11}{6}k)x_k$ , so $\sum_{k=1}^{\infty} x_k=\frac{2}{3}+\sum_{k=4}^{\infty} (-\frac{1}{6}k^3+k^2-\frac{11}{6}k+1)x_k$ . However, it is not hard to see that $-\frac{1}{6}k^3+k^2-\frac{11}{6}k+1\le 0$ for all $k\ge 4$ , meaning that the optimal situation is when $x_4=x_5=x_6=....=0$ , in which case the answer is $x_0=\frac{1}{3}$ .

This post has been edited 1 time. Last edited by Stormersyle, Mar 17, 2020, 2:27 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

920 posts

Grizzy

#26 h Nov 27, 2020, 4:43 PM • 1 Y

Y by ImSh95

Let $p_i$ be the probability that $X = i$ . Then we have the equations

$p_1 + 2p_2 + 3p_3 + \cdots = 1,$
$p_1 + 4p_2 + 9p_3 + \cdots = 2,$
and

$p_1 + 8p_2 + 27p_3 + \cdots = 5.$
Adding $11$ times the first equation to the third equation and subtracting $6$ times the second equation yields

$6p_1 + 6p_2 + 6p_3 + \sum_{k \ge 4} (k^3 - 6k^2 + 11k)p_k = 4.$
Then we note that for $k \ge 4$ , we have the inequality

$k^3 - 6k^2 + 11k > 6,$
so

$4 = 6p_1 + 6p_2 + 6p_3 + \sum_{k \ge 4} (k^3 - 6k^2 + 11k)p_k \ge 6(p_1 + p_2 + p_3 + \cdots)$
or

$p_1 + p_2 + p_3 + \cdots \le \frac{2}{3}.$
Then since $p_0 + p_1 + p_2 + p_3 + \cdots = 1$ ,

$p_0 \ge \frac{1}{3}.$
Equality occurs when $p_1 = \frac{1}{2}, p_3 = \frac{1}{6},$ and the rest of the $p_i$ 's are $0$ . The answer is $\boxed{\frac{1}{3}}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

779 posts

#27 h Dec 6, 2020, 6:54 PM • 2 Y

Y by ImSh95, Mango247

For all nonnegative integers $i,$ let $p_i$ denote the probability that $X=i.$ From the given, we know that $\sum_{i>0}ip_i=1, \hspace{15pt}\sum_{i>0}i^{2}p_i=2, \hspace{15pt}\sum_{i>0}i^{3}p_i=5.$ Therefore,
$\begin{align*} \sum_{i>0}(i-1)(i-2)(i-3)p_i &= \sum_{i>0}i^{3}p_i-6\sum_{i>0}i^{2}p_i+11\sum_{i>0}ip_i-6\sum_{i>0}p_i\\ &= 5-6(2)+11(1)-6(1-p_0)\\ &= 6p_0-2. \end{align*}$ For all positive integers $i,$ we have $(i-1)(i-2)(i-3)\ge 0.$ Therefore, we have $6p_0-2\ge 0,$ so $p_0\ge\frac{1}{3}.$ Equality is achieved when $p_0=\frac{1}{3},p_1=\frac{1}{2},p_3=\frac{1}{6},$ so we are done.

This post has been edited 1 time. Last edited by amuthup, Dec 6, 2020, 6:55 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5000 posts

#28 h Oct 1, 2021, 1:15 PM • 2 Y

Y by centslordm, ImSh95

Very wacky solution.

The answer is $\tfrac{1}{3}$ , achieved with $\mathbb{P}(X=0)=\tfrac{1}{3},\mathbb{P}(X=1)=\tfrac{1}{2},\mathbb{P}(X=2)=\tfrac{1}{6}$ . It remains to show this is maximal. Define $p_i=\mathbb{P}(X=i)$ for $i \geq 0$ , and let $p_1+p_2+\cdots=c$ . Next define the random variable $Y$ such that $\mathbb{P}(Y=0)=0$ and $\mathbb{P}(Y=i)=\tfrac{p_i}{c}$ for $i \geq 1$ . Clearly we have
$\mathbb{E}[Y]=\frac{1}{c},\mathbb{E}[Y^2]=\frac{2}{c},\mathbb{E}[Y^3]=\frac{5}{c}.$ Now let $Z=Y-1$ , so by Linearity of Expectation we have
$\begin{align*} \mathbb{E}[Z]&=\mathbb{E}[Y-1]=\frac{1}{c}-1\\ \mathbb{E}[Z^2]&=\mathbb{E}[Y^2-2Y+1]=1\\ \mathbb{E}[Z^3]&=\mathbb{E}[Y^3-3Y^2+3Y-1]=\frac{2}{c}-1. \end{align*}$ By the infinite (discrete) form of Cauchy-Schwarz,
$\mathbb{E}[Z]\mathbb{E}[Z^3]=\left(\sum_{k \geq 0} kq_k\right)\left(\sum_{k\geq 0} k^3q_k\right)\geq \left(\sum_{k\geq 0} k^2q_k\right)^2=\mathbb{E}[Z^2]^2,$ where $q_i=\mathbb{P}(Z=i)$ for $i \geq 0$ , as $Z$ by definition only takes on nonnegative integer values. This means that
$\left(\frac{1}{c}-1\right)\left(\frac{2}{c}-1\right)\geq 1^2 \implies \frac{2}{c^2}-\frac{3}{c} \geq 0 \implies c\leq \frac{2}{3},$ hence $p_1+p_2+\cdots\leq \tfrac{2}{3} \implies p_0 \geq \tfrac{1}{3}$ , since $p_0+p_1+p_2+\cdots=1$ . $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Oct 6, 2021, 1:13 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7320 posts

DottedCaculator

#29 h Oct 3, 2021, 2:00 AM • 4 Y

Y by centslordm, mathlearner2357, ImSh95, smartvong

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

63 posts

RM1729

#30 h Nov 9, 2021, 6:02 PM • 1 Y

Y by ImSh95

Let $p_i$ denote the probability of non negative integer $i$ .

We have,

$\sum i \cdot p_i = 1$
$\sum i^2 \cdot p_i = 2$
$\sum i^3 \cdot p_i = 5$
Hence note that,

$\sum (i^3-6i^2+11i-6) \cdot p_i = -2$
$\Rightarrow \sum (i-1)(i-2)(i-3) \cdot p_i = -2$
Thus,

$-6 \cdot p_0 + 0 + 0 + 0 +6 p_4 +\cdots = -2$
And hence,

$p_0 \geq \frac{1}{3}$
Note that equality can be achieved by taking $p_0=\frac{1}{3}, p_1=\frac{1}{2}, p_3=\frac{1}{6}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

279 posts

#31 h Jun 27, 2023, 3:14 AM • 2 Y

Y by ImSh95, Sagnik123Biswas

Let $p_k$ represent the probability that $X$ takes the value of $k$ . Notice that we have that
$p_1+2p_2+3p_3+\dots{}=1,$ $p_1+4p_2+9p_3+\dots{}=2,$ and
$p_1+8p_2+27p_3+\dots{}=5.$
Taking $11$ times the first equation, $-6$ times the second, and $1$ time(s) the third, and adding them together gives that
$6p_1+6p_2+6p_3+6p_4+\dots+\alpha{}=4$ where $\alpha$ is some nonnegative number. This gives that $\sum{}_{k>0}p_k\leq{}\frac{2}{3}$ , meaning that $p_0$ is at least $\frac{1}{3}$ , which indeed occurs when $p_1=\frac{1}{2}$ , $p_3=\frac{1}{6}$ , and the rest are zero.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2982 posts

#32 h Jun 30, 2023, 6:07 AM • 2 Y

Y by ImSh95, PRMOisTheHardestExam

hmm i had a different solution than most people

Let $p_i$ denote the probability of picking $i$ . The answer is $\frac 13$ , with equality achieved when $p_0 = \frac 13, p_1=\frac{1}{2}, p_3=\frac{1}{6}$ , and $p_i = 0$ for $i\neq 0, 1, 3$ . We can write
$\begin{align*} \sum p_i(i-1) &= \mathbb E[X] - 1 = 0\\ \sum p_i(i-1)^2 &= \mathbb E[X^2] - 2\mathbb E[X] + 1 = 1\\ \sum p_i(i-1)^3 &= \mathbb E[X^3]-3\mathbb E[X^2] +3\mathbb E[X] - 1 = 1 \end{align*}$ By Cauchy,
$p_0(1+p_0)=\left( \sum_{i=1}^\infty p_i(i-1) \right) \left( \sum_{i=1}^\infty p_i(i-1)^3 \right) \geq \left( \sum_{i=1}^\infty p_i(i-1)^2 \right)^2 = (1-p_0)^2.$ Solving, we get $p_0 \geq \frac 13$ , as desired.

This post has been edited 2 times. Last edited by bobthegod78, Jul 4, 2023, 5:31 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sagnik123Biswas

418 posts

Sagnik123Biswas

#33 h Aug 3, 2023, 8:48 AM

Y by

Intuition: If we think of $X$ geometrically, then placing more “mass” to the right would yield more pressure on $0$ to have higher concentration. Thus we place as many values at the left end. After some playing around, we see X has to span values until $3$ , from which we use the information given and get $p=0$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

419 posts

#34 h Dec 26, 2023, 7:26 PM

Y by

For each nonnegative integer $n$ , let $p_n$ denote the probability of the event $X=n$ . The following equations are valid:
$\begin{cases}\sum_{i=0}^{\infty}p_i=1, \\ \sum_{i=0}^{\infty}ip_i=1, \\ \sum_{i=0}^{\infty}i^2p_i=2, \\ \sum_{i=0}i^3p_i=5. \end{cases}$ Let $F(x)=p_0+p_1x+p_2x^2+p_3x^3+\cdots$
Then, $F'(x)=p_1+2p_2x+3p_3x^2+4p_4x^3+\cdots$
$F''(x)=2p_2+6p_3x+12p_4x^2+\cdots$
$F'''(x)=6p_3+24p_4x+60p_4x^2+\cdots$
So, $F'(x)+xF''(x)=p_1+4p_2x+9p_3x^2+\cdots$
So, $F'(x)+3xF''(x)+F'''(x)=p_1+8p_2x+27p_3x^2+\cdots$
We are given $F(1)=1$ , $F'(1)=1$ , $F'(1)+F''(1)=2$ and $F'(1)+3F''(1)+F'''(1)=3$ .
So, $F(1)=F'(1)=F''(1)=F'''(1)=1$ .
From Taylor expansion, we have
$F(x)=F(1)+F'(1)(x-1)+\frac{F''(1)}2(x-1)^2+\frac{F'''(1)}{6}(x-1)^3+\cdots$
We can just set $F''''(1)=0=F'''''(1)=F''''''(1)=\cdots$ for attaining minimum value.
So, $F(0)=p_0=1-1+\frac12-\frac16=\boxed{\frac13}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5542 posts

#35 h Feb 28, 2024, 4:58 PM • 2 Y

Y by blueberryfaygo_55, centslordm

Let $p_i$ denote the probability of $X = i$ for each positive integer $i$ .

The answer is $\boxed{ \frac 13}$ , achieved by $p_0 = \frac 13, p_1 = \frac 12, p_3 = \frac 16$ and all other probabilities are zero. Now we prove the bound.

Notice that $\mathbb E [X^3 - 6X^2 + 11X] = 5 - 6\cdot 2 + 1 = 4$ , but we also have $\mathbb E[X^3 - 6X^2 + 11X] = 6(p_1 + p_2 + p_3) + \sum_{i=4}^{\infty} (i^3 - 6i^2 + 11i) p_i \ge 6\left( \sum_{i=1}^\infty p_i \right),$ so $\sum_{i=1}^{\infty} p_i \le \frac 23$ , implying that $p_0 \ge \frac 13$ , as desired.

This post has been edited 1 time. Last edited by megarnie, Feb 28, 2024, 4:59 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1728 posts

OronSH

#36 h Jul 19, 2024, 11:35 PM • 1 Y

Y by centslordm

Consider $\mathbb E[X^3-6X^2+11X-6]=\mathbb E[(X-1)(X-2)(X-3)].$ By linearity of expectation it must be $5-6\cdot 2+11\cdot 1-6=-2.$ But it is always positive, except when $X=0$ and it is $-6.$ It follows that $X=0$ occurs with probability at least $\frac13.$ Equality holds at $P(X=0)=\frac13,P(X=1)=\frac12,P(X=3)=\frac16,P(X\ne0,1,3)=0.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1251 posts

ezpotd

#37 h Aug 8, 2024, 11:58 AM

Y by

We can rewrite the givens in the form $\sum_{i = 1}^{\infty} ip_i = 1$ , $\sum_{i = 1}^{\infty} i^2p_i = 2$ , $\sum_{i = 1}^{\infty} i^3p_i = 5$ , where $p_i$ are implicitly in $[0, 1]$ . Zero is excluded from the previous summations since it doesn't contribute anyways. To minimize $p_0$ is to maximize $p_1 + p_2 + \cdots$ over the interval where all $p_i$ are in $[0,1]$ . We instead maximize it where $p_i$ varies over all reals for $i = 1,2,3$ and $i$ is in $[0,1]$ otherwise, clearly any bound here also bounds the smaller range. We claim the maximum is achieved at $p_1 = \frac 12, p_2 = 0, p_3 = \frac 16$ , $p_i = 0$ for all other $i$ . We use a smoothing argument, take any such $i$ with $p_i > 0, i > 3$ , then there existing a unique $x,y,z$ satisfying $x + 2y + 3z = ip_i, x + 4y + 9z = i^2p_i, x + 8y + 27z = i^3p_i$ , set $p_1 += x, p_2 += y, p_3 += y, p_i -= p_i$ . Clearly the three givens are conserved, it remains to show that $x + y + z > p_i$ . Of course, we can write $x + y + z = \frac{11}{6} (x + 2y + 3z ) - (x + 4y + 9z) + \frac 16 (x + 8y + 29z) = \frac{11}{6} ip_i - i^2p_i + \frac 16 i^3 p_i$ . Dividing by $\frac{p_i}{6}$ , we desire to show then $i^3 - 6i^2 + 11i > 6$ , which is trivial since it resolves to $(i - 1)(i - 2)(i - 3)$ . Now we can apply this operation simultaneously for all $i$ such that $p_i > 0, i > 3$ (alternatively, claim the optimal case is when all $p_i$ with $i > 3$ are $0$ , assume otherwise and take some minimal $i > 3$ contradicting this, then apply operation), we are then left with $p_i = 0$ for all $i > 3$ , then the optimal case is forced from there since we have $3$ equations in $3$ variables.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

984 posts

bebebe

#38 h Aug 26, 2024, 5:57 PM

Y by

Let $p_i$ be the probability of event $i.$ We claim that the minimal is $p_0=\frac{2}{3},$ which is obtained when $p_1=\frac{1}{2}, p_3=\frac{1}{6},$ and $p_i=0$ for all other $i$ 's.

From the expected values, we know $1=p_1+2p_2+3p_3+\dots,$ $2=p_1+4p_2+9p_3+\dots,$ $5=p_1+8p_2+27p_3+\dots.$ We also know $p_0=1-p_1-p_2-p_3-\dots.$ We need to maximize $p_1+p_2+\dots.$ We claim that we can 'absorb' $p_i$ (where $i \ge 4$ ) into $p_1, p_2, p_3$ so that the expected values are satisfied, but the sum $p_1+p_2+\dots$ increases. In other words, if we set $p_i=0,$ then $p_1' + 2p_2' + 3p_3' = i p_i,$ $p_1'+4p_2'+9p_3'=i^2 p_i,$ $p_1'+8p_2'+27p_3' = i^3 p_i,$ where $p_1', p_2', p_3'$ is the change in $p_1, p_2, p_3$ respectively. This system of equations has a unique solution, so $p_1, p_2, p_3$ can indeed absorb $p_i$ while satisfying the expected values. The sum increases because $p_1'+p_2'+p_3' \ge \frac{p_1'}{4}+\frac{2p_2'}{4}+\frac{3p_3'}{4} \ge \frac{p_1'}{i}+\frac{2p_2'}{i}+\frac{3p_3'}{i}=p_i.$ Therefore, the greatest sum is achieved when $p_i=0$ where $i \ge 4.$

Solving the system $1=p_1+2p_2+3p_3,$ $2=p_1+4p_2+9p_3,$ $5=p_1+8p_2+27p_3,$ gives $p_1=\frac12, p_2=0, p_3=\frac16,$ and we get $p_0=\boxed{\frac23}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

996 posts

bjump

#39 h Mar 13, 2025, 5:09 PM • 1 Y

Y by OronSH

Let $p_k$ denote the probability $X=k$ .
We have
$\sum_{k=0}^\infty p_k = \sum_{k=0}^\infty kp^k = 1$ $\sum_{k=0}^\infty k^2 p_k = 2 , \sum_{k=0}^\infty k^3 p_k=5$ Linearly combining sums gives
$-2 = \sum_{k=0}^\infty (k-1)(k-2)(k-3)p_k \implies 6(p_0-\tfrac{1}{3}) =\sum_{k=4}^\infty (k-1)(k-2)(k-3)p_k$ Which means $p_0 \ge \tfrac{1}{3}$ this is attainable when $p_0 = \tfrac{1}{3}$ , $p_2 = \tfrac{1}{2}$ , and $p_3 = \tfrac{1}{6}$ .

This post has been edited 1 time. Last edited by bjump, Mar 13, 2025, 5:41 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a