A note on the Littlewood-Offord problem for discrete log-concave distributions
Marsiglietti, Melbourne
We present an extension of the famous Littlewood-Offord problem when Bernoulli distributions are replaced with discrete log-concave distributions. A variant of the Littlewood-Offord problem for arithmetic progressions, as well as an entropic version, is also discussed. Along the way, we recover and extend a result of Madiman and Woo (2015) on the entropy power inequality for discrete uniform distributions.
academic
লিটলউড-অফোর্ড সমস্যা সম্পর্কে একটি নোট বিচ্ছিন্ন লগ-অবতল বিতরণের জন্য
এই পত্রটি বিখ্যাত লিটলউড-অফোর্ড সমস্যাকে বার্নৌলি বিতরণ থেকে বিচ্ছিন্ন লগ-অবতল বিতরণে সাধারণীকরণ করে। নিবন্ধটি গাণিতিক অগ্রগতির লিটলউড-অফোর্ড সমস্যা বৈকল্পিক এবং এন্ট্রপি সংস্করণ নিয়ে আলোচনা করে। এই প্রক্রিয়ায়, লেখকরা ম্যাডিম্যান এবং উ (২০১৫) সম্পর্কে বিচ্ছিন্ন সমান বিতরণের এন্ট্রপি শক্তি অসমতার ফলাফল পুনরুদ্ধার এবং প্রসারিত করেন।
লিটলউড-অফোর্ড সমস্যা সম্ভাবনা তত্ত্ব এবং সমন্বয় গণিতে একটি ধ্রুবক সমস্যা। ভেক্টর a=(a1,…,an)∈(R∖{0})n এবং স্বাধীন রেডেমাকার র্যান্ডম ভেরিয়েবল X1,…,Xn (অর্থাৎ P(Xk=±1)=1/2) দেওয়া হলে, সমস্যাটি হল অনুমান করা:
supx∈RP(a1X1+⋯+anXn=x)
ক্লাসিক লিটলউড-অফোর্ড এবং এরডোস ফলাফল দেখায় যে উপরের সীমা O(1/n)।
১. তাত্ত্বিক সম্প্রসারণের প্রয়োজন: ক্লাসিক ফলাফল প্রধানত ১/২ প্যারামিটার সহ বার্নৌলি বিতরণের জন্য, ফক্স এট আল (২০১৮) প্রস্তাব করেছেন যে সমস্যাটি নির্বিচারে প্যারামিটার সহ বার্নৌলি বিতরণে প্রসারিত করা যায় কিনা
२. বিতরণ শ্রেণী সাধারণীকরণ: বিচ্ছিন্ন লগ-অবতল বিতরণ একটি গুরুত্বপূর্ণ বিতরণ শ্রেণী, যার মধ্যে রয়েছে সমান বিতরণ, বার্নৌলি বিতরণ, দ্বিপদী বিতরণ, পয়সন বিতরণ, জ্যামিতিক বিতরণ ইত্যাদি
३. ব্যবহারিক প্রয়োগ: এই সমস্যাটি বিপরীত ঘনীভবন অসমতা, সমন্বয় সংখ্যা তত্ত্ব এবং অন্যান্য ক্ষেত্রের সাথে ঘনিষ্ঠভাবে সম্পর্কিত
४. তাত্ত্বিক একীকরণ: আরও বিস্তৃত বিতরণ শ্রেণীর জন্য একটি একীভূত তাত্ত্বিক কাঠামো প্রদান করার চেষ্টা
१. প্রধান উপপাদ্য সাধারণীকরণ: লিটলউড-অফোর্ড সমস্যাকে সমস্ত সীমিত সমর্থন বিচ্ছিন্ন লগ-অবতল বিতরণে প্রসারিত করা (উপপাদ্য १.१), প্রমাণ করা হয়েছে:
supa∈(R∖{0})nsupx∈RP(a⋅X=x)≤1+c∑k=1nVar(Xk)1
যেখানে c=1, কিছু বিন্দু সম্পর্কে প্রতিসম বিতরণের জন্য c=2 নেওয়া যায়
२. এন্ট্রপি সংস্করণ: লিটলউড-অফোর্ড সমস্যার রেনি এন্ট্রপি শক্তি সংস্করণ প্রস্তাব করা (উপপাদ্য १.२), এন্ট্রপি শক্তির নিম্ন সীমা স্থাপন করা
३. গাণিতিক অগ্রগতি বৈকল্পিক: গাণিতিক অগ্রগতিতে লিটলউড-অফোর্ড সমস্যা সমাধান করা (উপপাদ্য १.३), P(a⋅X∈Al,m(x)) এর উপরের সীমা দেওয়া
४. এন্ট্রপি শক্তি অসমতা: ম্যাডিম্যান এবং উ সম্পর্কে বিচ্ছিন্ন সমান বিতরণের এন্ট্রপি শক্তি অসমতা পুনরুদ্ধার এবং প্রসারিত করা (উপপাদ্য १.४)
५. সর্বোত্তমতা বিশ্লেষণ: প্রমাণ করা হয়েছে যে প্রাপ্ত সীমা ধ্রুবক অর্থে কঠোর
পত্রের মূল প্রযুক্তিগত সরঞ্জাম হল প্রধান নীতি তত্ত্ব। সম্ভাবনা বিতরণ p,q এর জন্য, যদি:
∑i=1kqi≥∑i=1kpi,∀k
তাহলে p কে q দ্বারা প্রধান বলা হয়, p≺q দ্বারা চিহ্নিত করা হয়।
মূল লেম্মা २.२: যদি Y একটি সীমিত মূল্যবান র্যান্ডম ভেরিয়েবল হয়, f একটি নির্ধারক ফাংশন হয়, তাহলে Y≺f(Y)।
উপপাদ্য ३.१ (মূল প্রযুক্তিগত উপপাদ্য): সহগ ai∈R∖{0} এবং স্বাধীন লগ-অবতল পূর্ণসংখ্যা-মূল্যবান র্যান্ডম ভেরিয়েবল Xi এর জন্য, চিহ্ন vi∈{±1} বিদ্যমান যেমন:
a⋅X≺v⋅X
প্রমাণ কৌশল:
१. প্রথমে রৈখিক রূপান্তর T:R→Q এর মাধ্যমে বাস্তব সহগকে পূর্ণসংখ্যা সহগে হ্রাস করুন
२. সংকুচিত পুনর্বিন্যাস ব্যবহার করে, (T(ai)Xi)#=viXi, যেখানে vi=sign(T(ai))
३. উপপাদ্য २.३ প্রয়োগ করে হ্রাস সম্পূর্ণ করুন
१. হ্রাস পদক্ষেপ: উপপাদ্য ३.१ দ্বারা, যেকোনো a এর জন্য, চিহ্ন v বিদ্যমান যেমন a⋅X≺v⋅X
२. পরিচিত সীমা প্রয়োগ করুন: উপপাদ্য २.१ ব্যবহার করুন (অরবিন্দা এবং বোবকভ এট আল এর ফলাফল):
M(X)≤1+Var(X)1
লগ-অবতল র্যান্ডম ভেরিয়েবলের জন্য
३. ভেরিয়েন্স গণনা: Var(v⋅X)=∑i=1nVar(Xi) (vi=±1 কারণে)
४. উপসংহার:
M(a⋅X)≤M(v⋅X)≤1+∑k=1nVar(Xk)1
१. শুর অবতলতা: রেনি এন্ট্রপি Hα শুর অবতল
२. প্রধান সংক্রমণ: উপপাদ্য ३.१ দ্বারা, Nα(a⋅X)≥Nα(v⋅X)
३. এন্ট্রপি-ভেরিয়েন্স সম্পর্ক: Nα(X)≥1+Var(X) ব্যবহার করুন (উপপাদ্য २.१ এবং একঘেয়েতা দ্বারা)
४. বিশেষ ক্ষেত্র অপ্টিমাইজেশন: যখন 1<α≤2, আরও শক্তিশালী সীমা ব্যবহার করা যায় Nα(X)≥1+4Var(X)
१. একীভূত কাঠামো: প্রধান নীতি তত্ত্ব এবং চিহ্ন হ্রাসের মাধ্যমে, সাধারণ বিচ্ছিন্ন লগ-অবতল বিতরণ সমস্যা চিহ্ন সমস্যায় একীভূত হ্রাস পায়
२. সংকুচিত পুনর্বিন্যাস কৌশল: সংকুচিত পুনর্বিন্যাস ব্যবহার করে নির্বিচারে সহগ সমস্যাকে চিহ্ন সমস্যায় রূপান্তরিত করা, এটি মূল উদ্ভাবন
३. এন্ট্রপি-সম্ভাবনা দ্বৈত দৃষ্টিভঙ্গি: বিন্দু সম্ভাবনা অনুমান এবং এন্ট্রপি শক্তি অনুমানের মধ্যে সংযোগ স্থাপন করা, M(X)=e−H∞(X) এর মাধ্যমে
४. গাণিতিক অগ্রগতি পরিচালনা: গাণিতিক অগ্রগতি সমস্যাকে সমান বিতরণের সাথে কনভোলিউশন সমস্যায় রূপান্তরিত করা:
P(Y∈Al,m(x))=l⋅P(Y−mUl=x)
যেখানে Ul হল {1,…,l} এ সমান বিতরণ
५. ফুরিয়ার বিশ্লেষণ প্রয়োগ (অংশ ५): বার্নৌলি বিতরণের জন্য, হাউসডর্ফ-ইয়াং অসমতা এবং হোল্ডার অসমতা ব্যবহার করে আরও সূক্ষ্ম সীমা পান
१. ভেরিয়েন্সের মূল ভূমিকা: সমস্ত সীমা ভেরিয়েন্স যোগ ∑Var(Xk) এর উপর নির্ভর করে, এটি প্রাকৃতিক এবং সর্বোত্তম
२. প্রতিসমতা উন্নতি: প্রতিসম বিতরণ ধ্রুবক २ গুণ উন্নতি পেতে পারে
३. এন্ট্রপি-সম্ভাবনা একীকরণ: M(X)=e−H∞(X) এর মাধ্যমে, বিন্দু সম্ভাবনা সমস্যা এন্ট্রপি সমস্যার বিশেষ ক্ষেত্র
४. প্রধান নীতি তত্ত্বের শক্তি: চিহ্ন হ্রাস কৌশল জটিল সমস্যাকে মার্জিতভাবে সরল করে
१. লিটলউড-অফোর্ড (१९४३) এবং এরডোস (१९४५): ক্লাসিক O(1/n) সীমা স্থাপন করা
२. ক্লেইটম্যান (१९६५, १९७०): হিলবার্ট স্পেসে ভেক্টরে সাধারণীকরণ
३. হালাজ (१९७७): সহগ সীমাবদ্ধতার অধীনে উন্নত সীমা
४. তাও-ভু (२०१०) এবং নগুয়েন-ভু (२०११): বিপরীত লিটলউড-অফোর্ড উপপাদ্য
५. বান্ডেইরা-ফার্বার-কোয়ান (२०१७): স্থিতিস্থাপক সংস্করণ
६. ফক্স-কোয়ান-সাউয়ারম্যান (२०२१): নির্বিচারে প্যারামিটার বার্নৌলি বিতরণের সমস্যা প্রস্তাব করা
७. সিংহাল (२०२२): আংশিক সমাধান
८. মেলবোর্ন-ম্যাডিম্যান-রবার্তো (२०२३): সম্পূর্ণ সমাধান, c=2 সীমা প্রমাণ করা
१३. মার্শাল-ওলকিন-আর্নল্ড (२०११): প্রধান নীতি তত্ত্বের ক্লাসিক কাজ
१४. ম্যাডিম্যান-ওয়াং-উ (२०१७): স্পার্নার তত্ত্বের মাধ্যমে প্রধান নীতি এবং রেনি এন্ট্রপি অসমতা
१५. ম্যাডিম্যান-উ (२०१५): বিচ্ছিন্ন সমান বিতরণের এন্ট্রপি শক্তি অসমতা
१६. মেলবোর্ন-টকোজ (२०२०): লগ-অবতলের অধীনে রেনি এন্ট্রপি অসমতা বিপরীত
१. মূল উপপাদ্য: সফলভাবে লিটলউড-অফোর্ড সমস্যাকে সমস্ত সীমিত সমর্থন বিচ্ছিন্ন লগ-অবতল বিতরণে সাধারণীকৃত করা, সীমা:
1+c∑Var(Xk)1
যেখানে c∈{1,2} প্রতিসমতার উপর নির্ভর করে
२. পদ্ধতিগত অবদান: চিহ্ন হ্রাস কৌশল স্থাপন করা, এটি সাধারণ সহগ সমস্যা পরিচালনার মূল সরঞ্জাম
३. তাত্ত্বিক একীকরণ: রেনি এন্ট্রপি শক্তি কাঠামোর মাধ্যমে, বিন্দু সম্ভাবনা অনুমান, এন্ট্রপি অসমতা এবং গাণিতিক অগ্রগতি সমস্যা একীভূত করা
४. বিদ্যমান ফলাফল পুনরুদ্ধার: বিশেষ ক্ষেত্র হিসাবে একাধিক পরিচিত গুরুত্বপূর্ণ ফলাফল পুনরুদ্ধার করা
গুরুত্বপূর্ণ সাধারণীকরণ: ক্লাসিক সমস্যাকে রেডেমাকার/বার্নৌলি বিতরণ থেকে সম্পূর্ণ বিচ্ছিন্ন লগ-অবতল শ্রেণীতে সাধারণীকৃত করা, এটি বাস্তব তাত্ত্বিক অগ্রগতি
মার্জিত পদ্ধতি: চিহ্ন হ্রাস কৌশল (উপপাদ্য ३.१) অত্যন্ত মার্জিত, জটিল সমস্যাকে সারাংশে সরল করে
একীভূত কাঠামো: প্রধান নীতি তত্ত্বের মাধ্যমে একীভূত পরিচালনা পদ্ধতি প্রদান করা, অত্যন্ত শক্তিশালী তাত্ত্বিক সৌন্দর্য
१. তাত্ত্বিক ভিত্তি: বিচ্ছিন্ন লগ-অবতল বিতরণের বিপরীত ঘনীভবন তত্ত্যের জন্য ভিত্তিমূলক ফলাফল প্রদান করা
२. পদ্ধতিগত: চিহ্ন হ্রাস এবং প্রধান নীতি তত্ত্যের প্রয়োগ সম্পর্কিত সমস্যার জন্য নতুন চিন্তাভাবনা প্রদান করা
३. পরবর্তী গবেষণা: ধ্রুবক অপ্টিমাইজেশন, উচ্চ-মাত্রিক সাধারণীকরণ ইত্যাদির জন্য দিকনির্দেশনা খোলা
१. সম্ভাবনা তত্ত্ব: বিপরীত ঘনীভবন অসমতা, যোগের বিতরণ তত্ত্ব
२. সমন্বয় গণিত: যোজক সমন্বয়, র্যান্ডম যোগ সমস্যা
३. তথ্য তত্ত্ব: এন্ট্রপি অসমতা, তথ্য তাত্ত্বিক সীমা
१. এরডোস (१९४५): ক্লাসিক লিটলউড-অফোর্ড সমস্যার ভিত্তিমূলক ফলাফল
२. মেলবোর্ন-ম্যাডিম্যান-রবার্তো (२०२३): বার্নৌলি বিতরণের সম্পূর্ণ সমাধান, এই পত্রের সরাসরি পূর্বসূরী
३. ম্যাডিম্যান-ওয়াং-উ (२०१७): রেনি এন্ট্রপিতে প্রধান নীতি তত্ত্যের প্রয়োগ, মূল প্রযুক্তি প্রদান করা
४. বোবকভ-মার্সিগলিয়েটি-মেলবোর্ন (२०२२): বিচ্ছিন্ন লগ-অবতল বিতরণের ঘনীভবন ফাংশন সীমা, উপপাদ্য २.१ প্রদান করা
५. ম্যাডিম্যান-উ (२०१५): বিচ্ছিন্ন সমান বিতরণের এন্ট্রপি শক্তি অসমতা, এই পত্রের সাধারণীকরণের সূচনা বিন্দু
এটি একটি উচ্চ মানের তাত্ত্বিক গণিত পত্র, লিটলউড-অফোর্ড সমস্যা এই ধ্রুবক সমস্যায় বাস্তব অগ্রগতি অর্জন করেছে। প্রধান নীতি তত্ত্ব এবং চিহ্ন হ্রাস কৌশল প্রবর্তন করে, লেখক মার্জিতভাবে সমস্যাটি সম্পূর্ণ বিচ্ছিন্ন লগ-অবতল বিতরণ শ্রেণীতে সাধারণীকৃত করেছেন। পত্রের প্রধান মূল্য হল:
१. তাত্ত্বিক গভীরতা: সাধারণ লগ-অবতল বিতরণ পরিচালনার জন্য একীভূত কাঠামো প্রদান করা
२. পদ্ধতি উদ্ভাবন: চিহ্ন হ্রাস সাধারণ সহগ সমস্যা পরিচালনার মূল উদ্ভাবন
३. ফলাফল সম্পূর্ণতা: সম্ভাবনা, এন্ট্রপি এবং গাণিতিক অগ্রগতি একাধিক দিক একযোগে পরিচালনা করা
४. কঠোরতা: সমস্ত ফলাফলের সম্পূর্ণ প্রমাণ, এবং কঠোরতা বিশ্লেষণ করা
প্রধান সীমাবদ্ধতা ধ্রুবক ফ্যাক্টরের অ-সর্বোত্তমতা এবং সীমিত সমর্থন অনুমানে। কিন্তু এগুলি পত্রের মূল অবদানকে প্রভাবিত করে না। এই কাজ বিচ্ছিন্ন সম্ভাবনা তত্ত্ব এবং বিপরীত ঘনীভবন তত্ত্যের জন্য গুরুত্বপূর্ণ তাত্ত্বিক সরঞ্জাম প্রদান করে, সম্পর্কিত ক্ষেত্রে ক্রমাগত প্রভাব ফেলবে বলে প্রত্যাশিত।
সুপারিশ সূচক: ⭐⭐⭐⭐⭐ (५/५)
উপযুক্ত পাঠক: সম্ভাবনা তত্ত্ব, সমন্বয় গণিত, তথ্য তত্ত্ব গবেষকরা