Matrix Chernoff bound
রৈখিক বীজগণিতে নির্দিষ্ট প্রয়োগের জন্য, র্যান্ডম ম্যাট্রিক্সের একটি সীমাবদ্ধ যোগফলের বৃহত্তম আইগেনভ্যালু সম্ভাব্যতা বিতরণের বৈশিষ্ট্যগুলি জানা দরকারী। ধরুন এটি এলোমেলো ম্যাট্রিক্সের একটি সসীম ক্রম। স্কেলারের যোগফলের জন্য সুপরিচিত চেরনোফের অনুরূপ, একটি প্রদত্ত প্যারামিটার টি-এর জন্য নিম্নলিখিতগুলির একটি সীমা চাওয়া হয়ঃ নিম্নলিখিত উপপাদ্যগুলি বিভিন্ন অনুমানের অধীনে এই সাধারণ প্রশ্নের উত্তর দেয়; এই অনুমানগুলি তাদের শাস্ত্রীয়, স্কেলার প্রতিরূপগুলির সাথে সাদৃশ্য দ্বারা নীচে নামকরণ করা হয়েছে। এই সমস্ত উপপাদ্য একটি সাধারণ ফলাফলের নির্দিষ্ট প্রয়োগ হিসাবে পাওয়া যেতে পারে যা নীচে প্রাপ্ত। সম্পর্কিত কাজগুলির একটি সারসংক্ষেপ দেওয়া হয়েছে। ম্যাট্রিক্স গাউসিয়ান এবং রাডেমাকার সিরিজ স্ব-সংযুক্ত ম্যাট্রিক্সের ক্ষেত্রে মাত্রা সহ স্থির, স্ব-সংযুক্ত ম্যাট্রিক্সের একটি সীমাবদ্ধ ক্রম বিবেচনা করুন এবং স্বাধীন স্ট্যান্ডার্ড স্বাভাবিক বা স্বাধীন রাডেমাকার র্যান্ডম ভেরিয়েবলের একটি সীমাবদ্ধ ক্রম হতে দিন। তারপর, সকলের জন্য, যেখানে আয়তক্ষেত্রাকার ক্ষেত্রে মাত্রা সহ স্থির, স্ব-সংযুক্ত ম্যাট্রিক্সের একটি সীমাবদ্ধ ক্রম বিবেচনা করুন এবং স্বাধীন স্ট্যান্ডার্ড স্বাভাবিক বা স্বাধীন র্যাডেমাচার র্যান্ডম ভেরিয়েবলের একটি সীমাবদ্ধ ক্রম হতে দিন। তারপর, সকলের জন্য, ম্যাট্রিক্স চেরনোফ অসমতা ধ্রুপদী চেরনোফ সীমানা স্বাধীন, অ-নেতিবাচক এবং অভিন্নভাবে আবদ্ধ র্যান্ডম ভেরিয়েবলের যোগফল নিয়ে উদ্বেগ প্রকাশ করে। ম্যাট্রিক্স সেটিং-এ, অনুরূপ উপপাদ্যটি একটি অভিন্ন আইগেনভ্যালু বাউন্ড সাপেক্ষে ধনাত্মক-সেমিডিফাইনাইট র্যান্ডম ম্যাট্রিক্সের যোগফল নিয়ে উদ্বেগ প্রকাশ করে। প্রথম ম্যাট্রিক্স চেরনোফ মাত্রা সহ স্বাধীন, এলোমেলো, স্ব-সংযুক্ত ম্যাট্রিক্সের একটি সীমাবদ্ধ ক্রম বিবেচনা করুন। ধরে নিন যে প্রতিটি র্যান্ডম ম্যাট্রিক্স প্রায় নিশ্চিতভাবে সন্তুষ্ট করে। তারপর ম্যাট্রিক্স চেরনোফ দ্বিতীয় সংজ্ঞায়িত করুন স্বাধীন, এলোমেলো, স্ব-সংযুক্ত ম্যাট্রিক্সের একটি ক্রম বিবেচনা করুন যা প্রায় নিশ্চিতভাবে সন্তুষ্ট করে। গড় প্রত্যাশার ন্যূনতম এবং সর্বাধিক আইগেনভ্যালু গণনা করুন, তারপর বাইনারি তথ্য বিচ্যুতি হিসাবে সংজ্ঞায়িত করা হয়। ম্যাট্রিক্স বেনেট এবং বার্নস্টাইনের অসমতা স্কেলার সেটিংয়ে, বেনেট এবং বার্নস্টাইনের অসমতা স্বাধীন, শূন্য-অর্থ র্যান্ডম ভেরিয়েবলের যোগফলের উপরের লেজকে বর্ণনা করে যা হয় আবদ্ধ বা সাবএক্সপোনেনশিয়াল। ম্যাট্রিক্সের ক্ষেত্রে, অনুরূপ ফলাফলগুলি শূন্য-অর্থ র্যান্ডম ম্যাট্রিক্সের সমষ্টি নিয়ে উদ্বেগ প্রকাশ করে। বাউন্ডেড কেস মাত্রা সহ স্বাধীন, এলোমেলো, স্ব-সংযুক্ত ম্যাট্রিক্সের একটি সীমাবদ্ধ ক্রম বিবেচনা করুন। ধরে নিন যে প্রতিটি র্যান্ডম ম্যাট্রিক্স প্রায় নিশ্চিতভাবে সন্তুষ্ট করে। মোট বৈচিত্র্যের মান গণনা করুন, তারপর, বৈষম্যের নিম্নলিখিত শৃঙ্খলাটি সকলের জন্য রয়েছেঃ ফাংশনটি হিসাবে সংজ্ঞায়িত করা হয়। সাবএক্সপোনেনশিয়াল কেস মাত্রা সহ স্বাধীন, এলোমেলো, স্ব-সংযুক্ত ম্যাট্রিক্সের একটি সীমাবদ্ধ ক্রম বিবেচনা করুন। এর জন্য অনুমান করুন। ভেরিয়েন্স প্যারামিটারটি গণনা করুন, তারপর, বৈষম্যের নিম্নলিখিত শৃঙ্খলটি সকলের জন্য রয়েছেঃ আয়তক্ষেত্রাকার ক্ষেত্রে মাত্রা সহ স্বাধীন, এলোমেলো, ম্যাট্রিক্সের একটি সীমাবদ্ধ ক্রম বিবেচনা করুন। ধরে নিন যে প্রতিটি র্যান্ডম ম্যাট্রিক্স প্রায় নিশ্চিতভাবে সন্তুষ্ট করে। তারপর, সমস্ত হোল্ডের জন্য ভ্যারিয়েন্স প্যারামিটারটি সংজ্ঞায়িত করুন। ম্যাট্রিক্স আজুমা, হোফডিং এবং ম্যাকডিয়ারমিড বৈষম্য ম্যাট্রিক্স আজুমা আজুমার বৈষম্যের স্কেলার সংস্করণে বলা হয়েছে যে একটি স্কেলার মার্টিঙ্গেল তার গড় মান সম্পর্কে স্বাভাবিক ঘনত্ব প্রদর্শন করে এবং বিচ্যুতির জন্য স্কেল পার্থক্য ক্রমের মোট সর্বোচ্চ বর্গ পরিসীমা দ্বারা নিয়ন্ত্রিত হয়। ম্যাট্রিক্স সেটিং-এ নিম্নলিখিত এক্সটেনশনটি রয়েছে। মাত্রা সহ স্ব-সংযুক্ত ম্যাট্রিক্সের একটি সীমাবদ্ধ অভিযোজিত ক্রম এবং স্ব-সংযুক্ত ম্যাট্রিক্সের একটি নির্দিষ্ট ক্রম বিবেচনা করুন যা প্রায় নিশ্চিতভাবে সন্তুষ্ট করে। ভেরিয়েন্স প্যারামিটারটি গণনা করুন তারপর, সমস্ত ধ্রুবকের জন্য যখন অতিরিক্ত তথ্য পাওয়া যায় তখন 1/8-কে 1/2-এ উন্নত করা যেতে পারে। একটি ক্ষেত্রে ঘটে যখন প্রতিটি যোগফল শর্তসাপেক্ষভাবে প্রতিসম হয়। আরেকটি উদাহরণের জন্য এমন অনুমানের প্রয়োজন যা প্রায় নিশ্চিতভাবে এর সাথে যাতায়াত করে। ম্যাট্রিক্স হোফডিং প্লেসিং সংযোজন অনুমান যে ম্যাট্রিক্স আজুমার সমষ্টিগুলি স্বাধীন, হোফডিংয়ের বৈষম্যের একটি ম্যাট্রিক্স সম্প্রসারণ দেয়। মাত্রা সহ স্বাধীন, এলোমেলো, স্ব-সংযুক্ত ম্যাট্রিক্সের একটি সীমাবদ্ধ ক্রম বিবেচনা করুন এবং স্থির স্ব-সংযুক্ত ম্যাট্রিক্সের একটি ক্রম হতে দিন। ধরে নিন যে প্রতিটি র্যান্ডম ম্যাট্রিক্স প্রায় নিশ্চিতভাবে সন্তুষ্ট করে। তারপরে, যেখানে এই ফলাফলের একটি উন্নতি প্রতিষ্ঠিত হয়েছিলঃ যেখানে ম্যাট্রিক্স সীমাবদ্ধ পার্থক্য (ম্যাকডিয়ারমিড) স্কেলার সেটিংয়ে, ম্যাকডিয়ারমিডের অসমতা একটি ডুব মার্টিঙ্গেলে আজুমার অসমতা প্রয়োগ করে পার্থক্যগুলিকে সীমাবদ্ধ করার একটি সাধারণ উপায় সরবরাহ করে। সীমাবদ্ধ পার্থক্যের বৈষম্যের একটি সংস্করণ ম্যাট্রিক্স সেটিংয়ে রয়েছে। একটি স্বাধীন, র্যান্ডম ভেরিয়েবলের পরিবার হতে দিন, এবং এমন একটি ফাংশন হতে দিন যা ভেরিয়েবলগুলিকে মাত্রার একটি স্ব-সংযুক্ত ম্যাট্রিক্সে ম্যাপ করে। নির্দিষ্ট স্ব-সংযুক্ত ম্যাট্রিক্সের একটি ক্রম বিবেচনা করুন যা প্রতিটি সূচকের জন্য সমস্ত সম্ভাব্য মানগুলির উপর কোথায় এবং পরিসীমা পূরণ করে। ভেরিয়েন্স প্যারামিটারটি গণনা করুন তারপর, সব জায়গার জন্য। এই ফলাফলের একটি উন্নতি প্রতিষ্ঠিত হয়েছিল (আরও দেখুন): সকলের জন্য যেখানে এবং সম্পর্কিত উপপাদ্যগুলির সমীক্ষা এই ধরনের প্রথম সীমানা দ্বারা উদ্ভূত হয়েছিল। স্ব-সংযুক্ত ম্যাট্রিক্স গাউসিয়ান এবং রাডেমাকার সীমানার জন্য উপরের উপপাদ্যটি স্মরণ করুনঃ মাত্রা সহ স্থির, স্ব-সংযুক্ত ম্যাট্রিক্সের একটি সীমাবদ্ধ ক্রমের জন্য এবং স্বাধীন আদর্শ স্বাভাবিক বা স্বাধীন রাডেমাকার র্যান্ডম ভেরিয়েবলের একটি সীমাবদ্ধ ক্রমের জন্য, যেখানে আহলসওয়েড এবং উইন্টার একই ফলাফল দেবে, ব্যতীত। তুলনামূলকভাবে, উপরের উপপাদ্যটিতে কমিউট এবং; অর্থাৎ, এটি বৃহত্তম আইগেনভ্যালুগুলির যোগফলের পরিবর্তে যোগফলের বৃহত্তম আইগেনভ্যালু। এটি কখনই আহলসওয়েড-শীতকালীন মানের (আদর্শ ত্রিভুজ বৈষম্য দ্বারা) চেয়ে বড় নয়, তবে অনেক ছোট হতে পারে। অতএব, উপরের উপপাদ্যটি আহলসওয়েড-শীতকালীন ফলাফলের তুলনায় একটি শক্ত সীমা দেয়। এর প্রধান অবদান ছিল স্ব-সংযুক্ত ম্যাট্রিক্সের ক্ষেত্রে স্কেলার চেরনোফ আবদ্ধ প্রমাণ করতে ব্যবহৃত ল্যাপ্লাস-রূপান্তর পদ্ধতির সম্প্রসারণ (চেরনোফ bound#Additive ফর্ম (পরম ত্রুটি) দেখুন)। নীচের বিবরণে প্রদত্ত পদ্ধতিটি। এই বিষয়ে সাম্প্রতিক সমস্ত কাজ এই একই পদ্ধতি অনুসরণ করে এবং প্রধান পার্থক্যগুলি পরবর্তী পদক্ষেপগুলি থেকে অনুসরণ করে। আহলসওয়েড এবং উইন্টার এগিয়ে যাওয়ার জন্য গোল্ডেন-থম্পসন বৈষম্য ব্যবহার করে, যেখানে ট্রপ লাইবের উপপাদ্য ব্যবহার করে। ধরুন কেউ ডান দিকটি প্রায় স্থির রেখে সিরিজের দৈর্ঘ্য (এন) এবং ম্যাট্রিক্সের মাত্রা (ডি) পরিবর্তন করতে চান। তারপর n অবশ্যই প্রায় d-এর লগ হিসাবে পরিবর্তিত হতে হবে। বেশ কয়েকটি গবেষণাপত্র মাত্রার উপর নির্ভরতা ছাড়াই একটি সীমা স্থাপন করার চেষ্টা করেছে। রুডেলসন এবং ভার্শিনিন ম্যাট্রিক্সের জন্য একটি ফলাফল দেয় যা দুটি ভেক্টরের বাইরের গুণফল। নিম্ন পদমর্যাদার ম্যাট্রিক্সের জন্য মাত্রিক নির্ভরতা ছাড়াই একটি ফলাফল প্রদান করে। মূল ফলাফলটি আহলসওয়েদ-শীতকালীন পদ্ধতি থেকে স্বাধীনভাবে উদ্ভূত হয়েছিল, তবে আহলসওয়েদ-শীতকালীন পদ্ধতি ব্যবহার করে অনুরূপ ফলাফল প্রমাণ করে। পরিশেষে, অলিভিয়েরা অ্যালসওয়েড-শীতকালীন কাঠামো থেকে স্বাধীনভাবে ম্যাট্রিক্স মার্টিঙ্গেলসের জন্য একটি ফলাফল প্রমাণ করে। এ্যালসওয়েড-উইন্টার কাঠামো ব্যবহার করে ট্রপ ফলাফলের সামান্য উন্নতি করে। এই প্রবন্ধে কোনও ফলাফলই উপস্থাপন করা হয়নি। আহলসওয়েদ এবং শীতকালীন-এর উৎপত্তি এবং প্রমাণ ল্যাপ্লাস রূপান্তর যুক্তিটি তার নিজস্ব অধিকারে একটি উল্লেখযোগ্য ফলাফলঃ একটি এলোমেলো স্ব-সংযুক্ত ম্যাট্রিক্স হতে দিন। তারপর এটি প্রমাণ করার জন্য, ঠিক করুন। তারপর দ্বিতীয় থেকে শেষ বৈষম্য হল মার্কভের বৈষম্য। শেষ বৈষম্যটি তখন থেকেই রয়েছে। যেহেতু বাম-সর্বাধিক পরিমাণটি এর থেকে স্বাধীন, তাই অসীম ওভারটি এর জন্য একটি উপরের সীমা হিসাবে রয়ে যায়। সুতরাং, আমাদের কাজ হল বোঝা তবুও, যেহেতু ট্রেস এবং প্রত্যাশা উভয়ই রৈখিক, তাই আমরা তাদের বিনিময় করতে পারি, তাই এটি বিবেচনা করার জন্য যথেষ্ট, যাকে আমরা ম্যাট্রিক্স জেনারেটিং ফাংশন বলি। এখানেই পদ্ধতিগুলি ভিন্ন এবং ভিন্ন। অবিলম্বে পরবর্তী উপস্থাপনাটি অনুসরণ করা হয়। গোল্ডেন-থম্পসন বৈষম্য বোঝায় যে, যেখানে আমরা প্রত্যাশার রৈখিকতা বেশ কয়েকবার ব্যবহার করেছি। ধরুন। এই ফলাফলের পুনরাবৃত্তি করে আমরা একটি ঊর্ধ্বসীমা খুঁজে পেতে পারি। এটি লক্ষ্য করে, তারপর এটি পুনরাবৃত্তি করে, আমরা পাই এখন পর্যন্ত আমরা একটি অসীম ওভারের সাথে একটি বাউন্ড খুঁজে পাই। পরিবর্তে, এটি সীমাবদ্ধ করা যেতে পারে। যাই হোক না কেন, কেউ দেখতে পাবে কিভাবে আহলসওয়েড-শীতকালীন সীমানা বৃহত্তম আইগেনভ্যালুগুলির যোগফল হিসাবে উদ্ভূত হয়। ট্রপ এর প্রধান অবদান হল লাইবের উপপাদ্যের প্রয়োগ যেখানে গোল্ডেন-থম্পসন বৈষম্য প্রয়োগ করা হয়েছিল। ট্রপের উপসংহারটি নিম্নরূপঃ যদি একটি স্থির স্ব-সংযুক্ত ম্যাট্রিক্স হয় এবং একটি এলোমেলো স্ব-সংযুক্ত ম্যাট্রিক্স হয়, তবে প্রমাণঃ ধরা যাক। তারপর লাইবের উপপাদ্য আমাদের বলে যে এটি অবতল। চূড়ান্ত পদক্ষেপটি হল জেনসেনের অসমতা ব্যবহার করে ফাংশনের ভিতরে প্রত্যাশা সরানোঃ এটি আমাদের কাগজের প্রধান ফলাফল দেয়ঃ ম্যাট্রিক্স জেনারেটিং ফাংশনের লগের সাবঅ্যাডিটিভিটি। লগ এম. জি. এফ-এর সাবঅ্যাডিটিভিটি স্বাধীন, এলোমেলো স্ব-সংযুক্ত ম্যাট্রিক্সের একটি সীমাবদ্ধ ক্রম হতে দিন। তারপর সকলের জন্য, প্রমাণঃ এটি ছেড়ে দেওয়ার জন্য যথেষ্ট। সংজ্ঞাগুলি প্রসারিত করে, আমাদের দেখাতে হবে যে প্রমাণ সম্পূর্ণ করার জন্য, আমরা মোট প্রত্যাশার আইন ব্যবহার করি। প্রত্যাশার শর্ত থাকুক। যেহেতু আমরা ধরে নিই যে সবগুলিই স্বাধীন, তাই সংজ্ঞায়িত করুন। পরিশেষে, আমাদের কাছে রয়েছে যেখানে প্রতিটি ধাপে আমরা মাস্টার টেইল বাউন্ড সহ ট্রপের কোরোলারি ব্যবহার করি। নিম্নলিখিতটি পূর্ববর্তী ফলাফল থেকে তাৎক্ষণিকঃ উপরে দেওয়া সমস্ত উপপাদ্য এই বাউন্ড থেকে উদ্ভূত হয়েছে; উপপাদ্যগুলি অসীমকে আবদ্ধ করার জন্য বিভিন্ন উপায়ে গঠিত। এই পদক্ষেপগুলি প্রদত্ত প্রমাণগুলির তুলনায় উল্লেখযোগ্যভাবে সহজ। তথ্যসূত্র রৈখিক বীজগণিত